Alan Turing in 1934
|
|
|
Alan Turing in 1934
|
By 1933 Turing had already introduced himself to Russell and Whitehead's Principia Mathematica and so to the then arcane area of mathematical logic. Bertrand Russell had thought of logic as a solid foundation for mathematical truth, but many questions had since been raised about how truth could be captured by any formalism. In particular, in 1931 Goedel had shattered Russell's picture by showing the incompleteness of mathematics: the existence of true statements about numbers which could not be proved by the formal application of set rules of deduction. In 1935, Turing learnt from the lecture course of the Cambridge topologist M. H. A. Newman that a further question, posed by Hilbert, still lay open. It was the question of Decidability, the Entscheidungsproblem. Could there exist, at least in principle, a definite method or process by which it could be decided whether any given mathematical assertion was provable?
To answer such a question needed a definition of 'method' which would be not only precise but compelling. This is what Turing supplied. He analysed what could be achieved by a person performing a methodical process, and seizing on the idea of something done 'mechanically', expressed the analysis in terms of a theoretical machine able to perform certain precisely defined elementary operations on symbols on paper tape. He presented convincing arguments that the scope of such a machine was sufficient to encompass everything that would count as a 'definite method.' Daringly he included an argument based on the transitions between 'states of mind' of a human being performing a mental process.
This triple correspondence between logical instructions, the action of the mind, and a machine which could in principle be embodied in a practical physical form, was Turing's definitive contribution. Having made this novel definition of what should count as a 'definite method' --- in modern language, an algorithm --- it was not too hard to answer Hilbert's question in the negative: no such decision procedure exists.
In April 1936 he showed his result to Newman; but at the same moment the parallel conclusion of the American logician Alonzo Church became known, and Turing was robbed of the full reward for his originality. His paper, On Computable Numbers with an application to the Entscheidungsproblem, had to refer to Church's work, and was delayed until August 1936. However it was seen at the time that Turing's approach was original and different; Church relied upon an assumption internal to mathematics, rather than appealing to operations that could actually be done by real things or people in the physical world. Subsequently, the concept of the Turing machine has become the foundation of the modern theory of computation and computability.
Turing worked in isolation from the powerful school of logical theory centred on Church at Princeton University, and his work emerged as that of a complete outsider. One can only speculate, but it looks as if Turing found in the concept of the Turing machine something that would satisfy the fascination with the problem of Mind that Christopher Morcom had sparked; his total originality lay in seeing the relevance of mathematical logic to a problem originally seen as one of physics. In this paper, as in so many aspects of his life, Turing made a bridge between the logical and the physical worlds, thought and action, which crossed conventional boundaries.
His work introduced a concept of immense practical significance: the idea of the Universal Turing Machine. The concept of 'the Turing machine' is like that of 'the formula' or 'the equation'; there is an infinity of possible Turing machines, each corresponding to a different 'definite method' or algorithm. But imagine, as Turing did, each particular algorithm written out as a set of instructions in a standard form. Then the work of interpreting the instructions and carrying them out is itself a mechanical process, and so can itself be embodied in a particular Turing machine, namely the Universal Turing machine. A Universal Turing machine can be made do what any other particular Turing machine would do, by supplying it with the standard form describing that Turing machine. One machine, for all possible tasks.
It is hard now not to think of a Turing machine as a computer program, and the mechanical task of interpreting and obeying the program as what the computer itself does. Thus, the Universal Turing Machine embodies the essential principle of the computer: a single machine which can be turned to any well-defined task by being supplied with the appropriate program.
Additionally, the abstract Universal Turing Machine naturally exploits what was later seen as the 'stored program' concept essential to the modern computer: it embodies the crucial twentieth-century insight that symbols representing instructions are no different in kind from symbols representing numbers. But computers, in this modern sense, did not exist in 1936. Turing created these concepts out of his mathematical imagination. Only nine years later would electronic technology be tried and tested sufficiently to make it practical to transfer the logic of his ideas into actual engineering. In the meanwhile the idea lived only in his mind.
In common with other outstanding young scientists, Turing spent two years at Princeton University enrolled as a graduate student. He arrived in September 1936. On Computable Numbers... was published at the very end of 1936 and attracted some attention; by the time he left, the idea had come to the attention of the leading Hungarian-American mathematician John von Neumann. But Turing certainly did not shoot to fame. He worked on on algebra and number theory; on showing that his definition of computability coincided with that of Church; and on an extension of his ideas (Ordinal Logics) which provided a Ph.D. thesis.
The work on 'ordinal logics', probably his most difficult and deepest mathematical work, was an attempt to bring some kind of order to the realm of the uncomputable. This also was connected to the question of the nature of mind, as Turing's interpretation of his ideas suggested that human 'intuition' could correspond to uncomputable steps in an argument. But Turing never pursued this line of development after 1938. Instead, he was increasingly preoccupied with more immediate problems which demanded logical skills.
True to the concreteness of the Turing machine, he also spent time at Princeton making a cipher machine based on using electromagnetic relays to multiply binary numbers. Even then he saw a link from 'useless' logic to practical computation. Although not one of the political intellectuals of the 1930s, Turing followed current events and was influenced in studying ciphers by the prospect of war with Germany.
In 1944, at the invasion of Normandy that Allied control of the Atlantic allowed, Alan Turing was almost uniquely in possession of three key ideas:
Combined, these ideas provided the principle, the practical means, and the motivation for the modern computer, a single machine capable of handling any programmed task. He himself was as eager as anyone in the world to bring them together, and was spurred even more by a fourth idea: that the universal machine should be able to acquire and exhibit the faculties of the human mind. Even in 1944 he spoke to Donald Bayley of 'building a brain'.
Turing was captivated by the potential of the computer he had conceived. Although his 1936 work had shown the absolute limitations of the computable, he had become fascinated by what Turing machines could do, rather than by what they could not. He had long abandoned his youthful expectations of finding free will or free spirits through quantum mechanics. His later thought was strongly determinist and atheistic in character. And by the end of the Second World War he had turned against the tentative idea that there were steps of 'intuition' in human thought corresponding to uncomputable operations. Instead, he held that the computer would offer unlimited scope for practical progress towards embodying intelligence in an artificial form.
For the second time, he experienced being pre-empted by a parallel American publication, in this case the EDVAC plan for an electronic computer, with Von Neumann's name attached. Nonetheless, this publication when it appeared in June 1945 worked in practice to Turing's advantage, American competition stimulating the National Physical Laboratory to plan a rival project, to which he was appointed a Senior Principal Scientific Officer. Turing despised his nominal superior J. Womersley, but at least initially this applied mathematician showed a rapid appreciation of the scope of Turing's ideas, and with a eye for acronyms steered Turing's design towards formal approval in early 1946 as the Automatic Computing Engine, or ACE.
Turing's detailed scheme was drawn up in a continuation of wartime spirit: as a plan that could be effected immediately with the memory storage (cumbersome acoustic delay lines, as used in radar) that was to hand. Turing knew that superior technology would soon transform design: his emphasis was on speed in every sense, and in the exploitation of the universal machine concept. This meant, in particular, implementing arithmetical functions by programming rather than by building in electronic components, a concept different from that of the American-derived designs.
The hardware design was short-term; but his prospectus for the use of the machine was visionary. Turing projected a computer able to switch at will from numerical work to algebra, codebreaking, file handling, or chess-playing. Methods for handling subroutines included a suggestion that the machine could expand its own programs from an abbreviated form, ideas well ahead of contemporary American plans. A later talk (February 1947) depicted a national computer centre with remote terminals, and the prospect of the machine taking over more and more of its own programming work. In 1947 his Abbreviated Code Instructions marked the beginning of programming languages. But not a single component of the ACE was assembled, and Turing found himself without any influence in the engineering of the project. The lack of cooperation, very different from the wartime spirit, he found deeply frustrating.
From October 1947, the NPL allowed, or perhaps preferred, that he should spend the academic year at Cambridge. Rather than publish these fundamental principles of computing, he spent his time on new study amidst the post-war renaissance of science, not in mathematics or technology but in neurology and physiology. Out of this came a pioneering paper on what would now be called neural nets, written to amplify his earlier suggestions that a sufficiently complex mechanical system could exhibit learning ability. This was submitted to the NPL as an internal report, and never published in his lifetime. Meanwhile the NPL made no advance with the construction of the ACE, and as Turing's position fell back, other computer projects at Cambridge and Manchester took the lead.
Indeed it was Newman, who had been the first reader of On computable numbers, and in charge of the electronic breaking of the 'Fish' ciphers, who was partly responsible for this. On his 1945 appointment to the chair of pure mathematics at Manchester University, he had negotiated a large Royal Society grant for the construction of a computer. Newman strongly promoted Turing's principle of the stored-program computer, but unlike Turing, intended no personal involvement with engineering. He conveyed the basic principles to the leading radar engineer F. C. Williams, who had been attracted to Manchester, and the latter's brilliant innovation made possible a rapid success: Manchester in June 1948 had the world's first practical demonstration of Turing's computer principle.
Although losing in the race to implement a universal machine, and slow to communicate or compete in the game of scientific priority, Turing ran very competitively in a literal sense. After the war he developed his strength in cross-country running with frequent long-distance training and top-rank competition in amateur athletics. He would amaze his colleagues by running to scientific meetings, beating the travellers by public transport, and only an injury prevented his serious consideration for the British team in the 1948 Olympic Games.
The return to Cambridge helped Alan Turing form an agreeable circle of lasting friendships, particularly with Robin Gandy, who began at this period to develop under Turing's influence and would later inherit his mantle as a mathematical logician. Although never secretive about his sexuality, he now became more deliberately outspoken and exuberant, and all thoughts of comfort or conformity were now left behind. A mathematics student at King's College, Neville Johnson, became a lover.
Copyright Andrew Hodges 1995, 1999
http://artematrix.org/turing.machine/TuringMachine.htm
http://www.btinternet.com/~derek.thompson/Turing2.html
http://www.warthman.com/ex-turing.htm
http://ironphoenix.org/tril/tm/
http://sunsite.utk.edu/winners_circle/education/EDUHM01H/applet.html
http://www.turing.org.uk/turing/scrapbook/tmjava.html
Bernhard Dotzlers Turing Machine turing.zip (90k).
Turing Machine fra MIT turing-MIT.zip (237k).
Partly mirrored by artematrix.org to ensure online availability of important texts at all times. We have all experienced unfortunate downtime on servers when texts are needed the most, and apologize if this service should be considered a violation of any copywrite claims...
