3 ms·
It's not a math theorem. From http://mathworld.wolfram.com/Church-TuringThesis.html http://mathworld.wolfram.com/Church-TuringThesis.html There has never
by waynecochran 8y ago
It's not a math theorem.
From http://mathworld.wolfram.com/Church-TuringThesis.html http://mathworld.wolfram.com/Church-TuringThesis.html
There has never been a proof, but the evidence for
its validity comes from the fact that every
realistic model of computation, yet discovered,
has been shown to be equivalent.
http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/ChurchTuring.pdf http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/...
The Church–Turing Thesis is an extramathematical
proposition, not subject to formal proof.
- baddox 8y agoYou're right. The thesis is that nothing in the real world can compute a function that a Turing machine cannot, which is not proven (and it's not clear how it even could be proven). What is proven formally is the equivalence of several different formulations.