13

5

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

flag
The moderators are currently discussing closing this question. Please come across to meta.mathoverflow.net if you have a strong opinion about this. – Scott Morrison♦ Oct 30 2009 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 2009 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 2009 at 3:39
1 
 I started a new thread called "Philosophical questions" where this question can be discussed, here: meta.mathoverflow.net/discussion/21/… – Andrew Critch Oct 30 2009 at 6:10
1 
 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 2010 at 12:53
show 2 more comments

closed as not a real question by Scott Morrison♦ Oct 30 2009 at 2:19

2 Answers

6

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

link|flag
4

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

link|flag

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