non-computability of overfitting

[Timothy Y. Chow]

Sam Sanders wrote:
> The question is thus whether the below ML result is of the same kind, or whether
>
> "ML problems that appear in practise"
>
> are undecidable.

It is surely the case that undecidable problems are irrelevant to 
practical machine learning.  This topic has come up before on FOM.

https://cs.nyu.edu/pipermail/fom/2019-January/021338.html
https://cs.nyu.edu/pipermail/fom/2019-February/021380.html

Along similar lines, about twenty years ago, Carl de Marcken of ITA 
Software (later purchased by Google) showed that a certain problem arising 
from airline scheduling was undecidable.  I'm not sure if he ever formally 
published a paper, but you can find some details here:

https://web.archive.org/web/20050215180009/http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf

Of course, as usual when practical problems are concerned, the real 
problem involves at worst an exhaustive search over finitely many 
possibilities, so the undecidability result just a theoretical curiosity.

Tim