Editing Turing machine (section)

===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".