4 ms·
The Church-Turing Theorem is not really a mathematical theorem; It is more like F = Ma in Physics. It's an empirical result.
by waynecochran 8y ago
The Church-Turing Theorem is not really a mathematical theorem; It is more like F = Ma in Physics. It's an empirical result.
- baddox 8y agoI 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.
- contravariant 8y agoIt's not a theorem, but that's because it's not proven, or can't be proven really. Unless you're referring to the fact that those three definitions coincide, that is a theorem. The statement F=ma is either a definition, axiom or theorem depending on what context you're working in. There are more fundamental (empirically tested) axioms that have F=ma as a consequence. Unless you introduce special relativity, then it becomes false.
- kccqzy 8y agoThe statement that "f is generally recursive iff it is Turing computable" is a theorem that can be proven, because we can rigorously define what it means to be Turing computable (computable by a Turing machine which is precisely defined) and generally recursive (which is the smallest set of functions closed under projection, composition, primitive recursion and minimalization). The theorem was proven by Turing and Kleene soon after the concept of Turing computable was introduced. But if you remove the word "Turing" it is no longer a theorem. It becomes a thesis because we don't have a definition of what it means to be computable. It is in fact an innovation of Turing to identify computable with Turing computable, but that's by no means universal.
- ccalf 8y agoI think it's clearer to understand the Church-Turing thesis as two theses, not one. Turing's thesis was that (intuitive) computability equals (formalizable) Turing computability. So you could completely ignore the recursive functions part (and so, Church's Thesis) and there would still be the same sort of lay confusion about the computability thesis.