This entry on Alan Turing was first submitted to the editors in 2001. It has been revised slightly for publication in 2005.
The work of the British mathematician, Alan Turing, stands as the foundation of computer science. Turing's 1936 definition of computability remains a classic paper in the elucidation of an abstract concept into a new paradigm. His 1950 argument for the possibility of Artificial Intelligence is one of the most cited in modern philosophical literature. These papers, his best known, have led his contributions to be defined as theoretical. But his work was highly practical, both in codebreaking during World War II codebreaking, and in the design of an electronic digital computer. Indeed Turing's expression for the modern computer was 'Practical Universal Computing Machine,' a reference to his 1936 'universal machine.' This combination of theory and practice meant that Turing's work fitted no conventional category of 'pure' or 'applied.' Likewise his life involved many contradictions. Detached from social and economic motivations, and perceived as an eccentric, apolitical, unworldly innocent, he was swept into a central position in history as the chief scientific figure in the Anglo-American mastery of German communications.
The matter of MindAmidst this complexity there is one constant theme: Turing's fascination with the description of mental action in scientific terms. His computational model can be seen as a twentieth-century renovation of materialist philosophy, with a claim that the discrete state machine is the appropriate level of description for mental states. However it did not begin in that way: Turing's interest in the material embodiment of mind comes first in a private letter of about 1932 (Hodges 1983, page 63) in which he alluded to the newly elucidated quantum-mechanical nature of matter, and then, influenced by Eddington, speculated on 'Will' as a physical effect in a region of the brain. It was after studying von Neumann's axioms of quantum mechanics, then Russell on the foundations of mathematics, that he learnt of logic, and so of the question that was to make his name.
The question, proposed by Hilbert, but transformed through the 1931 discovery of Kurt Gödel, was that of the decidability of mathematical propositions. Is there a definite method or procedure which can (in principle) be applied to a mathematical proposition and which will decide whether it is provable? Turing learnt of this outstanding Entscheidungsproblem from the lectures of the Cambridge mathematician Max Newman. The difficulty of the question was that it demanded an unassailable definition of the concept of method, procedure, or algorithm. This is what Turing supplied in 1936 through the definition of the Turing machine. Specifically, he modelled the action of a human being in following a definite method, either through explicit instructions, or through following a sequence of 'states of mind.'
Turing's definition came shortly after another elucidation of 'effective calculability' by the American logician Alonzo Church. Thus in a narrow sense Turing was pre-empted. Church's definition turned out to be mathematically equivalent to Turing's definition of computability. But Church (and Gödel) agreed that Turing's definition gave an intuitively compelling account of why this definition encompassed 'effectiveness'.
The Turing machine breaks down the concept of a procedure into primitive atomic steps. The exact details are somewhat arbitrary and nowadays other equivalent formulations are often used. The essential point is that the machines should have finite descriptions (as 'tables of behaviour'), but be allowed unlimited time and space for computation.
Church's thesis, that his definition of effective calculability would capture any natural notion of that concept, became the Church-Turing thesis, and opened a new area for mathematical 'decision problems.' But the work had much wider consquences: Turing's bold modelling of 'states of mind' opened a new approach to what are now called the cognitive sciences. It is often asserted that modelling the mind with a computer shows the influence of a dominant technology, but in fact Turing's work went in the reverse direction. For a striking and visionary aspect of Turing's paper was his definition of a 'universal' Turing machine, which led to the computer. A machine is universal if it can read the 'table of behaviour' of any other machine, and then execute it. This is just what a modern computer does, the instructions in programs being equivalent to 'tables of behaviour'. It was essential in Turing's description that the instructions must be stored and read like any other form of data; and this is the idea of the internally stored program. It is now hard to study Turing machines without the programmers' mind-set, and to remember that when Turing formulated them, computers did not exist.
Turing and machinesTuring's work, being based on answering Hilbert's question, modelled the human being performing a methodical computation. However the imagery of the teleprinter-like 'machine' was striking. Newman (1955), in stressing the boldness of this innovation, said that Turing embarked on 'analyzing the general notion of a computing machine.' This was criticised by Gandy (1988) as giving a false impression of Turing's approach. But Newman's account of the flavour of Turing's thought should not be entirely discounted; Turing certainly became fascinated by machines and engineered machines with his own hands in 1937-9. Church also makes it clear that the notion of a computing machine was current at this time. Church (1937) wrote (while Turing was working with him at Princeton) that Turing
... proposes as a criterion that an infinite sequence of digits 0 and 1 be "computable" that it shall be possible to devise a computing machine, occupying a finite space and with working parts of finite size, which will write down the sequence to any desired number of terms if allowed to run for a sufficiently long time. As a matter of convenience, certain further restrictions are imposed on the character of the machine, but these are of such a nature as obviously to cause no loss of generality — in particular, a human calculator, provided with pencil and paper and explicit instructions, can be regarded as a kind of Turing machine.Yet neither Turing nor Church analyzed the general concept of a computing machine with 'working parts.' Turing (1939), giving a definitive statement of the Church-Turing thesis, used the expression 'purely mechanical' without further analysis. Only in 1948 did he give some more discussion.
This topic has recently been made controversial by B. J. Copeland, who holds that the Church-Turing thesis is widely misunderstood, because it was never intended to apply to machines. Copeland overlooks Church's characterisation of computability, as quoted above, which assumes that all finitely defined machines fall within the scope of computability. To support his claim, Copeland points to the 'oracle' defined by Turing (1939), which supplies an uncomputable function, and holds that it gives a broader characterization of computation. But the whole point of Turing's oracle is that it facilitates the mathematical exploration of the uncomputable. The oracle, as Turing emphasised, cannot be a machine. It performs non-mechanical steps. His 'oracle-machines,' defined so as to call upon 'oracles', are not purely mechanical.
Turing's oracle is related to Gödel's theorem, which seems to show that the human mind can do more than a mechanical system, when it sees the truth of formally unprovable assertions. Turing described this as mental 'intuition'. The oracle, as Newman (1955) interpreted it, can be taken as a model of 'intuition.' But Turing left open the question of how intuition was to be considered as actually embodied. He was not at this stage committed to the computability of all mental acts, as came to be his position after 1945. His 1936 work had considered the mind only when applied to a definite method or procedure. Turing had to resolve this question before embarking on his Artificial Intelligence program.
Copeland has gone even further and has described Turing's 'oracle' as heralding a new revolution in computer science, illustrating 'what Turing imagined' by sketching an oracle supposed to operate by measuring a physical quantity to infinite precision. But Turing's oracle models what machines cannot do, and the question for him was, and always remained, whether machines can do as much as minds. He did not suggest the opposite idea, stated in Copeland (1997), that 'among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform.'
The historical question of what Turing thought must naturally be distinguished from scientific truth. It is a serious (and unanswered) question as to whether actual physical objects do necessarily give rise to computable effects. Nowadays we demand a closer analysis of 'finite size.' Gandy (1980) arrived at conclusions that generally support Church's assumptions: the limitations of computability follow from quite general assumptions about the construction of a machine. But if the constraint of finiteness is interpreted so as to allow a 'machine' with infinitely many sub-components built on smaller and smaller scales, or working faster and faster without limit, then it is easy to show that Turing's computability can be surpassed in a finite time. In any imaginary universe such a construction might be possible; such examples may therefore be said to show that the Church-Turing thesis has a physical content.
'Effective' means 'doing' (as opposed to postulating or imagining), thus depending on some concept of realistic action, and hence on physical law. Quantum computation has already shown that the classical picture of 'doing' is incomplete. The nature of quantum mechanics, still mysterious in its non-local and 'reduction' properties, means that there may yet be more to be found out, and in recent years the work of Penrose (1989, 1994), who like Turing focuses on the mind and brain, has drawn new attention to this question.
Turing's practical machineryIt is perhaps surprising that Turing himself did not in this 1936-39 period say anything about the physics of the 'machine' concept, in view of his interest in quantum mechanics. He might have done so but for the war. War disrupted Turing's investigation of the uncomputable, along with his conversations with Wittgenstein on the foundations of mathematics (Diamond 1976) — never extended, as many now wish they had been, into the philosophy of mind. But war work gave Turing an intimate acquaintance with the power of algorithms and with advanced technology for implementing them. For Turing became the chief scientific figure at Bletchley Park, the British cryptanalysis centre and a key location in modern history.
Turing had anticipated this development in 1936. He had applied his ideas to 'the most general code or cipher', and in fact one of the machines he made himself was to implement a particular cipher system (Hodges 1983, page 138). This, together with his Cambridge connection with influential figures such as J. M. Keynes, may explain why he was the first mathematician brought into the codebreaking department .
Turing transformed the Government Code and Cypher School with the power of scientific method. Turing's logic and information theory, applied with advanced engineering, achieved astounding feats, with particular effect in decrypting the U-Boat Enigma signals for which he was personally responsible. By 1944 the power reliability and speed of electronic technology showed Turing that his universal machine could be implemented. The plethora of advanced algorithms employed in cryptanalysis also supplied ample practical motivation.
In 1945, Turing was appointed to the National Physical Laboratory, with the commission of designing an electronic computer. Turing's plans soon emerged as the ACE proposal (Turing 1946). Again, Turing was pre-empted by work in the United State, for the EDVAC report of 1945 had preceded his own publication. Turing's plans were however independent, more detailed, and more far-reaching. Furthermore, a recent survey (Davis 2000) suggests that von Neumann needed his knowledge of Turing's work when shaping the EDVAC. As a point of interest in the history of science, none of the mathematical leaders — Turing, von Neumann, Newman — clearly defined the stored program concept or its debt to symbolic logic in treating instructions as data. Turing never published the book on the theory and practice of computation that he might have done, and so neglected his own good claim to be the inventor of the computer.
It is an unobvious fact, long resisted, now familiar, that more complex algorithms do not need more complex machines, only sufficient storage space and processor speed. This was Turing's central idea. In a world familiar with the power of a universal machine we can better appreciate the remark in (Turing 1946) that '...every known process has got to be translated into instruction table form at some stage...' Turing emphasised that arithmetical calculations were only one aspect of the computer's role — partly the influence of non-numerical Bletchley Park work, but more deeply, his base in symbolic logic. His hardware design was probably impractical in detail, but he far surpassed von Neumann in seeing the significance of software, and that this would use the computer itself, a fact now familiar in compilers and editors:
The work of constructing instruction tables should be very fascinating. There need be no real danger of it ever becoming a drudge, for any processes that are quite mechanical may be turned over to the machine itself.
Turing's insight into programming by modifying instructions led to the idea of simulating learning, training and evolution by an extension of these ideas. As he put it, human intelligence required something other than 'discipline', namely 'initiative.' By 1945 Turing had convinced himself that human faculties of an apparently non-mechanical nature did not require explanation in terms of the uncomputable. Turing was well aware of the paradox of expecting intelligence from a machine capable only of obeying orders. But he believed that with sufficient complexity machines need not appear 'mechanical' as in common parlance.
A crucial point is that Turing had by this stage formulated an argument from human 'mistakes' to explain why Gödel's theorem did not show the existence of an uncomputable human intuition; indeed a sentence in (Turing 1946) shows the early influence of this view in his project for Artificial Intelligence (Hodges 1997). He now expected self-modifying machines to exhibit the apparently 'non-mechanical' aspects of mental behaviour.
With this as his strategic goal, Turing sketched networks of logical elements, to be organised into function by 'training' or by an analogy with evolution. Although he did not develop his specific schemes, he anticipated the 'connectionist' approach to Artificial Intelligence. Nowadays the term 'non-algorithmic' is confusingly used for systems where the program is implicitly developed, rather than explicitly written by a programmer. Turing was however quite clear that such operations still lie within the realm of the computable. All these developments were sketched in (Turing 1948). He also in this paper gave his only systematic account of the concept of 'machine'. In doing so he introduced the possibility of random elements into the Turing machine model, but he made no reference to a need for uncomputable elements in randomness. Indeed he indicated that pseudo-random elements, clearly computable, would suffice.
Turing's Intelligent MachineryDisappointed with the lack of progress at the NPL, Turing moved in 1948 to Manchester. There Michael Polanyi stimulated Turing to write for a more general audience on the question of whether machines could in principle rival the human mind. The idea in (Turing 1950) was to cut through traditional philosophical assumptions about Mind, by the thought-experiment now known as the Turing Test, but which he called 'the imitation game'. A human and a programmed computer compete to convince an impartial judge that they are human, by textual messages alone. Turing's position was that thought or intelligence, unlike other human faculties, is capable of being fairly tested through a communication channel like a teleprinter.
Critics have raised questions about non-verbal communication, cultural assumptions, animal intelligence, and other issues. Turing's principal defence against all such arguments was that we can only judge the intelligence of other humans by making such external comparisons, and that is unfair to impose more stringent criteria on a computer. But it may be held that, when addressing human consciousness with moral seriousness, there is something inadequate about a definition of intelligence that depends upon deceit. Turing also confused the issue by introducing the 'imitation game' with a poor analogy: a parlour game in which a man has to pretend to be a woman under the same conditions of remote questioning. In such a game imitation proves nothing, so the analogy is misleading and has confused many readers. However, Turing's drama has the merit of expressing the full-bloodedness of his program. His wit has attracted lasting popular interest. Turing's references to gender have also fascinated cultural critics, who speculate widely over biographical and social issues in their commentaries (Lassègue 1998).
A dryer but stronger feature of (Turing 1950) lies in Turing's setting out of the level of description of the discrete state machine, and his emphasis on explaining computability and the universal machine. Critics who point out that the brain is not structured like a computer miss his essential point that any algorithm can be implemented on the computer. This applies to explicit algorithms, and to those arrived at by processes as in neural networks; Turing described both. Another strength of Turing's paper lies in his advocating both approaches, never seeing programming as standing in opposition to the modelling of intelligence by learning and adaptation. Artificial Intelligence research has tended towards division between the two camps dominated by expert systems and neural networks, but recently hybrid approaches have appeared. Thus Turing's ideas still have force. Also futuristic was Turing's prophecy that by the end of the century 'one will be able to speak of machines thinking without expecting to be contradicted.'
It is probably true to say that this prophecy was not fulfilled in 2000, but Turing was prepared to take this risk:
The popular view that scientists proceed inexorably from well-established fact to well-established fact, never being influenced by any unproved conjecture, is quite mistaken. Provided it is made clear which are proved facts and which are conjectures, no harm can result. Conjectures are of great importance since they suggest useful lines of research.Turing's conjecture was that the brain's action is computable. If this is true, then it is hard to refute his argument that given sufficient storage space, a computer can perform the function of the mind. Turing emphasised this argument by putting a figure on the storage capacity of the brain. But he still did not directly address that underlying question of whether physical objects necessarily have computable behaviour. Artificial Intelligence research has generally accepted without question the assumption that they do. But Penrose, linking the still ill-understood 'reduction' in quantum mechanics with Gödel's theorem, has thrown the spotlight back on the problems that Turing himself found most perplexing.
Turing's unfinished workTuring (1951) did refer to the problem of quantum mechanics when giving a popular radio talk. As Copeland (1999) has noted, he gave a more qualified assertion of the computability of mental action than in Turing (1950). But this was not because of believing oracles to reside in the brain; it was because of quantum unpredictability. . But this was not because of believing oracles to reside in the brain; it was because of quantum unpredictability. Harking back to his schooldays reading, he referred to Eddington in connection with the mechanism of the brain. This brief allusion may explain why Turing thereafter gave fresh attention to quantum theory. His friend, student and colleague Gandy (1954) wrote in a letter to Newman of Turing's ideas, in particular of his attention to the question of the 'reduction' or 'measurement' process and the 'Turing paradox' that according to standard theory, continuous observation should prevent a system from evolving.
These ideas were not developed into publication. They were curtailed by his suicide in 1954. One of many ironies of Turing's life, lived for science, was that he suffered in 1952-53 a 'scientific' treatment by oestrogen supposed to negate his homosexuality. This treatment was the alternative to prison after his arrest in February 1952. His openness and defiance did not command the admiration of authority, and there was at least one further crisis when he found himself under watch. One may regret that he did not write more of his own sense of liberty and will. Indeed it is remarkable that he, so original and unconventional, should champion the possibility of programming the mind. But he left few hints as to the personal dilemmas encountered on the roads to freedom. He was of course constrained by intense state secrecy, his brain the repository of the most highly guarded Anglo-American secrets.
Besides his new enquiries in physics, he had a large body of incomplete theory and computational experiment in mathematical biology. This, neglected until the 1970s, is now the foundation of a lively area of non-linear dynamics. Turing described his theory as intended to oppose 'The Argument from Design.' It was a theme parallel to (and through his interest in brain function connected with) his quest for a new materialism of mind. He had not exhausted his ideas, and their impact has not yet been fully absorbed.
Bibliography:Church A. (1937) Review of Turing 1936-7, Journal of Symbolic Logic, 2, 42-43.
Copeland. B. J. (1997), The Church-Turing thesis, in E. N. Zalta (ed.), Stanford Encyclopaedia of Philosophy, http://plato.stanford.edu
Copeland B. J. (1999) A lecture and two radio broadcasts on machine intelligence by Alan Turing, in K. Furukawa, D. Michie. and S. Muggleton (eds.), Machine Intelligence 15, 445-476 (Oxford: Oxford University Press)
Davis, M. (2000) The universal computer (New York: Norton)
Diamond, C. (ed.) (1976) Wittgenstein's lectures on the foundations of mathematics, Cambridge 1939, (Hassocks, UK: Harvester Press)
Gandy, R. O. (1954) letter to M. H. A. Newman. Included in the Mathematical Logic volume of the Collected Works.
Gandy, R. O. (1980) Principles of Mechanisms, in The Kleene Symposium, eds. J. Barwise, H. J. Keisler and K. Kunen (Amsterdam: North-Holland)
Gandy R. O. (1988) The confluence of ideas in 1936, in (Herken 1988)
Herken R. (ed.) (1988) The universal Turing machine: a half-century survey (Berlin: Kammerer und Unverzagt, Oxford: Oxford University Press)
Hodges, A. (1983) Alan Turing: the enigma (London: Burnett, New York: Simon & Schuster; new editions London, Vintage 1992, New York: Walker 2000).
Hodges, A. (1997) Turing, a natural philosopher (London: Phoenix; also New York: Routledge, 1999). Included in: The Great Philosophers (eds. R. Monk and F. Raphael, London: Weidenfeld and Nicolson 2000)
Lassègue, J. (1998) Turing (Paris: Les Belles Lettres)
Newman, M. H. A. (1955), Alan M. Turing, Biographical Memoirs of Fellows of the Royal Society, 1, 253-263
Penrose, R. (1989) The emperor's new mind (Oxford, New York: Oxford University Press)
Penrose, R. (1994) Shadows of the mind (Oxford, New York: Oxford University Press)
Turing, A. M.,The Collected Works of A. M. Turing: Pure Mathematics, ed. J. L. Britton, (1993); Mechanical Intelligence, ed. D. C. Ince, (1993); Morphogenesis, ed. P.T. Saunders, (1993); Mathematical Logic, eds. R. O. Gandy and C. E. M. Yates, (2001). (Amsterdam: North-Holland)
Turing, A. M., ed. B. J. Copeland (2004) The Essential Turing (Oxford: Oxford University Press)
Turing A. M. (1936-7), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, ser. 2, 42, 230-265
Turing A. M. (1939), Systems of Logic defined by Ordinals, Proceedings of the London Mathematical Society, ser. 2, 45, 161-228
Turing, A. M. (1946), Proposed electronic calculator, unpublished report for National Physical Laboratory; published in A. M. Turing's ACE Report of 1946 and other papers (eds. B. E. Carpenter and R. W. Doran, Cambridge, Mass.: MIT Press, 1986)
Turing A. M. (1948), Intelligent machinery, report for National Physical Laboratory; script available at http://www.turingarchive.org; published (ed. D Michie) in Machine Intelligence 5, 3-23 (1969).
Turing A. M. (1950), Computing machinery and intelligence, Mind 59, 433-460
Turing A. M. (1951) BBC Radio talk, script available at http://www.turingarchive.org; also in Copeland (1999)