Turing completeness is significant in that every real-world design for a computing device can be simulated by a
universal Turing machine. The
Church–Turing thesis states that this is a law of mathematics that a universal Turing machine can, in principle, perform any calculation that any other programmable
computer can. This says nothing about the effort needed to write the
program, or the time it may take for the machine to perform the calculation, or any abilities the machine may possess that have nothing to do with computation.
Charles Babbage's
analytical engine (1830s) would have been the first Turing-complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform a conditional branch and therefore were not Turing-complete. In the late 19th century,
Leopold Kronecker formulated notions of computability, defining
primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions that compute them do not allow for an infinite loop. In the early 20th century,
David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction that could be performed by a machine. Soon it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved by
Kurt Gödel in 1930 to be enough to produce every theorem. The actual notion of computation was isolated soon after, starting with
Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation that deduces their theorems. Church and Turing independently demonstrated that Hilbert's (decision problem) was unsolvable, thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on
general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique. In 1941
Konrad Zuse completed the
Z3 computer. Zuse was not familiar with Turing's work on computability at the time. In particular, the Z3 lacked dedicated facilities for a conditional jump, thereby precluding it from being Turing complete. However, in 1998, it was shown by Rojas that the Z3 is capable of simulating conditional jumps, and therefore Turing complete in theory. To do this, its tape program would have to be long enough to execute every possible path through both sides of every branch. The first computer capable of conditional branching in practice, and therefore Turing complete in practice, was the
ENIAC in 1946. Zuse's
Z4 computer was operational in 1945, but it did not support conditional branching until 1950. ==Computability theory==