Turing : entry for the Routledge Encyclopaedia of The Philosophy of Science (2002)

by Andrew Hodges

NOTE

ALAN TURING, British mathematician, was born June 23, 1912 and died June 7, 1954. His work 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 World War II codebreaking, and in the design of a 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 Mind

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 became the Church-Turing thesis, and opened a new area for mathematical 'decision problems.' But the work had much wider consequences: 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 prograns 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 machines

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

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. His claim centres on the belief that Turing defined his oracle to be the component of a kind of machine (Copeland 1999b). 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 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.' Turing did not raise 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.

The question of Turing's concept of 'machine' has also recently been related to the future of technology. Copeland and Proudfoot (1999a) have claimed that 'the search is on' to find a physical oracle leading to a new revolution in computer science. They illustrate their vision of 'what Turing imagined' by drawing an oracle supposed to operate by measuring a physical quantity to infinite precision. They invoke the 'real Turing' in support of this project (Copeland and Proudfoot 1998). But this prospectus has no place whatever in Turing's thought. 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,' and there have been many approaches to analysing 'the notion of a computing machine' in physical terms. 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. A different approach is illustrated by (Davies 2001), suggesting the 'effective' calculation of an uncomputable number by a 'machine' with infinitely many sub-components built on smaller and smaller scales without limit. In any imaginary universe such a construction might be possible; Davies and other writers comment that such examples therefore 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 Roger Penrose (1989, 1994, 1996), who like Turing focusses on the mind and brain, has drawn new attention to this question.

Turing's practical machinery

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 American work, 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.

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 Machinery

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 unfinished work

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:

(1) Turing's Works

The Turing Digital Archive is available at http://www.turingarchive.org and contains many original typescripts and letters of Turing.

(2) Surveys of Turing's work

Davis, M. (2000) The universal computer (New York: Norton)

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). Further material is on http://www.turing.org.uk

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)

Newman, M. H. A. (1955), Alan M. Turing, Biographical memoirs of the Royal Society.

(3) Other References

Copeland. B. J. (1997), The Church-Turing thesis, in E. N. Zalta (ed.), Stanford Encyclopaedia of Philosophy, http://plato.stanford.edu

Copeland B. J. and Proudfoot D. (1998), Enigma variations, (London: Times Literary Supplement, 3 July 1998.

Copeland B. J. and Proudfoot D. (1999a) Alan Turing's forgotten ideas in computer science, Scientific American, April 1999.

Copeland B. J. (1999b), A lecture and two radio broadcasts on machine intelligence by Alan Turing, in K. Furukawa, D. Michie. and S. Muggleton (eds.), Machine Intelligence 15, (Oxford: Oxford University Press, 1999)

Davies, E. B (2001) Building infinite machines, to appear in Brit. J. Phil. Science.

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)

Lassègue, J. (1998) Turing (Paris: Les Belles Lettres)

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)

Penrose, R. (1996) Beyond the doubting of a shadow, Psyche electronic journal, http://psyche.csse.monash.edu.au/v2/psyche-2-23-penrose.html

Turing A. M. (1936-7), On computable numbers, with an application to the Entscheidungsproblem, Proc. London Maths. Soc., ser. 2, 42, (230-265) also in M. Davis, (ed.) The Undecidable (New York: Raven, 1965)

Turing A. M. (1939), Systems of Logic defined by Ordinals, Proc. Lond. Math. Soc., ser. 2, 45, 161-228; also in M. Davis (ed.) The Undecidable (New York: Raven, 1965). This was also Turing's 1938 Ph.D. thesis, Princeton University.

Turing, A. M. (1946), Proposed electronic ealculator, 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, unpublished report for National Physical Laboratory; published (ed. D Michie) in Machine Intelligence 7 (1969).

Turing A. M. (1950), Computing machinery and intelligence, Mind 49, (433-460)

Turing A. M. (1951) BBC Radio talk, script available at http://www.turingarchive.org; also in Copeland (1999b)