5 ms·

> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. Assumption that all learning algorith

> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. 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 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

umanwizard 8y ago
"X can be implemented as a Turing machine" means the same thing as "there exists an algorithm to do X". 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.
- deleted 8y ago
  [deleted]
- __MatrixMan__ 8y ago
  I think that simplifies things a bit too far. 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.
  - umanwizard 8y ago
    It is probably not possible to discover a new computational trick, by the Church-Turing thesis. 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.
    - __MatrixMan__ 8y ago
      The Church-Turing thesis has more to do with what a human can achieve than what is physically possible. I think your position appears section 2 here: https://plato.stanford.edu/entries/church-turing/ https://plato.stanford.edu/entries/church-turing/ ...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.
    - no_identd 8y ago
      That depends on what you mean by "Church-Turing thesis": * http://www.cse.uconn.edu/~dqg/papers/strong-cct.pdf 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.4770&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455...) * https://www.semanticscholar.org/paper/Computability-Beyond-Church-Turing-via-Choice-Bickford-Cohen/dfd626bdd64b7722d473ad15e3f327610f2e9288 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 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 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/Mathematics/reals!model!euclidean!geometry/index.html http://www.nuprl.org/LibrarySnapshots/Published/Version2/Mat...) * https://geocoq.github.io/GeoCoq/ 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 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_15 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 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.pdf 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-excluded-middle/25385 https://mathoverflow.net/questions/25363/au-revoir-law-of-ex... * Here: https://www.youtube.com/watch?v=21qPOReu4FI https://www.youtube.com/watch?v=21qPOReu4FI * And here: https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf 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 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? ;)
  - roywiggins 8y ago
    Scott Aaronson's paper "NP-complete Problems and Physical Reality" makes some persuasive arguments about what sorts of computations are probably at all plausible to implement in reality. https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf
  - IngoBlechschmid 8y ago
    All usual models of computation (such as Turing machines, register machines, the lambda calculus, ...) agree on which functions from the naturals to the naturals they deem computable, and the Church–Turing thesis states that these are exactly those functions which can actually be computed by machines in the real world. 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.

umanwizard 8y ago

"X can be implemented as a Turing machine" means the same thing as "there exists an algorithm to do X". 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.

deleted 8y ago
[deleted]
__MatrixMan__ 8y ago
I think that simplifies things a bit too far. 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.
- umanwizard 8y ago
  It is probably not possible to discover a new computational trick, by the Church-Turing thesis. 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.
  - __MatrixMan__ 8y ago
    The Church-Turing thesis has more to do with what a human can achieve than what is physically possible. I think your position appears section 2 here: https://plato.stanford.edu/entries/church-turing/ https://plato.stanford.edu/entries/church-turing/ ...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.
  - no_identd 8y ago
    That depends on what you mean by "Church-Turing thesis": * http://www.cse.uconn.edu/~dqg/papers/strong-cct.pdf 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.4770&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455...) * https://www.semanticscholar.org/paper/Computability-Beyond-Church-Turing-via-Choice-Bickford-Cohen/dfd626bdd64b7722d473ad15e3f327610f2e9288 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 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 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/Mathematics/reals!model!euclidean!geometry/index.html http://www.nuprl.org/LibrarySnapshots/Published/Version2/Mat...) * https://geocoq.github.io/GeoCoq/ 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 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_15 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 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.pdf 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-excluded-middle/25385 https://mathoverflow.net/questions/25363/au-revoir-law-of-ex... * Here: https://www.youtube.com/watch?v=21qPOReu4FI https://www.youtube.com/watch?v=21qPOReu4FI * And here: https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf 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 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? ;)
- roywiggins 8y ago
  Scott Aaronson's paper "NP-complete Problems and Physical Reality" makes some persuasive arguments about what sorts of computations are probably at all plausible to implement in reality. https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf
- IngoBlechschmid 8y ago
  All usual models of computation (such as Turing machines, register machines, the lambda calculus, ...) agree on which functions from the naturals to the naturals they deem computable, and the Church–Turing thesis states that these are exactly those functions which can actually be computed by machines in the real world. 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.