Editing Turing machine (section)

==History==
{{See also|Algorithm|Church–Turing thesis}}

===Historical background: computational machinery===
[[Robin Gandy]] (1919–1995)—a student of Alan Turing (1912–1954), and his lifelong friend—traces the lineage of the notion of "calculating machine" back to [[Charles Babbage]] (circa 1834) and actually proposes "Babbage's Thesis":

{{blockquote|''That the whole of development and operations of analysis are now capable of being executed by machinery''.|(italics in Babbage as cited by Gandy, p. 54)}}

Gandy's analysis of Babbage's [[analytical engine]] describes the following five operations (cf. p.&nbsp;52–53):
# The arithmetic functions +, −, ×, where − indicates "proper" subtraction: {{nowrap|''x'' − ''y'' {{=}} 0}} if {{nowrap|''y'' ≥ ''x''}}.
# Any sequence of operations is an operation.
# Iteration of an operation (repeating n times an operation P).
# Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
# Conditional transfer (i.e., conditional "[[goto]]").

Gandy states that "the functions which can be calculated by (1), (2), and (4) are precisely those which are [[Turing computable]]." (p.&nbsp;53). He cites other proposals for "universal calculating machines" including those of [[Percy Ludgate]] (1909), [[Leonardo Torres Quevedo]] (1914),<ref name="LTQ1914es">L. Torres Quevedo. ''Ensayos sobre Automática – Su definicion. Extension teórica de sus aplicaciones,'' Revista de la Academia de Ciencias Exacta, Revista 12, pp. 391–418, 1914.</ref><ref name="LTQ1915fr">Torres Quevedo. L. (1915). [https://diccan.com/dicoport/Torres.htm "Essais sur l'Automatique - Sa définition. Etendue théorique de ses applications"], ''Revue Génerale des Sciences Pures et Appliquées'', vol. 2, pp. 601–611.</ref> [[Maurice d'Ocagne]] (1922), [[Louis Couffignal]] (1933), [[Vannevar Bush]] (1936), [[Howard Aiken]] (1937). However:

{{blockquote|… the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized…|Gandy p. 55}}

===The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900===
With regard to [[Hilbert's problems]] posed by the famous mathematician [[David Hilbert]] in 1900, an aspect of [[Hilbert's tenth problem|problem #10]] had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for No. 10 is as follows:

{{blockquote|''10. Determination of the solvability of a Diophantine equation''. Given a [[Diophantine equation]] with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

The Entscheidungsproblem [decision problem for [[first-order logic]]] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.|quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008}}

By 1922, this notion of "[[Entscheidungsproblem]]" had developed a bit, and [[Heinrich Behmann|H. Behmann]] stated that

{{blockquote|...&nbsp;most general form of the Entscheidungsproblem [is] as follows:
<blockquote>A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion ...</blockquote>|Gandy p. 57, quoting Behmann}}
{{blockquote|Behmann remarks that ... the general problem is equivalent to the problem of deciding which mathematical propositions are true.|''ibid.''}}
{{blockquote|If one were able to solve the Entscheidungsproblem then one would have a "procedure for solving many (or even all) mathematical problems".|''ibid.'', p. 92}}

By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics ''[[Completeness (logic)|complete]]'' ... Second, was mathematics ''[[Consistency proof|consistent]]'' ... And thirdly, was mathematics ''[[Decidability (logic)|decidable]]''?" (Hodges p.&nbsp;91, Hawking p.&nbsp;1121). The first two questions were answered in 1930 by [[Kurt Gödel]] at the very same meeting where Hilbert delivered his retirement speech (much to the chagrin of Hilbert); the third—the Entscheidungsproblem—had to wait until the mid-1930s.

The problem was that an answer first required a precise definition of "definite general applicable prescription", which Princeton professor [[Alonzo Church]] would come to call "[[effective calculability]]", and in 1928 no such definition existed. But over the next 6–7 years [[Emil Post]] developed his definition of a worker moving from room to room writing and erasing marks per a list of instructions (Post 1936), as did Church and his two students [[Stephen Kleene]] and [[J. B. Rosser]] by use of Church's lambda-calculus and Gödel's [[recursion theory]] (1934). Church's paper (published 15 April 1936) showed that the Entscheidungsproblem was indeed "undecidable"<ref>The narrower question posed in [[Hilbert's tenth problem]], about [[Diophantine equation]]s, remains unresolved until 1970, when the relationship between [[recursively enumerable set]]s and [[Diophantine set]]s is finally laid bare.</ref> and beat Turing to the punch by almost a year (Turing's paper submitted 28 May 1936, published January 1937). In the meantime, Emil Post submitted a brief paper in the fall of 1936, so Turing at least had priority over Post. While Church refereed Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that Church's lambda-calculus and his machines would compute the same functions.

{{blockquote|But what Church had done was something rather different, and in a certain sense weaker. ... the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church's demonstration.|Hodges p. 112}}

And Post had only proposed a definition of [[Church–Turing thesis|calculability]] and criticised Church's "definition", but had proved nothing.

===Alan Turing's a-machine===
In the spring of 1935, Turing as a young Master's student at [[King's College, Cambridge]], took on the challenge; he had been stimulated by the lectures of the logician [[M. H. A. Newman]] "and learned from them of Gödel's work and the Entscheidungsproblem ... Newman used the word 'mechanical' ... In his obituary of Turing 1955 Newman writes:

{{blockquote|To the question 'what is a "mechanical" process?' Turing returned the characteristic answer 'Something that can be done by a machine' and he embarked on the highly congenial task of analysing the general notion of a computing machine.|Gandy, p. 74}}

Gandy states that:

{{blockquote|I suppose, but do not know, that Turing, right from the start of his work, had as his goal a proof of the undecidability of the Entscheidungsproblem. He told me that the 'main idea' of the paper came to him when he was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis of computation or his realization that there was a universal machine, and so a [[Cantor's diagonal argument|diagonal argument]] to prove unsolvability.|''ibid.'', p. 76}}

While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges p.&nbsp;96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD thesis, titled "[[Systems of Logic Based on Ordinals]]", contains the following definition of "a computable function":

{{blockquote|It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.|Turing (1939) in ''The Undecidable'', p. 160}}

Alan Turing invented the "a-machine" (automatic machine) in 1936.<ref name=Hodges-2012/> Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its ''Proceedings'' (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129) It was Turing's doctoral advisor, [[Alonzo Church]], who later coined the term "Turing machine" in a review.<ref name="mitpress.mit.edu"/>  With this model, Turing was able to answer two questions in the negative:
* Does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task)? 
* Does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol?<ref name="The Undecidable' page 119"/><ref name="Turing 1937 230–265"/>
Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the [[computability|uncomputability]] of the ''[[Entscheidungsproblem]]'' ('decision problem').<ref name="ReferenceA"/>

When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes created by encryption machines called "The Enigma"; he also became involved in the design of the ACE ([[Automatic Computing Engine]]), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the [[EDVAC]] [the USA's initiative], but in his own universal machine" (Hodges p.&nbsp;318). Arguments still continue concerning the origin and nature of what has been named by Kleene (1952) [[Turing's Thesis]]. But what Turing ''did prove'' with his computational-machine model appears in his paper "[[On Computable Numbers, with an Application to the Entscheidungsproblem]]" (1937):

{{blockquote|[that] the Hilbert Entscheidungsproblem can have no solution ... I propose, therefore to show that there can be no general process for determining whether a given formula U of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.|from Turing's paper as reprinted in ''The Undecidable'', p. 145}}

Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".

===1937–1970: The "digital computer", the birth of "computer science"===
In 1937, while at Princeton working on his PhD thesis, Turing built a digital (Boolean-logic) multiplier from scratch, making his own electromechanical [[relays]] (Hodges p.&nbsp;138). "Alan's task was to embody the logical design of a Turing machine in a network of relay-operated switches ..." (Hodges p.&nbsp;138). While Turing might have been just initially curious and experimenting, quite-earnest work in the same direction was going in Germany ([[Konrad Zuse]] (1938)), and in the United States ([[Howard Aiken]]) and [[George Stibitz]] (1937); the fruits of their labors were used by both the Axis and Allied militaries in [[World War II]] (cf. Hodges p.&nbsp;298–299). In the early to mid-1950s [[Hao Wang (academic)|Hao Wang]] and [[Marvin Minsky]] reduced the Turing machine to a simpler form (a precursor to the [[Post–Turing machine]] of [[Martin Davis (mathematician)|Martin Davis]]); simultaneously European researchers were reducing the new-fangled [[electronic computer]] to a computer-like theoretical object equivalent to what was now being called a "Turing machine". In the late 1950s and early 1960s, the coincidentally parallel developments of Melzak and Lambek (1961), Minsky (1961), and Shepherdson and Sturgis (1961) carried the European work further and reduced the Turing machine to a more friendly, computer-like abstract model called the [[counter machine]]; Elgot and Robinson (1964), Hartmanis (1971), Cook and Reckhow (1973) carried this work even further with the [[register machine]] and [[random-access machine]] models—but basically all are just multi-tape Turing machines with an arithmetic-like instruction set.

===1970–present: as a model of computation===
Today, the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating questions in the [[theory of computation]]. In particular, [[computational complexity theory]] makes use of the Turing machine:

{{blockquote|Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models have obtained a dominant position in machine-based complexity theory:
<blockquote>''the off-line multitape Turing machine''..., which represents the standard model for string-oriented computation, and

the ''random access machine (RAM)'' as introduced by Cook and Reckhow ..., which models the idealised Von Neumann-style computer.</blockquote>|van Emde Boas 1990:4}}
{{blockquote|Only in the related area of analysis of algorithms this role is taken over by the RAM model.|van Emde Boas 1990:16}}