Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
The moderators are currently discussing closing this question. Please come across to tea.mathoverflow.net if you have a strong opinion about this. –  Scott Morrison Oct 30 '09 at 2:19
I don't really want to use the "not a real question" tag, but I think the consensus is that this question to too broad or too vague. –  Scott Morrison Oct 30 '09 at 2:20
I think Kevin should be given a chance to edit his question before it is closed. It's not a bad question, just a bit vague. Give it more than an hour before it's closed. –  Grétar Amazeen Oct 30 '09 at 3:39
I started a new thread called "Philosophical questions" where this question can be discussed, here: tea.mathoverflow.net/discussion/21/philosophical-questions/… –  Andrew Critch Oct 30 '09 at 6:10
I voted to reopen this question, since I think that mathematicians can have a lot to say about it. This topic is certainly one that is treated in any graduate level mathematics course on computability theory. –  Joel David Hamkins Mar 20 '10 at 12:53
show 2 more comments

closed as not a real question by Scott Morrison Oct 30 '09 at 2:19

It'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.

2 Answers

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 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...

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 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 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".

share|improve this answer
add comment

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

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.