# Why is Turing completeness right?

I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can perform any possible computation.

Of course, calculating machines of one kind or another go back to antiquity. People have built machines which for performing addition and subtraction (e.g., an abacus), multiplication and division (e.g., the slide rule), and more domain-specific machines such as calculators for the positions of the planets.

The striking thing about a computer is that it can perform any computation. Any computation at all. And all without having to rewire the machine. Today everybody takes this idea for granted, but if you stop and think about it, it's kind of amazing that such a device is possible.

I have two actual questions:

1. When did mankind figure out that such a machine was possible? Has there ever been any serious doubt about whether it can be done? When was this settled? (In particular, was it settled before or after the first actual implementation?)

2. How did mathematicians prove that a Turing-complete machine really can compute everything?

That second one is fiddly. Every formalism seems to have some things that cannot be computed. Currently "computable function" is defined as "anything a Turing-machine can compute". But how do we know there isn't some slightly more powerful machine that can compute more stuff? How do we know that Turing-machines are the correct abstraction?

• Computers (and their theoretical models, like Turing machines) CANNOT compute everything. Check out for example the Halting Problem.
– kol
Commented Jun 23, 2012 at 14:12
• Answer to second question: we don't prove this; it's a matter of definition; it turns out what we think intuitively of "computable" is computable by Turing machines (or anything equivalent). This claim is known as Church-Turing thesis. Commented Jun 23, 2012 at 15:03
• What would it mean to disprove Church-Turing thesis? Commented Jun 23, 2012 at 22:54
• Machines like your PC that have finite memory are not Turing equivalent. Turing machines have an unbounded tape which means that the longer a computation continues, the more memory they can potentially use. PCs cannot perform computations that take finite time but that require more storage than they have available. Commented Jun 23, 2012 at 23:51
• @MikeSamuel this is a pedantic distinction and akin to saying "there is a finite number of particles in the universe, thus everything is finite state". It is a true statement, but not a useful one. It is seldom useful to model a real-world computer as a finite state machine. Commented Jun 24, 2012 at 2:38

Mankind formalized computation and developed two system for it in 1936 with the seminal papers of Alonzo Church on $\lambda$-calculus and Alan Turing (who today, June 23rd 2012, would turn 100 years old if not for despicable circumstances leading to his early passing) on what became known as Turing-machines. Both mathematicians were solving the Entscheidungsproblem.

Although Church's paper was published slightly earlier, Turing was unaware of it when he developed his ideas, and Turing's approach proved to be more useful for the design of real-world machines. This was because he showed how to design a Universal Turing Machine that could be programmed to run any computation. This universal machine, with a concrete architecture based on the work of John von Neumann is the basic idea behind the machine on which you are reading my answer.

As you noted, computable is defined as "computable on a Turing machine" and all other reasonable models of computation have proven to be equivalent in their power. The belief that all reasonable models of computation are equivalent in what decision problems they can solve is known as the Church-Turing thesis. In its original form, it is almost completely believed by the learned community. In fact it is not completely clear what it would mean to prove/disprove the Church-Turing thesis; in a lot of ways it becomes an empirical question.

However, there is still the extended Church-Turing thesis which asks the slightly more subtle question of: what can be computed efficiently?. Many classical models, such as $\lambda$-calculus, Turing Machines, tag-based systems, cellular automata, etc are equivalent under the extended thesis as well. However, the recent development of quantum computing casts doubt on the extended thesis. Although most people who work on quantum computers (including me) believe they are more efficient that classical ones, the matter is subject to scholarly debate. Note that in terms of the coarse notion of what is computable (as opposed to efficiently computable) quantum computing is still equivalent to Turing's model.

• Turing's 1936 paper, compared to Church's work at the time, was much more compelling in its argument that any numerical function that can be computed algorithmically by a human can be computed by a Turing machine. Church's formalisms did not obviously have that property, and to this day the reduction of other computational systems to Turing machines is vital because of Turing's original analysis of what Turing machines can compute. Commented Jun 24, 2012 at 2:06
• @CarlMummert I definitely agree, but Church's work must be mentioned for completeness. Also, it is not at all insignificant, while most of Theory A is built around TMs, Theory B is much more lambda-calc friendly. So it is also partially a difference of cultures. Commented Jun 24, 2012 at 2:35
• Wait - so you're saying that it hasn't been proven that there is no more powerful computational system? It's merely an assumption? Commented Jun 24, 2012 at 16:16
• @MathematicalOrchid all reasonable models of computation (reasonable roughly means: at one time only working on finite sections of objects and only doing one of finitely many options) that I am familiar with have been shown equivalent to Turing machines. Commented Jun 24, 2012 at 16:30
• @MathematicalOrchid To provide a potentially more straightforward answer to your follow-up question: right, nobody has proven that that there isn't some reasonable model of computation more powerful than a TM. "Assumption" is one word for it; "hypothesis" is another. We could wake up tomorrow and see about a new, better model of computing on CNN. It's unlikely, but possible. Commented Jun 25, 2012 at 1:33

There's a reason it's called a Turing Machine, and it's because it was invented by Alan Turing. He did a 1936 paper on it, establishing these concepts. If you want to know more about Turing Machines, check the paper. It was seriously doubted, before he designed and built one that cracked the Enigma, that this concept could actually work. However the British were pretty desperate and he was a genius, so they trusted him and it paid off massively.

However, when you think about it some more, it's really not that amazing at all. It was known long before Turing that all of mathematics could be reduced to some set of axioms. All you would have to do is give the instruction set the ability to perform these axioms, and off you go.

• Turing did not design or build enigma (although he did design another computer which was never built). Your second paragraph is well made: a lot of the excitement around the time of Turing (and indeed this was the point of his own paper) related to the limits of computation. Commented Jun 23, 2012 at 14:05
• We trusted him? Only up until he was publically proven to be a homosexual, then we killed him for it. Also it's been proven that there are a set of problems that can be stated within any axiomatic framework that can never be proven with those axioms.
– Tony Hopkinson
Commented Jun 23, 2012 at 14:21
• @TonyHopkinson: I know. However, the job of the TM is not to compute everything, but only to compute what can be computed. Your statement only says that there are some computations which cannot be proven to be correct. That does not mean that they cannot be done.