How would this affect the practical nature of the problem? Also, why is this novel? All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem.
It's not an earth-shattering paper, it's a technical curiosity.
the OP is a light article about a light paper, to promote a new lightweight journal that launched this week.
I think the argument should be the other way around.
The halting problem doesn't say "given any Turing machine, no algorithm can determine whether it halts". It says "no algorithm can determine whether any given Turing machine halts".
In the Generative Adversarial Network (GAN) framework, this would be the One Weird Trick the generator could pull that would always foil the discriminator.
This paper is interesting because it connects learnability to a different kind of undecidability than the Halting Problem: the Continuum Hypothesis. In some ways it's more troubling than the Halting Problem, because at least we can usually figure out whether some actual program halts, using some cleverness, but no one can begin to say whether the Continuum Hypothesis is true or false.
The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). That's good news, because it implies the EMX learning model will work:
> Their results imply that the finite subsets of the unit interval have monotone-compression schemes, and therefore are learnable in EMX, if and only if the continuum hypothesis is true, which is known to be unprovable.
If someone comes along and casts doubt on the Continuum Hypothesis through some mystical but persuasive line of reasoning (news flash: not gonna happen), then there might be some EMX functions that can't be learned, but no one is going to lose sleep over that. There are lots of more immediate reasons why machine learning fails in practice, like not having good training data.
> The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals).
I don't think this is correct. It's very well-accepted that CH is independent of ZFC. Now, you might mean that most mathematicians suspect that adding CH to ZFC is more intuitive/natural/useful than adding !CH to ZFC, but that's a quite different statement. I don't know much about this, but it seems plausible that both extensions of ZFC could be useful for different things, in the same way that using the parallel postulate is useful for some things (Euclidean geometry) and using alternative parallel postulates is useful for other things (non-Euclidean geometries).
The P=NP problem, AFAIK, isn't yet proven to be independent of ZFC, although I have heard some seemingly educated people suggest their suspicions that it may be.
And now you have me wondering if you win the Millennium Prize if you prove that P=NP is independent of ZFC. Surely you would.
Yes, the P=NP problem is not yet proven to be independent of ZFC. It's certainly a possibility, and to be honest a quite intriguing and fun one, but we shouldn't make the mistake to think that any hard open problem is independent of ZFC. (I know that you didn't state that, I'm just writing this for the record.) Sometimes hard open problems are simply hard open problems.
I guess I'm a constructivist about this.
You can't just wave your hands and take !CH as an axiom. Remember what that means: you reject that there is no set with cardinality between the integers and the reals, so you're implying there is such a set. I realize not all mathematicians share this point of view, but if you can't somehow construct the intermediate set you're claiming exists, or show that it can be constructed, then you don't really have any grounds for taking !CH to be true. Without a positive reason for believing such a set exists, I have a hard time pretending that !CH could possibly be a "useful" (your word) axiom to add to ZFC.
By contrast, imagining that CH might be true is easy. You don't have to construct any never-before-seen mathematical objects to make your point. You just presume, without fear of being contradicted by ZFC, that the integers are countably infinite, and the reals are uncountably infinite but only sort of "minimally" so (there are higher orders of uncountable infinity, but none lower). You may never be able to prove CH (certainly not with ZFC, and almost certainly not with any other logical system), but at least the model makes sense: there's no cardinality in between that of the integers and the reals.
Which is not to say that CH is particularly useful! In fact, maybe the most interesting thing about the paper is the idea that the CH could be meaningfully connected to anything in an applied form of math like machine learning. Does that weird connection between CH and ML have any practical consequences for ML in general, or the EMX learning algorithm in particular? Probably not, especially since assuming CH is true just implies EMX should work, so it's fine to keep using it to solve learning problems.
In other words, if you wanted to convince an ML practitioner that their learning algorithms might be unreliable because the Continuum Hypothesis might be false, I think they would be within their rights to request you show them an actual set with cardinality between the integers and the reals. When you couldn't, they would then be within their rights to ignore your objection.
You say you do math and not philosophy, but the whole CH independence proof kinda moves this discussion out of the realm of (ZFC-based) math, doesn't it? If you don't want to consider philosophy here, there's not much more to say.
Even Grothendieck's EGA has a couple of arguments that cannot be carried out in ZFC in the generality he presents them in, but I wouldn't call EGA a philosophy treatise nor an algebraic geometer a philosopher
In their example they are expressing it in set theory and than operating on it...
I probably failed at explaining on a simple level...sorry
Assumption that all learning algorithms can be implemented on a Turing machine cannot hold true, since there are mathematical problems that cannot (take for example https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem). Unless you categorise machine learning problems as problems that can be implemented with a Turing machine, making the statement a tautology.
Edit: thinking about my comment maybe I am the one being tautologic. If there is a learning algorithm that can solve Hilbert's problem it would transcend mathematics
Turing machines are just a formalization of the concept of algorithms/computer programs.
So problems that can't be implemented as a Turing machine are not "learning algorithms", or any kind of algorithm.
A Turing Machine represents the most complete computational toolkit we happen to know of--not the most complete computational toolkit possible. If we discovered a new computational trick tomorrow--one that a Turing Machine can't perform (the ability to solve the halting problem for Turing Machines, for instance), then we would have discovered another--higher--class of computers, and it would be a reasonable linguistic move to refer to their programs as "algorithms" as well.
That said, the models of computation bifurcate when studying the question which higher-order functions (functions which input functions as arguments) are computable. Such a function can be easily computable according to one model and not computable at all according to another. I'm writing this because far too often the unqualified statement "all the usual models of computation are equivalent" is made. This is emphatically only true for first-order computation, not for higher-order computation.
The Church-Turing thesis can't be proven, since it is a statement about what is possible in the physical universe, not a statement about mathematics. But the intuitive arguments in favor of it (i.e., that Turing machines capture exactly what we mean by "computation") are, for me, extremely convincing.
...but whether or not it's Turing's, it's still a valid position to take. It just strikes me as a trope of human history to identify the limits with our limits. Kind of like how we once thought we were the center of the universe.
Yeah, it seems unlikely that we'll ever watch a neural network perform an action that would yield an unprovable result, but given that we can't know either way I think it's more fun to think that it's at least possible.
* http://www.cse.uconn.edu/~dqg/papers/strong-cct.pdf The Interactive Nature of Computing: Refuting the Strong Church-Turing Thesis (Published version here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455...)
* https://www.semanticscholar.org/paper/Computability-Beyond-C...
See also a previous hacker news discussion of the Church-Turing thesis here:
https://news.ycombinator.com/item?id=18253994
albeit I take issue with the supposed "proof" by counter example via Compass & Straightedge construction given in the video there, due to results like these two:
* https://link.springer.com/article/10.1007/s10472-018-9603-0 Kellison, Ariel; Bickword, Mark; Constable, Robert L. - Implementing Euclid’s straightedge and compass constructions in type theory [September 2018] (Code here: http://www.nuprl.org/LibrarySnapshots/Published/Version2/Mat...)
* https://geocoq.github.io/GeoCoq/ (Numerous papers by Michael Beeson et al., just check the page, I won't link them all here)
(Note that the authors of the two above works take very different yet similar approaches to the whole matter, it really pays off to compare both to each other.)
However, there seem to exist at least two different spanners in the works:
* https://link.springer.com/article/10.1007/s10472-018-9610-1 Makowsky, Johann A. - Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries
* https://link.springer.com/chapter/10.1007/978-3-662-57669-4_... Makowsky, Johann A. - The Undecidability of Orthogonal and Origami Geometries
(If the first of the two above papers makes you wonder "well who DIDN'T overlook Ziegler's theorem... Well... https://scholar.google.com/scholar?cites=2279217158168053275)
Oh and in case anyone here still believes Hilbert's old wives tale about /his/ Axiom of Choice, there's plenty of AC to go around in constructive mathematics:
https://vrahli.github.io/articles/bar-induction-lics-long.pd...
But if that doesn't convince you yet, you might go through the 5 stages of accepting it anyway, as outlined by Andrej Bauer here:
* https://mathoverflow.net/questions/25363/au-revoir-law-of-ex...
* Here: https://www.youtube.com/watch?v=21qPOReu4FI
* And here: https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
And here's one last paper to almost conclude what turned into a bit of a larger-than-I-expected Constructivism propaganda piece comment:
http://t-news.cn/Floc2018/FLoC2018-pages/preprint_cX1w.pdf "On Expanding Standard Notions of Constructivity"
And to now conclude this, a semi-joke: Wouldn't the fact that one can't prove the Church-Turing thesis, but could falsify it by counterexample, put propagation of belief in the meme of the Church-Turing thesis into either the complexity class of RE, or co-RE? ;)