Hacker News Reader

Comment by yes_man | Hacker News Reader

> 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). 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

View on HN

"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.

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.

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.

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/

...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.

That depends on what you mean by "Church-Turing thesis":

* 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? ;)

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

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.

Reply on news.ycombinator.com