Turing completeness
The property of a computing system that can perform any calculation a universal Turing machine can perform.
- Year
- 1936
- Section
- Computing
History
A system is Turing-complete when it can carry out any computation that a universal Turing machine can carry out, which means it can simulate that machine and be simulated by it. A Turing machine is an abstract device that reads and writes symbols on an infinite tape following a table of rules. The concept gives a yardstick for the computing power of a machine or language, and today nearly all general-purpose programming languages meet it.
Before the idea was formalized, mechanical calculators such as adders and multipliers were built and refined from the 1830s to the 1940s. They could not make decisions through a conditional branch, so they were not Turing-complete. Charles Babbage designed his analytical engine in the 1830s, and it would have been the first such machine had it been built in his time, although he did not realize that no other machine could surpass it. In the nineteenth century Leopold Kronecker defined primitive recursive functions, which can be computed by repetition but do not allow unbounded loops. In the early twentieth century David Hilbert pursued a program to axiomatize all of mathematics with rules a machine could apply. In 1930 Kurt Gödel showed that a small set of deduction rules suffices to produce every theorem, and his incompleteness theorem revealed the limits of axiom systems when they reason about their own computations.
The notion of computation was isolated soon after. Alonzo Church and Alan Turing independently showed that Hilbert's decision problem has no general solution, which pinpointed the computational core of Gödel's result. Around 1936 Turing described an abstract machine with a tape and a read-write head, and showed that a universal machine can imitate any other. This led to the Church-Turing thesis, a conjecture that anything computable by an algorithm can be computed by a Turing machine. It has never been proven, but no physical counterexample is known.
The first real machines came later. In 1941 Konrad Zuse completed the Z3, a program-controlled computer without conditional jumps, and at the time he was unaware of Turing's work. In 1998 Raúl Rojas showed that the Z3 could simulate such jumps and was therefore Turing-complete in theory, provided its program tape was long enough. The ENIAC, in 1946, was the first computer to perform conditional branching in practice. Zuse's Z4 was operational in 1945 but did not gain conditional branching until 1950.
Real equipment has finite memory, so none is strictly Turing-complete. In everyday usage the term means that one real computer or language can approximately simulate the computational aspects of another, which underlies virtualization and emulation. The halting problem also shows that no general method can predict whether an arbitrary program will ever stop. In practice, tools therefore impose time limits or restrict loops, and those languages fall outside completeness. The property tells us what can be computed in principle, not how easy a program is to write or how long it takes to run.
Timeline
- 1830Charles Babbage designs his analytical engine, which would have been Turing-complete had it been built.
- 1930Kurt Gödel shows that a small set of deduction rules suffices to produce every theorem.
- 1936Alan Turing describes the abstract machine that bears his name and the universal machine that can imitate any other.
- 1941Konrad Zuse completes the Z3, program-controlled but without conditional jumps.
- 1945Zuse's Z4 becomes operational, still without conditional branching.
- 1946The ENIAC becomes the first computer to perform conditional branching in practice.
- 1998Raúl Rojas shows that the Z3 could simulate conditional jumps and be Turing-complete in theory.
Trivia and anecdotes
A calculator with limits
Mechanical adders and multipliers of the nineteenth and twentieth centuries were useful, but they could not choose what to do based on a result, so they fell outside completeness.
Spreadsheets that go further
A spreadsheet without cycles is not Turing-complete, but the macro language of Excel is.
Complete in theory, not in practice
Zuse's Z3 could be Turing-complete only if its program tape were long enough, which was not the case in practice.