most recent 30 from http://mathoverflow.net 2013-06-19T02:41:29Z http://mathoverflow.net/feeds/question/3360 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3360/what-is-the-most-compelling-reason-to-believe-churchs-thesis foocorge 2009-10-30T00:38:12Z 2009-10-30T15:04:25Z

<p>Church's thesis states that the Turing machine is a universal model of computation. What is the most compelling argument supporting this assertion?</p>

http://mathoverflow.net/questions/3360/what-is-the-most-compelling-reason-to-believe-churchs-thesis/3362#3362 lhf 2009-10-30T01:01:47Z 2009-10-30T01:01:47Z

<p>The usual answer is that all proposed models of computation have turned out to be equivalent.</p>

http://mathoverflow.net/questions/3360/what-is-the-most-compelling-reason-to-believe-churchs-thesis/3363#3363 Kevin Lin 2009-10-30T01:07:01Z 2009-10-30T15:04:25Z

<p>There is a good amount of 'experimental evidence', I guess. There have been lots of other models proposed, and <a href="http://en.wikipedia.org/wiki/Church%E2%80%93Turing%5Fthesis#Success%5Fof%5Fthe%5Fthesis" rel="nofollow">they've all been proven to be computationally equivalent to Turing machines</a>. This is true even for <a href="http://en.wikipedia.org/wiki/Quantum%5Fcomputer" rel="nofollow">quantum computers</a>. That is, they can all do the exact same things that Turing machines can. But there is also the question of whether this equivalence is a polynomial-time equivalence. This leads to the 'strong Church-Turing thesis'. It is believed by many that quantum computers are strictly better than classical computers in terms of time complexity, though as far as I know this has not been proven yet. If this were proven, then the strong Church-Turing thesis would be false. Then the natural thing would be to assert a quantum version of the strong Church-Turing thesis...</p> <p><hr /></p> <p>Edit: I see that this topic has been closed. I agree that it is perhaps too philosophical for Math Overflow. But still, let me make a few more mathematical comments, and one philosophical comment. Consider the <a href="http://en.wikipedia.org/wiki/Lambda%5Fcalculus" rel="nofollow">lambda calculus</a>. This is a very simple model of computation; its functionality is essentially restricted to a notion of a function and a notion of evaluation of functions which allows for recursion. The interesting thing is that even with this seemingly very limited functionality, the lambda calculus is still Turing-equivalent. What this shows is that it is relatively easy for a "reasonable model of computation" to be at least as powerful as Turing machines; once it has a notion of functions and a notion of evaluation of functions, it will be at least as powerful as the lambda calculus, and thus Turing machines. The more philosophical question arises when we consider the converse situation, namely, why should we expect "reasonable models of computation" to <em>not</em> be strictly <em>more</em> powerful than Turing machines? There is (probably) no good mathematical answer to this, because there is (probably) no good mathematical definition of "reasonable".</p>