History
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. Obviously, 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 an "if/goto" and therefore are not true computers.
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 which 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 which 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 to be enough to produce every theorem by Kurt Gödel in 1930. Gödel's completeness theorem of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.
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 which deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (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.
John von Neumann was inspired by these results to design actual working universal computing machines. The first formal programming languages of the 1930s demonstrated that such a computer would be useful. The first actual implementation of a Turing-complete machine appeared in 1941: the program-controlled Z3 of Konrad Zuse, but the first machine explicitly designed to be Turing complete and widely appreciated as being universal was the 1946 ENIAC. This machine was able to solve a wide range of effective problems in the 1940s, many related to atomic bomb design.
Read more about this topic: Turing Completeness
Famous quotes containing the word history:
“Philosophy of science without history of science is empty; history of science without philosophy of science is blind.”
—Imre Lakatos (1922–1974)
“A man acquainted with history may, in some respect, be said to have lived from the beginning of the world, and to have been making continual additions to his stock of knowledge in every century.”
—David Hume (1711–1776)
“Every library should try to be complete on something, if it were only the history of pinheads.”
—Oliver Wendell Holmes, Sr. (1809–1894)