Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child’s arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent.

  An ‘infinity of symbols’, he wished to argue, did not correspond to anything in reality. It might be argued that there was an infinity of symbols, in that

  an Arabic numeral such as 17 or 999999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, however, attempts to have an enumerable infinity of symbols).

  But he disposed of this objection with the observation that

  The differences from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at one glance. This is in accordance with experience. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same.

  Accordingly, he felt justified in restricting a machine to a finite repertoire of symbols. Next came a most important idea:

  The behaviour of the computer at any moment is determined by the symbols which he is observing, and his ‘state of mind’ at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need to be taken into account is finite. The reasons for this are the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be ‘arbitrarily close’ and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.

  The word ‘computer’ here meant only what that word meant in 1936: a person doing calculations. Elsewhere in the paper he appealed to the idea that ‘the human memory is necessarily limited,’ but this was as far as he went in a discussion of the nature of the human mind. It was a bold act of imagination, a brave suggestion that ‘states of mind’ could be counted, on which to base his argument. It was especially noteworthy because in quantum mechanics, physical states could be ‘arbitrarily close’. He continued with his discussion of the human computer:

  Let us imagine the operations performed by the computer to be split up into ‘simple operations’ which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change in the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and the state of mind of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to the squares whose symbols may be altered in this way is the same as in regard to the observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always ‘observed’ squares.

  Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square.

  In connection with ‘immediate recognisability’, it may be thought that there are other kinds of square which are immediately recognisable. In particular, squares marked by special symbols might be taken as immediately recognisable. Now if these squares are marked only by single symbols there can be only a finite number of them, and we should not upset our theory by adjoining these marked squares to the observed squares. If, on the other hand, they are marked by a sequence of symbols, we cannot regard the process of recognition as a simple process. This is a fundamental point and should be illustrated. In most mathematical papers the equations and theorems are numbered. Normally the numbers do not go beyond (say) 1000. It is, therefore, possible to recognise a theorem at a glance by its number. But if the paper was very long, we might reach Theorem 157767733443477; then, further on in the paper, we might find ‘… hence (applying Theorem 157767734443477) we have…’. In order to make sure which was the relevant theorem we should have to compare the two numbers figure by figure, possibly ticking the figures off in pencil to make sure of their not being counted twice. If in spite of this it is still thought that there are other ‘immediately recognisable’ squares, it does not upset my contention so long as these squares can be found by some process of which my type of machine is capable.…

  The simple operations must therefore include:

  (a) Changes of the symbol on one of the observed squares

  (b) Changes of one of the squares observed to another square within L squares of one the previously observed squares.

  It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following:

  (A) A possible change (a) of symbol together with a possible change of state of mind;

  (B) A possible change (b) of observed squares, together with a possible change of state of mind.

  The operation actually performed is determined, as has been suggested [above] by the state of mind of the computer and the observed symbols. In particular, they determine the state of mind of the computer after the operation is carried out.

  ‘We may now construct a machine,’ Alan wrote, ‘to do the work of this computer.’ The drift of his argument, indeed, was obvious, with each ‘state of mind’ of the human computer being represented by a configuration of the corresponding machine.

  These ‘states of mind’ being a weak point of the argument, he added an alternative justification of the idea that his machines could perform any ‘definite method’ which did not need them:

  We suppose [still] that the computation is carried out on a tape; but we avoid introducing the ‘state of mind’ by considering a more physical and definite counterpart of it. It is always possible for the computer to break off from his work, to go away and forget all about it, and later to come back and go on with it. If he does this he must leave a note of instructions (written in some standard form) explaining how the work is to be continued. This note is the counterpart of the ‘state of mind’. We will suppose that the computer works in such a desultory manner that he never does more than one step at a sitting. The note of instructions must enable him to carry out one step and write the next note. Thus the state of progress of the computation at any stage is completely determined by the note of instructions and the symbols on the tape…

  But these arguments were quite different. Indeed, they were complementary. The first put the spotlight upon the range of thought within the individual – the number of ‘states of mind’. The second conceived of the individual as a mindless executor of given directives. Both approached the contradiction of free will and determinism, but one from the side of internal will, the other from that of external constraints. These approaches were not explored in the paper, but left as seeds for future growth.*

  Alan had been stimulated by Hilbert’s decision problem, or the Entscheidungs problem as it was in German. He had not only answered it, but had done much more. Indeed, he would entitle his p
aper ‘On Computable Numbers, with an application to the Entscheidungs problem.’ It was as though Newman’s lectures had tapped some stream of enquiry which had been flowing all the time and which found in this question an opportunity to emerge. He had done something, for he had resolved a central question about mathematics, and had done so by crashing in as an unknown and unsophisticated outsider. But it was not only a matter of abstract mathematics, not only a play of symbols, for it involved thinking about what people did in the physical world. It was not exactly science, in the sense of making observations and predictions. All he had done was to set up a new model, a new framework. It was a play of imagination like that of Einstein or von Neumann, doubting the axioms rather than measuring effects. Even his model was not really new, for there were plenty of ideas, even in Natural Wonders, about the brain as a machine, a telephone exchange or an office system. What he had done was to combine such a naive mechanistic picture of the mind with the precise logic of pure mathematics. His machines – soon to be called Turing machines – offered a bridge, a connection between abstract symbols, and the physical world. Indeed, his imagery was, for Cambridge, almost shockingly industrial.

  Obviously there was a connection between the Turing machine and his earlier concern with the problem of Laplacian determinism. The relationship was indirect. For one thing, it might be argued that the ‘spirit’ he had thought about was not the ‘mind’ that performed intellectual tasks. For another, the description of the Turing machines had nothing to do with physics. Nevertheless, he had gone out of his way to set down a thesis of ‘finitely many mental states’, a thesis implying a material basis to the mind, rather than stick to the safer ‘instruction note’ argument. And it would appear that by 1936 he had indeed ceased to believe in the ideas that he had described to Mrs Morcom as ‘helpful’ as late as 1933 – ideas of spiritual survival and spiritual communication. He would soon emerge as a forceful exponent of the materialist view and identify himself as an atheist. Christopher Morcom had died a second death, and Computable Numbers marked his passing.

  Beneath the change there lay a deeper consistency and constancy. He had worried about how to reconcile ideas of will and spirit with the scientific description of matter, precisely because he felt so keenly the power of the materialist view, and yet also the miracle of individual mind. The puzzle remained the same, but now he was approaching it from the other side. Instead of trying to defeat determinism, he would try to account for the appearances of freedom. There had to be a reason for it. Christopher had diverted him from the outlook of Natural Wonders, but now he had returned.

  There was another point of constancy, in that he was still looking for some definite, down-to-earth resolution of the paradox of determinism and free will, not a wordy philosophical one. Earlier, in this search, he had favoured Eddington’s idea about the atoms in the brain. He would remain very interested in quantum mechanics and its interpretation, a problem that von Neumann had by no means resolved, but the Jabberwocky would not be his problem. For now he had found his own métier, by formulating a new way of thinking about the world. In principle, quantum physics might include everything, but in practice to say anything about the world would require many different levels of description. The Darwinian ‘determinism’ of natural selection depended upon the ‘random’ mutation of individual genes; the determinism of chemistry was expressed in a framework where the motion of individual molecules was ‘random’. The Central Limit Theorem was an example of how order could arise out of the most general kind of disorder. A cipher system would be an example of how disorder could arise by means of a determinate system. Science, as Eddington took care to observe, recognised many different determinisms, many different freedoms. The point was that in the Turing machine, Alan had created his own determinism of the automatic machine, operating within the logical framework he held to be appropriate to the discussion of the mind.

  He had worked entirely on his own, not once discussing the construction of his ‘machines’ with Newman. He had a few words with Richard Braithwaite at the High Table one day on the subject of Gödel’s theorem. Another time he put a question about the Cantor method to Alister Watson, a young King’s Fellow (a communist, as it happened) who had turned from mathematics to philosophy. He described his ideas to David Champernowne, who got the gist of the universal machine, and said rather mockingly that it would require the Albert Hall to house its construction. This was fair comment on Alan’s design in Computable Numbers, for if he had any thoughts of making it a practical proposition they did not show in the paper.38 Just south of the Albert Hall, in the Science Museum, were lurking the remains of Babbage’s ‘Analytical Engine’, a projected universal machine of a hundred years before. Quite probably Alan had seen them, and yet if so, they had no detectable influence upon his ideas or language. His ‘machine’ had no obvious model in anything that existed in 1936, except in general terms of the new electrical industries, with their teleprinters, television ‘scanning’, and automatic telephone exchange connections. It was his own invention.

  A long paper, full of ideas, with a great deal of technical work and evidence of more left unpublished, Computable Numbers must have dominated Alan’s life from spring 1935 through the following year. In the middle of April 1936, returning from Easter at Guildford, he called on Newman and gave him the draft typescript.

  There were many questions to be asked about the discoveries that Gödel and he had made, and what they meant for the description of mind. There was a profound ambiguity to this final settlement of Hilbert’s programme, though it certainly ended the hope of a too naive rationalism, that of solving every problem by a given calculus. To some, including Gödel himself, the failure to prove consistency and completeness would indicate a new demonstration of the superiority of mind to mechanism. But on the other hand, the Turing machine opened the door to a new branch of deterministic science. It was a model in which the most complex procedures could be built out of the elementary bricks of states and positions, reading and writing. It suggested a wonderful mathematical game, that of expressing any ‘definite method’ whatever in a standard form.

  Alan had proved that there was no ‘miraculous machine’ that could solve all mathematical problems, but in the process he had discovered something almost equally miraculous, the idea of a universal machine that could take over the work of any machine. And he had argued that anything performed by a human computer could be done by a machine. So there could be a single machine which, by reading the descriptions of other machines placed upon its ‘tape’, could perform the equivalent of human mental activity. A single machine, to replace the human computer! An electric brain!

  The death of George V, meanwhile, marked a transition from protest at the old order to fear of what the new might hold in store. Germany had already defeated the new Enlightenment; had already injected iron into the idealist soul. March 1936 saw the re-occupation of the Rhineland: it meant that the future lay with militarism. Who then could have seen the connection with the fate of an obscure Cambridge mathematician? Yet connection there was. For one day Hitler was to lose the Rhineland, and it would be then, and only then, that the universal machine could emerge into the world of practical action. The idea had come out of Alan Turing’s private loss. But between the idea and its embodiment had to come the sacrifice of millions. Nor would the sacrifices end with Hitler; there was no solution to the world’s Entscheidungs problem.

  * John Bennett was a boy in the house, who himself died later in 1930 on a lone winter trek across the Rockies.

  * For comparison: a skilled worker earned about £160 per annum; unemployment benefit ran at £40 per annum for a single man.

  * W. Sierpinski, a prominent twentieth century Polish pure mathematician.

  * ‘Mays’ were the semi-official second year examinations.

  *Joynson Hicks, the reactionary Home Secretary.

  * This gave him a tenuous link with his mother, who had shares in a Bethnal Green housing associatio
n. Alan’s reaction was approval that they planned the flats for the families who needed them rather than vice versa.

  †‘Regarding Aunt J’s funeral’, Alan wrote in January 1934 to his mother, ‘I am not v. keen on going, and I think it would be consummate hypocrisy if I did. But if you think anyone will be the better for my attending I will see whether it can be managed.’

  * Alan also considered Ibsen’s plays ‘remarkably good’.

  * The analogy is not intended to be exact; Hilbert space and quantum mechanical ‘states’ differ in an essential way from anything in ordinary experience.

  * The word ‘group’, as used in mathematics, has a technical meaning quite distinct from its use in ordinary language. It refers to the idea of a set of operations, but only when that set of operations meets certain precise conditions. These may be illustrated by considering the rotations of a sphere. If A, B and C are three different rotations, then one can see that:

  (i) there exists a rotation which exactly reverses the effect of A.

  (ii) there exists a rotation which has exactly the same effect as performing A, and then B.

  Let this rotation be called ‘AB’. Then

  (iii) AB, followed by C, has the same effect as A, followed by BC.

  These are essentially the conditions required for the rotations to form a ‘group’. Abstract group theory then arose by taking these conditions, representing them appropriately with symbols, and then abandoning the original concrete embodiment. The resulting theory might profitably be applied to rotations, as indeed it was, in quantum mechanics. It could also apply to the apparently unrelated field of ciphering. (Ciphers enjoy the ‘group’ properties: a cipher must have a well-defined decipherment operation which reverses it, and if two ciphering operations are performed in succession, the result is another cipher.) But by the 1930s it was accepted that ‘groups’ could be explored in the abstract, without any concrete representation or application in mind.