Church's thesis states that the Turing machine is a universal model of computation. What is the most compelling argument supporting this assertion?
closed as not a real question by Scott Morrison♦ Oct 30 '09 at 2:19It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question. 


There is a good amount of 'experimental evidence', I guess. There have been lots of other models proposed, and they've all been proven to be computationally equivalent to Turing machines. This is true even for quantum computers. 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 polynomialtime equivalence. This leads to the 'strong ChurchTuring 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 ChurchTuring thesis would be false. Then the natural thing would be to assert a quantum version of the strong ChurchTuring thesis... 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 lambda calculus. 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 Turingequivalent. 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 not be strictly more powerful than Turing machines? There is (probably) no good mathematical answer to this, because there is (probably) no good mathematical definition of "reasonable". 


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

