3 ms·
I don’t think that’s quite the case. The theorem is a mathematical given formalizations of computability (algorithms). Those formalizations were devised to refl
by baddox 8y ago
I don’t think that’s quite the case. The theorem is a mathematical given formalizations of computability (algorithms). Those formalizations were devised to reflect what seems to be the physical limits of computers in the real world, of course. If we discovered more powerful methods of computation in the real world, we would presumably update our mathematical formalizations, but the math behind the current formalizations is correct (in the same way that the math used in Newtonian physics is correct even though we now know that non-Newtonian physics are needed to analyze certain phenomena.
- waynecochran 8y agoIt'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.