Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  * There is nothing ‘real’ about ‘real numbers’. The term is a historical accident, arising from the equally misleading terms ‘complex numbers’ and ‘imaginary numbers’. The reader not familiar with these expressions could think of ‘real numbers’ as ‘lengths defined with a hypothetical infinite precision.’

  * Alan acquired a copy, soon heavily annotated, of Hilbert and Courant’s Methoden der Mathematischen Physik in July 1933.

  * The author of one of the books which described the Central Limit Theorem.

  * A simple example of a topological problem is that of the ‘four colour theorem’. This states that a map such as one of the English counties can always be coloured with just four colours, in such a way that no two adjoining counties share the same colour. Alan himself took some interest in this problem, but it was to remain an unproved assertion until 1976.

  * A recent development in pure mathematics, extending and generalising the idea of ‘periodicity’.

  * The arguments also implied two rather different interpretations of the machine ‘configuration’. From the first point of view, it was natural to think of the configuration as the machine’s internal state – something to be inferred from its different responses to different stimuli, rather as in behaviourist psychology. From the second point of view, however, it was natural to think of the configuration as a written instruction, and the table as a list of instructions, telling the machine what to do. The machine could be thought of as obeying one instruction, and then moving to another instruction. The universal machine could then be pictured as reading and decoding the instructions placed upon the tape. Alan Turing himself did not stick to his original abstract term ‘configuration’, but later described machines quite freely in terms of ‘states’ and ‘instructions’, according to the interpretation he had in mind. This free usage will accordingly be employed in what follows.

  3

  New Men

  I hear it was charged against me that I sought to destroy institutions,

  But really I am neither for nor against institutions,

  (What indeed have I in common with them? or what with the

  destruction of them?)

  Only I will establish in the Mannahatta and in every city of these

  States inland and seaboard,

  And in the fields and woods, and above every keel little or large that

  dents the water,

  Without edifices or rules or trustees or any argument,

  The institution of the dear love of comrades.

  Almost on the same day that Alan announced his discovery to Newman, someone else completed a demonstration that the Hilbert Entscheidungs-problem was unsolvable. It was at Princeton, where the American logician Alonzo Church had finished his argument for publication1 on 15 April 1936. Church’s essential idea, showing the existence of an ‘unsolvable problem’, had been announced a year earlier, but only at this point did he put it exactly in the form of answering Hilbert’s question.

  A new idea had found its way into two human minds simultaneously and independently. At first, this was not known at Cambridge, and Alan wrote to his mother on 4 May:

  I saw Mr Newman four or five days after I came up. He is very busy with other things just at present and says he will not be able to give his whole attention to my theory for some week or so yet. However he examined my note for C.R.* and approved it after some alterations. I also got it vetted by a French expert, and sent it off. I have had no acknowledgement of it, which is rather annoying. I don’t think the full text will be ready for a fortnight or more yet. It will probably be about fifty pages. It is rather difficult to decide what to put into the paper now and what to leave over till a later occasion.

  When Newman did read it in mid-May, he could hardly believe that so simple and direct an idea as the Turing machine would answer the Hilbert problem over which many had been labouring for the five years since Gödel had disposed of the other Hilbert questions. His first impression was that it must be wrong, for some more sophisticated machine would be able to solve the ‘unsolvable problem’, and that one would then continue on and on. But finally he satisfied himself that no finitely defined machine could possibly do more than was allowed by the Turing construction.

  Then Church’s paper arrived from across the Atlantic. It pre-empted the result, and threw into jeopardy the publication of Alan’s work, scientific papers not being allowed to repeat or copy one another. But what Church had done was something rather different, and in a certain sense weaker. He had developed a formalism called the ‘lambda-calculus’* and, with the logician Stephen Kleene, had discovered that this formalism could be used to translate all the formulae of arithmetic into a standard form. In this form, proving theorems was a matter of converting one string of symbols of the lambda-calculus into another string, according to certain rather simple rules. Church had then been able to show that the problem of deciding whether one string could be converted into another string was unsolvable, in the sense that there existed no formula of the lambda-calculus which could do it. Having found one such unsolvable problem, it had become possible to show that the exact question that Hilbert had posed must also be unsolvable. But it was not obvious that ‘a formula of the lambda-calculus’ corresponded to the notion of a ‘definite method’. Church gave verbal arguments for the assertion that any ‘effective’ method of calculation could be represented by a formula of the lambda-calculus. But the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church’s demonstration.

  So Alan was able to submit his paper on 28 May 1936 to the London Mathematical Society for publication in its Proceedings, and Newman wrote to Church:

  31 May 1936

  Dear Professor Church,

  An offprint which you kindly sent me recently of your paper in which you define ‘calculable numbers’, and shew that the Entscheidungs problem for Hilbert logic is insoluble, had a rather painful interest for a young man, A.M. Turing, here, who was just about to send in for publication a paper in which he had used a definition of ‘Computable numbers’ for the same purpose. His treatment – which consists in describing a machine which will grind out any computable sequence – is rather different from yours, but seems to be of great merit, and I think it of great importance that he should come and work with you next year if that is at all possible. He is sending you the typescript of his paper for your criticisms.

  If you find that it is right, and of merit, I should be greatly obliged if you could help Turing to get to Princeton next year, by writing to the Vice-Chancellor, Clare College, Cambridge, in support of Turing’s application for the Procter Fellowship. If he fails to win this he can still just manage to come, I think, since he is a Fellow of King’s College, but it would be a very tight fit. Is there any possibility of a small supplementary grant at the Princeton end? … I should mention that Turing’s work is entirely independent: he has been working without any supervision or criticism from anyone. This makes it all the more important that he should come into contact as soon as possible with the leading workers on this line, so that he should not develop into a confirmed solitary.

  There was no one in England who could referee the paper for publication in the London Mathematical Society Proceedings, and in fact Church himself was the only person who could reasonably do so. Newman wrote to the Secretary of the London Mathematical Society, F.P. White, explaining the position:

  31 May 1936

  Dear White,

  I think you know the history of Turing’s paper on Computable numbers. Just as it was reaching its final state an offprint arrived, from Alonzo Church of Princeton, of a paper anticipating Turing’s results to a large extent.

  I hope it will nevertheless be possible to publish the paper. The methods are to a large extent different, and the result is so important that different treatments of it should be of interest. The main result of both Turing and Church is that the Entscheidungs problem on which Hilbert’s disci
ples have been working for a good many years – i.e. the problem of finding a mechanical way of deciding whether a given row of symbols is the enunciation of a theorem provable from the Hilbert axioms – is insoluble in its general form. …

  Alan reported to his mother on 29 May:

  I have just got my main paper ready and sent in. I imagine it will appear in October or November. The situation with regard to the note for Comptes Rendus was not so good. It appears that the man I wrote to, and whom I asked to communicate the paper for me had gone to China, and moreover the letter seems to have been lost in the post, for a second letter reached his daughter.

  Meanwhile a paper has appeared in America, written by Alonzo Church, doing the same things in a different way. Mr Newman and I have decided however that the method is sufficiently different to warrant the publication of my paper too. Alonzo Church lives at Princeton so I have decided quite definitely about going there.

  He had applied for a Procter Fellowship. Princeton offered three of these, one in the gift of Cambridge, one of Oxford, one of the Collège de France. He was not to be successful, for the Cambridge one went that year to R.A. Lyttleton, the mathematician and astronomer. But he must have found that his King’s fellowship would provide just enough funds.

  Meanwhile, it was now necessary for the publication of the paper that he should include a demonstration that its definition of ‘computable’ – that is, as anything that could be computed by a Turing machine – was exactly equivalent to what Church had called ‘effectively calculable’, meaning that it could be described by a formula in the lambda-calculus. So he studied Church’s work from the papers which he and S.C. Kleene had produced in 1933 and 1935, and sketched out the required demonstration in an appendix to the paper which was finished on 28 August. The correspondence of ideas was quite straightforward, since Church had used a definition (that of a formula being ‘in normal form’) which corresponded to the Turing definition of ‘satisfactory’ machines, and had then used a Cantor diagonal argument to produce an unsolvable problem.

  If he had been a more conventional worker, he would not have attacked the Hilbert problem without having read up all of the available literature, including Church’s work. He then might not have been pre-empted – but then, he might never have created the new idea of the logical machine, with its simulation of ‘states of mind’, which not only closed the Hilbert problem but opened up quite new questions. It was the advantage and the disadvantage of working as what Newman called ‘a confirmed solitary’. Both with the Central Limit Theorem and with the Entscheidungs problem, he had been the Captain Scott of mathematics, coming in a splendid second place. And while he was not the person to think of mathematics and science as a sort of competitive game, it was obviously a disappointment. It meant months of delay, and obscured the originality of his own attack. It confused his moment of coming out into the world.

  As for the Central Limit Theorem, his fellowship dissertation was entered for the Cambridge mathematical essay competition, the Smith’s Prize, that summer. This caused a flurry down at Guildford, where Mrs Turing and John spent a frantic half-hour on hands and knees doing up the parcel, which Alan had left until the last minute before sending off. John had married in August 1934 and Alan had by now become an uncle. Neither his brother, nor his parents, had the faintest inkling of the philosophical problems which underlay his work, or which underlay his life. News of Alan’s successes came as glowing reports from a higher and higher Sixth Form. Mrs Turing, with her interest in the spiritual world, would have been the most sensitive to Alan’s concern with free will, but even she never saw this fundamental connection. For Alan never expatiated on his inner problems, and only occasionally did rather cryptic hints of them emerge.

  The university, like King’s, took a charitable view of Alan’s rediscovery of the theorem, and it won him the prize and hence £31. By now he had taken up sailing as a holiday pastime, and thought of putting the money towards buying a boat. But he decided against it, perhaps needing it for his year in America.

  Victor Beuttell came to stay with Alan at Cambridge in the early summer. Alan was returning the hospitality that the Beuttells had offered him but another reason for Victor’s visit was that he had now joined the family firm and had been set to work on developing the K-ray system. The geometry that he had discussed with Alan at school had helped him, but he was hoping to have Alan’s advice on the new problem which was to make a double-sided system so that both sides of a poster could be illuminated evenly by a single light source. (It was required by a brewery chain). Alan, however, said he was too preoccupied with his own work, and instead they went off to watch the May Bumps boat races.

  Once they were talking about art and sculpture and it was in this connection that Alan suddenly amazed Victor by saying that he found the male form beautiful, and the female unattractive. Victor now found himself a double crusader, and tried to convince Alan that Jesus had indicated the right course by befriending Mary Magdalene. Alan had no answer to this, but then this was not a problem of reason. All he could do was to express the sensation of being in a Looking-Glass world, in which from his point of view the conventional ideas were the wrong way about. This was probably the first time that he opened the subject outside the King’s ambience.

  It was difficult for Victor, who was a not particularly mature twenty-one, to know how to react. An element of trust now came into his staying in Alan’s room, though Alan remained ‘a perfect gentleman’. But Victor did not reject Alan’s friendship. Instead, they continued to agree to disagree on this subject as they did on religion. They talked of what hereditary or environmental influences might determine it one way or the other. But whatever these were, it was clear that here was part of Alan that was so; that part of his reality was shaped that way. For him, without a God, there was nothing to appeal to but some inner consistency. As in mathematics, that consistency could not be proved by a rule-book, and there was no deus ex machina to hand down decisions as to right and wrong. The axioms of his life were becoming clear by now, although how to live them out was quite another question. He had wanted the commonest in nature; he liked ordinary things. But he found himself to be an ordinary English homosexual atheist mathematician. It would not be easy.

  Alan also paid a visit to the Clock House before going out west, the first for three years. Mrs Morcom was now semi-invalid, but still mentally as vigorous as ever. She noted in her diary:

  September 9 (Wednesday) … Alan Turing came … He has come for a farewell visit before going out to America for 9 months (Princetown) to study under 2 great authorities on his subject: Godel (Warsaw) Alonso Church and Kleene. We had talk before dinner and again later to bring us up to date with our news. … He and Edwin played billiards.

  September 10: … Alan and Veronica to farms and Dingleside. … V and Alan tea up here with me. Had long talk with Alan about his work and whether in his subject (some abstruse branch of logic) one would come to ‘dead end’ etc.

  September 11: Alan went down to church alone to see Chris’ window and the little garden which he hadn’t seen before since it was finished – only the day he came to the dedication of the window… Alan taught me game called ‘Go’ – rather like Peggity.

  September 12: … Rupert and Alan had tea in my room and then I took them all by surprise by coming down to dinner. There were 10 of us – a jolly party. Gramophone concert… Men billiards.

  September 13 … Alan did problems with R[eginald] … Alan Rup[ert] and 2 girls bathed at Cadbury’s pool … Rup[ert] and Alan tea with me … Alan tried to explain what he is working at … they went off to catch 7.45 New Street.

  Alan lost Rupert when it came to the satisfactory and the unsatisfactory description numbers. It would have been hard for Mrs Morcom to feel that this ‘abstruse branch of logic’ had anything to do with the scientific imagination of her lost son, so that Alan had done something that Christopher had been called away from.

  Mrs Turing saw Alan off at Southa
mpton on 23 September, when he embarked on the Cunard liner, the Berengaria. He had picked up a sextant in the Farringdon Road market to amuse himself on the voyage. He also went equipped with all the standard upper-middle-class British prejudices about America and Americans, and the five days on the Atlantic did little to disabuse him. From ‘41°20′N, 62°W’, he complained:2

  It strikes me that Americans can be the most insufferable and insensitive creatures you could wish. One of them has just been talking to me and telling me of all the worst aspects of America with evident pride. However they may not all be like that.

  The towers of the Manhattan skyline swam into view next morning, on 29 September, and Alan entered the New World:

  We were practically in New York at 11.00 a.m. on Tuesday but what with going through quarantine and passing the immigration officers we were not off the boat until 5.30 p.m. Passing the immigration officers involved waiting in a queue for over two hours with screaming children round me. Then, after getting through the customs I had to go through the ceremony of initiation to the U.S.A., consisting of being swindled by a taxi-driver. I considered his charge perfectly preposterous, but as I had already been charged more than double English prices for sending my luggage, I thought it was possibly right.