[FOM] Learnability

[Josef Urban]

I have not properly read the paper (which indeed looks interesting), but
the surprise likely comes from the assumption that ML is a "pretty
practical task".

But we may try to learn all sorts of "not so practical" tasks - e.g.
estimating the halting of a Turing machine (program), provability of an
arbitrary FOL/HOL/ZFC proposition, etc. And some of the "seemingly
practical" tasks may in full generality be very hard.

Already Turing in his 1950 seminal paper on AI discusses some of these
relations (e.g., Godel/Turing results vs feasibility of AI).

Josef

On Thu, Jan 17, 2019 at 3:17 AM Victor Marek <marek at cs.uky.edu> wrote:

> During a routine perusal of the site RealClearScience.com, I read the piece
> about the article "Learnability can be undecidable", by S. Ben-David, P.
> Hrubes
> et.al. The piece is published in the journal Nature Machine Intelligence.
> In that paper the authors appear to show that certain aspect of machine
> learning
> (pretty practical task) is equivalent (in ZFC) to Continuum Hypothesis
> which
> is (as we know since P.J. Cohen) undecidable in ZFC.
>
> I never did Machine Learning, and this appears to be absolutely incredible.
> The piece in RealClearScience is a product of a science writer, not
> necessarily
> knowing what s/he is talking about.
>
> Obviously, the matter is relevant to F.O.M. Could someone in the community
> make
> this matter clearer for pedestrians such as I?
>
> Thanks,
>
>                 Victor Marek
> Victor W. Marek                                 Department of Computer
> Science
> marek at cs.uky.edu                                        University of
> Kentucky
> marek at cs.engr.uky.edu                                 Lexington, KY
> 40506-0633
> 859-257-3496 (office)                                     859-257-3961
> (Dept)
> http://www.cs.uky.edu/~marek                              859-257-1505
> (FAX)
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20190117/1b2047b7/attachment.html>