Editing Turing completeness (section)

==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{{snd}} 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 [[computer program|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.{{citation needed|date=December 2021}} 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 function]]s. 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 {{lang|de|[[Entscheidungsproblem]]}} (decision problem) was unsolvable,<ref>{{ Citation | last = Hodges | first = Andrew | author-link = Andrew Hodges | orig-year = 1983 | year = 1992 | title = Alan Turing: The Enigma |location = London | publisher=Burnett Books | page = 111 | isbn = 0-04-510060-8 | title-link = Alan Turing: The Enigma }}</ref> thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on [[general recursive function]]s, 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)|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.<ref>{{cite journal |first=Raul |last=Rojas |title=How to make Zuse's Z3 a universal computer |journal=Annals of the History of Computing |volume=20 |issue=3 |pages=51–54 |year=1998 |doi=10.1109/85.707574  |url=https://www.researchgate.net/publication/3330654}}</ref>

The first computer capable of conditional branching in practice, and therefore Turing complete in practice, was the [[ENIAC]] in 1946. Zuse's [[Z4 (computer)|Z4]] computer was operational in 1945, but it did not support conditional branching until 1950.<ref>{{Cite journal|last=Rojas|first=Raúl|date=2014-02-01|title=Konrad Zuse und der bedingte Sprung|trans-title=Konrad Zuse and the conditional jump|journal=Informatik-Spektrum|language=de|volume=37|issue=1|pages=50–53|doi=10.1007/s00287-013-0717-9|s2cid=1086397|issn=0170-6012}}</ref>