Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  In the summer and autumn of 1934, he continued to work on his dissertation.29 The deadline for its submission was 6 December, but Alan handed it in a month early, and was ready for a next step. Eddington, who had played so important a part in his early development, had suggested his dissertation problem to him. The next suggestion came from Hilbert, although not so directly. In the spring of 1935, while his dissertation went the rounds of the King’s Fellows, Alan went to a Part III course on Foundations of Mathematics. It was given by M.H.A. Newman.

  Newman, then nearly forty, was with J.H.C. Whitehead the foremost British exponent of topology. This branch of mathematics could be described as the result of abstracting from geometry such concepts as ‘connected’, ‘edge’ and ‘neighbouring’ which did not depend upon measurement.* In the 1930s it was unifying and generalising much of pure mathematics. Newman was a progressive figure in a Cambridge where classical geometry was more strongly represented.

  The basis of topology was the theory of sets, and so Newman had been drawn into the foundations of set theory. He had also attended the 1928 international congress at which Hilbert represented the Germany excluded in 1924. Hilbert had revived his call for an investigation into the foundations of mathematics. And it was in Hilbert’s spirit, rather than as a continuation of Russell’s ‘logistic’ programme, that Newman lectured. Indeed, the Russell tradition had petered out, for Russell himself had left Cambridge in 1916 when first convicted and deprived of his Trinity College lectureship; and of his contemporaries, Wittgenstein had turned in a different direction, Harry Norton had gone mad, and Frank Ramsey had died in 1930. This left Newman as the only person in Cambridge with a deep knowledge of modern mathematical logic, although there were others, Braithwaite and Hardy amongst them, who were interested in the various approaches and programmes.

  The Hilbert programme was essentially an extension of the work on which he had started in the 1890s. It did not attempt to answer the question which Frege and Russell had tackled, that of what mathematics really was. In that respect it was less philosophical, less ambitious. On the other hand, it was more far-reaching in that it asked profound and difficult questions about the systems such as Russell produced. In fact Hilbert posed the question as to what were, in principle, the limitations of a scheme such as that of Principia Mathematica. Was there a way of finding out what could, and what could not, be proved within such a theory? Hilbert’s approach was called the formalist approach, because it treated mathematics as if a game, a matter of form. The allowable steps of proof were to be considered like the allowable moves in a game of chess, with the axioms as the starting position of the game. In this analogy, ‘playing chess’ corresponded to ‘doing mathematics’, but statements about chess (such as ‘two knights cannot force checkmate’) would correspond to statements about the scope of mathematics. And it was with such statements that the Hilbert programme was concerned.

  At that 1928 congress, Hilbert made his questions quite precise. First, was mathematics complete, in the technical sense that every statement (such as ‘every integer is the sum of four squares’) could either be proved, or disproved. Second, was mathematics consistent, in the sense that the statement ‘2 + 2 = 5’ could never be arrived at by a sequence of valid steps of proof. And thirdly, was mathematics decidable? By this he meant, did there exist a definite method which could, in principle, be applied to any assertion, and which was guaranteed to produce a correct decision as to whether that assertion was true.

  In 1928, none of these questions was answered. But it was Hilbert’s opinion that the answer would be ‘yes’ in each case. In 1900 Hilbert had declared ‘that every definite mathematical problem must necessarily be susceptible of an exact settlement … in mathematics there is no ignorabimus’; and when he retired in 1930 he went further:30

  In an effort to give an example of an unsolvable problem, the philosopher Comte once said that science would never succeed in ascertaining the secret of the chemical composition of the bodies of the universe. A few years later this problem was solved.… The true reason, according to my thinking, why Comte could not find an unsolvable problem lies in the fact that there is no such thing as an unsolvable problem.

  It was a view more positive than the Positivists. But at the very same meeting, a young Czech mathematician, Kurt Gödel, announced results which dealt it a serious blow.

  Gödel was able to show31 that arithmetic must be incomplete: that there existed assertions which could neither be proved nor disproved. He started with Peano’s axioms for the integers, but enlarged through a simple theory of types, so that the system was able to represent sets of integers, sets of sets of integers, and so on. However, his argument would apply to any formal mathematical system rich enough to include the theory of numbers, and the details of the axioms were not crucial.

  He then showed that all the operations of ‘proof’, these ‘chess-like’ rules of logical deduction, were themselves arithmetical in nature. That is, they would only employ such operations as counting and comparing, in order to test whether one expression had been correctly substituted for another – just as to see whether a chess move was legal or not would only be a matter of counting and comparing. In fact, Gödel showed that the formulae of his system could be encoded as integers, so that he had integers representing statements about integers. This was the key idea.

  Gödel continued to show how to encode proofs as integers, so that he had a whole theory of arithmetic, encoded within arithmetic. It was an exploitation of the fact that if mathematics were regarded purely as a game with symbols, then it might as well employ numerical symbols as any other. He was able to show that the property of ‘being a proof or of ‘being provable’ was no more and no less arithmetical than the property of ‘being square’ or ‘being prime’.

  The effect of this encoding process was that it became possible to write down arithmetical statements which referred to themselves, like the person saying ‘I am lying.’ Indeed Gödel constructed one particular assertion which had just such a property, for in effect it said ‘This statement is unprovable.’ It followed that this assertion could not be proved true, for that would lead to a contradiction. Nor could it be proved false, for the same reason. It was an assertion which could not be proved or disproved by logical deduction from the axioms, and so Gödel had proved that arithmetic was incomplete, in Hilbert’s technical sense.

  There was more to it than this, for one remarkable thing about Gödel’s special assertion was that since it was not provable, it was, in a sense, true. But to say it was ‘true’ required an observer who could, as it were, look at the system from outside. It could not be shown by working within the axiomatic system.

  Another point was that the argument assumed that arithmetic was consistent. If, in fact, arithmetic were inconsistent, then every assertion would be provable. So more precisely, Gödel had shown that formalised arithmetic must either be inconsistent, or incomplete. He was also able to show that arithmetic could not be proved consistent within its own axiomatic system. To do so, all that would be required would be a proof that there was a single proposition (say, 2 + 2 = 5) which could not be proved true. But Gödel was able to show that such a statement of existence had the same character as the sentence that asserted its own unprovability. And in this way, he had polished off the first two of Hilbert’s questions. Arithmetic could not be proved consistent, and it was certainly not consistent and complete. This was an amazing new turn in the enquiry, for Hilbert had thought of his programme as one of tidying up loose ends. It was upsetting for those who wanted to find in mathematics something that was absolutely perfect and unassailable; and it meant that new questions came into view.

  Newman’s lectures finished with the proof of Gödel’s theorem, and thus brought Alan up to the frontiers of knowledge. The third of Hilbert’s questions still remained open, although it now had to be posed in terms of ‘provability’ rather than ‘truth’. Gödel’s results did not rule out the possibility that ther
e was some way of distinguishing the provable from the non-provable statements. Perhaps the rather peculiar Gödelian assertions could somehow be separated off. Was there a definite method, or as Newman put it, a mechanical process which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable?

  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 consituted 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, von Neumann Janos 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 Janos 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 is not clear from the context whether ‘next year’ means 1935-6, or 1936-7.

  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 q
uality 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 coure, 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.