Alan Turing: The Enigma (27 page)

^*
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 publication
¹
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 disciples 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.