Alan had been stimulated by Hilbert’s decision problem, or the Entscheidungsproblem as it was in German. He had not only answered it, but had done much more. Indeed, he would entitle his paper ‘On Computable Numbers, with an application to the Entscheidungsproblem.’ 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 Entscheidungsproblem.
* * *
* 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’ wer
e the semi-official second-year examinations.
* Not the von Neumann book, however, which he only received in October 1932.
* Joynson Hicks, the reactionary Home Secretary.
* This gave him a tenuous link with his mother, who had shares in a Bethnal Green housing association. 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.
* 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’.
* It is not clear from the context whether ‘next year’ means 1935–6 or 1936–7.
* 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 Entscheidungsproblem 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 Ma
y 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 Entscheidungsproblem 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,
Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game Page 20