Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game

by Andrew Hodges

  From one point of view this was a very tall order, going to the heart of everything known about creative mathematics. Hardy, for instance, had said32 rather indignantly in 1928 that:

  There is of course no such theorem, and this is very fortunate, since if there were we should have a mechanical set of rules for the solution of all mathematical problems, and our activities as mathematicians would come to an end.

  There were plenty of statements about numbers which the efforts of centuries had failed either to prove or disprove. There was Fermat’s so-called Last Theorem, which conjectured that there was no cube which could be expressed as the sum of two cubes, no fourth power as sum of two fourth powers, and so on. Another was Goldbach’s conjecture, that every even number was the sum of two primes. It was hard to believe that assertions which had resisted attack so long could in fact be decided automatically by some set of rules. Furthermore, the difficult problems which had been solved, such as Gauss’s Four Square Theorem, had rarely been proved by anything like a ‘mechanical set of rules’, but by the exercise of creative imagination, constructing new abstract algebraic concepts. As Hardy said, ‘It is only the very unsophisticated outsider who imagines that mathematicians make discoveries by turning the handle of some miraculous machine.’

  On the other hand, the progress of mathematics had certainly brought more and more problems within the range of a ‘mechanical’ approach. Hardy might say that ‘of course’ this advance could never encompass the whole of mathematics, but after Gödel’s theorem, nothing was ‘of course’ any more. The question deserved a more penetrating analysis.

  Newman’s pregnant phrase ‘by a mechanical process’ revolved in Alan’s mind. Meanwhile, the spring of 1935 saw two other steps forward. The fellowship election was held on 16 March. Philip Hall had just become an elector, and argued for Alan, saying that his full strength had not been shown in his rediscovery of the Central Limit Theorem. But his advocacy was not needed. Keynes, Pigou and the Provost, John Sheppard, all had an assessment of him for themselves. He was elected, the first of his year, as one of the forty-six Fellows. The boys of Sherborne School enjoyed a half-holiday, and there was a clerihew that circulated:

  Turing

  Must have been alluring

  To get made a don

  So early on.

  He was still only twenty-two. The fellowship carried with it £300 a year for three years, which would normally be extended to six, and no explicit duties. He was entitled to room and board when he chose to reside at Cambridge, and to dine at High Table. On his first evening in the senior common room, he played Rummy and won a few shillings from the Provost. But he tended to prefer the company at dinner of his friends David Champernowne, Fred Clayton and Kenneth Harrison. It did not change his style of life, but did make him free for three years to pursue thought in any way he chose – as free as anyone could be without a private income. He supplemented his fellowship by supervising undergraduates in next-door Trinity Hall. If they came to his rooms hoping for a glimpse of King’s eccentricity, they were sometimes rewarded, as when Alan sat Porgy the teddy bear by the fire, in front of a book supported by a ruler, and greeted them with ‘Porgy is very studious this morning.’

  The election coincided with what Alan called a ‘small-scale discovery’ which constituted a first publishable paper. It was a neat result in group theory, which he announced to Philip Hall (whose own research lay in that field) on 4 April, saying he was ‘thinking of doing this sort of thing seriously.’ It was submitted and published33 by the London Mathematical Society later in the month.

  The result was a small improvement to a paper by von Neumann,34 which developed the theory of ‘almost periodic functions’* by defining them with reference to ‘groups’. As it happened, von Neumann arrived at Cambridge later that month. He was spending a summer away from Princeton, and gave a lecture course at Cambridge on the subject of ‘almost periodic functions’. Alan certainly met him this term, and most likely through attending this course.

  They were very different men. When Alan Turing was born, János von Neumann was the eight-year-old son of a rich Hungarian banker.35 There was for him no public-school training, and by 1922, before Alan was floating his paper boats at Hazelhurst, the eighteen-year-old von Neumann had published his first paper. Budapest János became Göttingen Johann, one of Hilbert’s disciples, and then in 1933 became Princeton Johnny, adopting English as his fourth language. The paper on ‘almost periodic functions’ was his fifty-second, part of an immense output which had moved from the axioms of set theory and quantum mechanics, to the topological groups which were the pure-mathematical underpinning of quantum theory, but taking in numerous other topics on the side.

  John von Neumann was one of the most important figures in twentieth-century mathematics, but he was a man who added worldly to intellectual success. He enjoyed a commanding manner, a sophisticated, racy humour, a training in engineering, a wide knowledge of history – and a salary of $10,000 over and above his substantial private income. He cut a figure very different from that of the twenty-two-year old in the shabby sports jacket, sharp but shy with a hesitant voice that had trouble with one language, let alone four. But mathematics did not see these things, and it might well have been the result of a meeting of minds when on 24 May Alan wrote home: ‘… I have applied for a visiting Fellowship at Princeton for next year.’*

  An additional reason would be, however, that Alan’s friend Maurice Pryce, whom he had met at the scholarship examinations in 1929, and with whom he had kept in touch, was ready to go to Princeton in September, having secured a fellowship there. In any case, it was becoming more and more clear that Princeton was the new Göttingen; there was a flow of first-rate mathematicians and physicists to and fro across the Atlantic. It was an aspect of the continuing transfer of power from Europe, and from Germany in particular, to America. No one who wanted to do something, as Alan did, could any longer ignore the United States.

  Alan continued work in group theory during 1935.36 He also thought of working in quantum mechanics, and approached R. H. Fowler, Professor of Mathematical Physics, for a suitable problem to work on. Fowler suggested trying to explain the dielectric constant of water, one of his favourite research topics. But Alan made no progress. And this problem, as indeed the whole field of mathematical physics, which offered so much to attract the ambitious young mathematicians of the 1930s, was put aside. For he had seen something new, something at the centre of mathematics, something at his centre. It owed almost nothing to the Tripos; it used only the commonest in Nature. It was profoundly ordinary, and yet led to a spectacular idea.

  It had become his habit to run long distances in the afternoons, along the river and elsewhere, even as far as Ely. It was at Grantchester, so he said later, lying in the meadow, that he saw how to answer Hilbert’s third question. It must have been in the early summer of 1935. ‘By a mechanical process’, Newman had said. So Alan Turing dreamed of machines.

  ‘For, of course, the body is a machine. It is a vastly complex machine, many, many times more complicated than any machine ever made by hands; but still after all a machine.’ Such was Brewster’s paradoxical assertion. At one level, the body was living, not a machine. But at another, more detailed level of description, that of the ‘living bricks’, it was all determined. It was not the power of the machine that was the point of the remark; it was its lack of will.

  It was not the determinism of physics, or chemistry, or of biological cells, that was involved in Hilbert’s question about decidability. It was something more abstract. It was the quality of being fixed in advance, in such a way that nothing new could arise. And the operations were to be operations on symbols, rather than on things of any particular mass or chemical composition.

  Alan had to abstract this quality of being determined, and apply it to the manipulation of symbols. People had spoken, as Hardy did, of ‘mechanical rules’ for mathematics, of ‘turning the handle’ of a miraculous machine, but no
one had actually sat down to design one. This was what he set out to do. For although he was not really ‘the very unsophisticated outsider’ of whom Hardy spoke, he attacked the problem in a peculiarly naive way, undaunted by the immensity and complexity of mathematics. He started from nothing, and tried to envisage a machine that could tackle Hilbert’s problem, that of deciding the provability of any mathematical assertion presented to it.

  There were, of course, machines in existence which manipulated symbols. The typewriter was one such. Alan had dreamt of inventing typewriters as a boy; Mrs Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter ‘mechanical’. It would mean that its response, to any particular action of the operator, was perfectly certain. One could describe in advance exactly how the machine would behave in any contingency. But there was more to be said even about a humble typewriter than that. The response would depend upon the current condition, or what Alan called the current configuration, of the machine. In particular, a typewriter would have an ‘upper case’ configuration and a ‘lower case’ configuration. This was an idea which Alan put in a more general and abstract form. He would consider machines which at any time would be in one of a finite number of possible ‘configurations’. Then if, as with the typewriter keyboard, there were only a finite number of things that could be done to the machine, a complete account of the behaviour of the machine could be given, once for all, in finite form.

  However, the typewriter had a further feature which was essential to its function. Its typing point could move, relative to the page. Its typing action would be independent of the position of this point on the page. Alan incorporated this idea too into his picture of the more general machine. It was to have internal ‘configurations’, and a variable position on a printing line. The action of the machine would not depend upon its position.

  Neglecting details as to margins, line control, and so forth, these ideas would suffice to give a complete description of the nature of a typewriter. An exact account of the configurations and positions allowed, and of how the character keys determined the symbols printed, the shift key the change of configuration from ‘lower’ to ‘upper’, and the space bar and backspace the printing position, would bring out the features most relevant to its function. If an engineer took this account, and created a physical machine which met its specifications, the result would be a typewriter, regardless of its colour, weight, or other attributes.

  But a typewriter was too limited to serve as a model. It dealt with symbols, but it could only write them, and it required a human operator to choose the symbols and changes of configuration and position, one at a time. What, Alan Turing asked, would be the most general kind of machine that dealt with symbols? To be a ‘machine’ it would have to retain the typewriter’s quality of having a finite number of configurations, and an exactly determined behaviour in each. But it would have to be capable of much more. And so he imagined machines which were, in effect, super-typewriters.

  To simplify the description he imagined his machines working with just one line of writing. This was only a technicality, which allowed margins and line control to be forgotten. But it was important that the supply of paper was to be assumed unlimited. In his picture, the typing point of his super-typewriter could progress indefinitely to left or right. For the sake of definiteness, he imagined the paper as being in the form of a tape, marked off into unit squares, such that just one symbol could be written on any one square. Thus his machines were to be finitely defined, but they would be allowed an unlimited amount of space on which to work.

  Next, the machine would be able to read, or using his word, to ‘scan’ the square of tape on which it rested. It would still of course be able to write symbols, but now also to erase them. But it would only be able to move one place to the left or the right at a time. What role remained to the human operator of the typewriter? He did mention the possibility of what he called ‘choice machines’, in which an external operator would have the job of making decisions at certain points. But the thrust of his argument was directed at what he called automatic machines, in which human intervention would play no part. For the goal of his development was the discussion of what Hardy had called ‘a miraculous machine’ – a mechanical process which could work on Hilbert’s decision problem, reading a mathematical assertion presented to it, and eventually writing a verdict as to whether it was provable or not. The whole point was that it should do so without the interference of human judgment, imagination or intelligence.

  Any ‘automatic machine’ would work away by itself, reading and writing, moving to and fro, all in accordance with the way in which it was constructed. At every step its behaviour would be completely determined by the configuration it was in and the symbol it had read. To be precise, the construction of the machine would determine, for each combination of configuration and symbol scanned:

  whether to write a new (specified) symbol in a blank square, to leave the existing one unchanged, or to erase it and leave a blank square

  whether to remain in the same configuration, or to change to some other (specified) configuration

  whether to move to the square on the left, or to the right, or to stay in the same position.

  If all this information, defining an automatic machine, were written out, it would form a ‘table of behaviour’ of a finite size. It would completely define the machine in the sense that whether physically constructed or not, the table would hold all the relevant information about it. From this abstract point of view, the table was the machine.

  Every different possible table would define a machine with a different kind of behaviour. There would be infinitely many possible tables, corresponding to infinitely many possible machines. Alan had rendered the vague idea of a ‘definite method’ or a ‘mechanical process’ into something very precise: a ‘table of behaviour’. And so now he had a very precise question to answer: was there or was there not one of these machines, one of these tables, that could produce the decision that Hilbert asked for?

  An example machine: The following ‘table of behaviour’ completely defines a machine with the character of an adding machine. Started with the ‘scanner’ somewhere to the left of two groups of 1’s, separated by a single blank space, it will add the two groups, and stop. Thus, it will transform

  into

  The task of the machine is to fill in the blank space, and to erase the last ‘1’. It will therefore suffice to provide the machine with four configurations. In the first it moves along the blank tape looking for the first group of ‘1’s. When it moves into the first group, it goes into the second configuration. The blank separator sends it into the third configuration, in which it moves along the second group until it encounters another blank, which acts as the signal to turn back, and to enter the fourth and final configuration in which it erases the last ‘1’ and marks time for ever.

  The complete table is:

  Even a very simple machine of this kind, as shown in the example, would be doing more than sums. The machine would effect acts of recognition, such as ‘finding the first symbol to the right’. A rather more complicated machine could perform multiplication, by repeated acts of copying out one group of 1s, while erasing one at a time of another group of 1s, and recognising when it had finished. Such a machine could also effect acts of decision, as for instance in deciding whether one number was divisible by another, or whether a given number was prime or composite. Clearly there was scope for exploiting this principle to mechanise a vast range of ‘definite methods’. But could there be such a machine that could decide Hilbert’s question about provability?

  This was much too hard a problem to approach by trying to write a ‘table’ to solve it. But there was an approach which led to the answer by a back-door route. Alan hit on the idea of the ‘computable numbers’. The crucial notion was that any ‘real number’ which was defined by some definite rule could be calculated by one of his machines. For instance, there
would be a machine to calculate the decimal expansion of π, rather as he had done at school. For it would require no more than a set of rules for adding, multiplying, copying, and so forth. π being an infinite decimal, the work of the machine would never end, and it would need an unlimited amount of working space on its ‘tape’. But it would arrive at every decimal place in some finite time, having used only a finite quantity of tape. And everything about the process could be defined by a finite table, left alone to work on a blank tape.

  This meant that he had a way of representing a number like π, an infinite decimal, by a finite table. The same would be true of the square root of three, or the logarithm of seven – or any other number defined by some rule. Such numbers he called the ‘computable numbers’.

  More precisely, the machine itself would know nothing about decimals or decimal places. It would simply produce a sequence of digits. A sequence that could be produced by one of his machines, starting on a blank tape, he called a ‘computable sequence’. Then an infinite computable sequence, prefaced by a decimal point, would define a ‘computable number’ between 0 and 1. It was in this more strict sense that any computable number between 0 and I could be defined by a finite table. It was important to his argument that the computable numbers would always be expressed as infinite sequences of digits, even if these were all 0 after a certain point.