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

Home > Science > Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game > Page 24
Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game Page 24

by Andrew Hodges


  *

  Back for three months in the mild Cambridge summer of 1937, there were three major projects on hand. First there was some tidying up of Computable Numbers. Bernays, in Zürich, had perhaps rather annoyingly found some errors13 in his proof that the Hilbert decision problem, in its precise form, was unsolvable, and these had to be put right by a correction note in the LMS Proceedings. He also completed a formal demonstration14 that his own ‘computability’ coincided exactly with Church’s ‘effective calculability’. By now there existed yet a third definition of the same sort of idea. This was the ‘recursive function’, which was a way of making absolutely precise the notion of defining a mathematical function in terms of other more elementary functions; Gödel had suggested it, and it had been taken up by Kleene. It was implicit in Gödel’s proof of the incompleteness of arithmetic. For when Gödel showed that the concept of proof by chess-like rules was an ‘arithmetical’ concept, one as ‘arithmetical’ as finding a highest common factor or something of the kind, he was really saying it could be done by a ‘definite method’. This idea, when formalised and extended somewhat, led to the definition of the ‘recursive function’. And now it had turned out that the general recursive function was exactly equivalent to the computable function. So Church’s lambda-calculus, and Gödel’s way of defining arithmetical functions, both turned out to be equivalent to the Turing machine. Gödel himself later acknowledged15 the Turing machine construction as the most satisfactory definition of a ‘mechanical procedure’. At the time, it was a very striking and surprising fact, that three independent approaches to the idea of doing something in a definite way, had converged upon equivalent concepts.

  The second project concerned the ‘new ideas in logic’ for a doctoral thesis. The basic idea was to see if there was any way in which to escape the force of Gödel’s result that there would always be true but unprovable assertions within arithmetic. This was not a new question, for Rosser, now at Cornell, had produced a paper16 in March 1937 which took it up. But Alan planned a rather more general attack on the question.

  His third project was a very ambitious one, for he had decided to try his strength on the central problem of the theory of numbers. It was not a new interest, for he had possessed Ingham’s book on the subject since 1933. But in 1937 Ingham sent him some recent papers,17 on learning that he wished to make an attack himself. It was ambitious because the question he chose was one that had long absorbed and defeated the greatest pure mathematicians.

  Although the prime numbers were such ordinary things, it was easy to pose quite baffling questions about them in a few words. One question had been solved very early on. Euclid had been able to show that there were infinitely many prime numbers, so that although in 1937 the number 2127 – 1 = 170141183460469231731687303715884 105727 was the largest known prime, it was also known that they continued for ever. But another property that was easy to guess, but very hard to prove, was that the primes would always thin out, at first almost every other number being prime, but near 100 only one in four, near 1000 only one in seven, and near 10,000,000,000 only one in 23. There had to be a reason for it.18

  In about 1793, the fifteen-year-old Gauss noticed that there was a regular pattern to the thinning-out. The spacing of the primes near a number n was proportional to the number of digits in the number n; more precisely, it increased as the natural logarithm of n. Throughout his life Gauss, who apparently liked doing this sort of thing, gave idle leisure hours to identifying all the primes less than three million, verifying his observation as far as he could go.

  Little advance was made until 1859, when Riemann developed a new theoretical framework in which to consider the question. It was his discovery that the calculus of the complex numbers* could be used as a bridge between the fixed, discrete, determinate prime numbers on the one hand, and smooth functions like the logarithm – continuous, averaged-out quantities – on the other. He thereby arrived at a certain formula for the density of the primes, a refinement of the logarithm law that Gauss had noticed. Even so, his formula was not exact, and nor was it proved.

  Riemann’s formula ignored certain terms which he was unable to estimate. These error terms were only in 1896 proved to be small enough not to interfere with the main result, which now became the Prime Number Theorem, and which stated in a precise way that the primes thinned out like the logarithm – not just as a matter of observation, but proved to be so for ever and ever. But the story did not end here. As far as the tables went it could be seen that the primes followed this logarithmic law quite amazingly closely. The error terms were not only small compared with the general logarithmic pattern; they were very small. But was this also true for the whole infinite range of numbers, beyond the reach of computation? – and if so what was the reason for it?

  Riemann’s work had put this question into a quite different form. He had defined a certain function of the complex numbers, the ‘zeta-function’. It could be shown that the assertion that the error terms remained so very small was essentially equivalent to the assertion that this Riemann zeta-function took the value zero only at points which all lay on a certain line in the plane. This assertion had become known as the Riemann Hypothesis. Riemann had thought it ‘very likely’ to be true, and so had many others, but no proof had been discovered. In 1900 Hilbert had made it his Fourth Problem for twentieth-century mathematics, and at other times called it ‘the most important in mathematics, absolutely the most important’. Hardy had bitten on it unsuccessfully for thirty years.

  This was the central problem of the theory of numbers, but there was a constellation of related questions, one of which Alan picked for his own investigation. The simple assumption that the primes thinned out like the logarithm, without Riemann’s refinements to the formula, seemed always to overestimate the actual number of primes by a certain amount. Common sense, or ‘scientific induction’, based on millions of examples, would suggest that this would always be so, for larger and larger numbers. But in 1914 Hardy’s collaborator J. E. Littlewood had shown that this was not so, for there existed some point where the simple assumption would underestimate the cumulative total of primes. Then in 1933 a Cambridge mathematician, S. Skewes, had shown19 that if the Riemann Hypothesis were true, a crossover point would occur before

  which, Hardy commented, was probably the largest number ever to serve any definite purpose in mathematics.* It could be asked whether this enormous bound might be reduced, or whether one could be found that did not depend upon the truth of the Riemann Hypothesis, and these were the problems that Alan now undertook.

  One new departure at Cambridge was his acquaintance with Ludwig Wittgenstein, the philosopher. He would have seen Wittgenstein before at the Moral Science Club, and Wittgenstein (like Bertrand Russell) had received a copy of Computable Numbers. But it was in this summer of 1937 that Alister Watson, the King’s Fellow, introduced them and they met sometimes in the botanical gardens. Watson had written a paper20 on the foundations of mathematics for the Moral Science Club, in which he made use of the Turing machine. Wittgenstein, whose first work had been as an engineer, always liked practical, down-to-earth constructions and would have approved of the way that Alan had made a vague idea so definite. Curiously, the failure of the Hilbert programme had also meant the end of the point of view advanced by Wittgenstein in his first phase, in the Tractatus Logico-Philosophicus, that every well-posed problem could be solved.

  Alan probably had a boating holiday – either on the Norfolk Broads, or at Bosham on Chichester Harbour. He also stayed for a while with the Beuttells in London. Although Mr Beuttell in principle espoused liberal causes of feminism and profit-sharing, his own firm was run on strictly autocratic lines, and so was his family. Victor’s younger brother Gerard was studying physics at Imperial College, but his father was extremely annoyed that he spent his time flying model aeroplanes to investigate wind currents, and put a stop to his studies. Alan was furious to hear this, saying that Gerard had a contribution to mak
e to science,21 and was doubly upset because he respected his father. He also roared with approval when he heard that Gerard had told his father, in connection with his infringing some petty rule of the family firm, that he would only obey ‘sensible rules’.

  It was also in London that Alan met James again for a weekend. They stayed at a rather sordid bed-and-breakfast place near Russell Square. They went to see a film or two and Elmer Rice’s play Judgment Day about the Reichstag-fire trial. Alan must have found it a relief to be with someone who did not reject his sexual advances, although it was always clear that James aroused in him neither deep feelings, nor a special physical attraction. The relationship was not able to develop beyond this point. After this weekend, James had almost no further experience for about twelve years. Although Alan was more exploratory, this would be his story too. His life would not change until much water had flowed under the bridge.

  On 22 September, Alan met up at Southampton with an American friend from Graduate College, Will Jones. They had arranged to travel back together, and boarded the German liner, the Europa. Will Jones had spent the summer at Oxford, and it was he who chose the German ship, simply because it was faster. A more dutiful anti-fascist than Alan would not have used it, but on the other hand a more conventional person would not have spent the voyage in learning Russian, enjoying the shocked German expressions as he wielded a textbook emblazoned with hammer and sickle.

  On the boat, wrote Alan on arrival, he

  Was very glad to have Will Jones as travelling companion. There didn’t seem to be anyone very interesting on board so Will and I whiled away the time with philosophical discussions, and spent half of one afternoon in trying to find the speed of the boat.

  Back at Princeton, Alan and Will Jones spent much time talking together. Will Jones came from the old white South of deepest Mississippi, and had studied philosophy at Oxford. So this was not the stereotyped meeting of Yankee brashness and old world elegance, far from it. Will Jones came from quite another America, just as Alan represented a plain-speaking, pragmatic, liberal England. As a philosopher with a serious interest in science, Will Jones also rose above the usual boundaries of arts and sciences. He was currently writing a dissertation on the claim of Kant that moral categories could be justified even if human actions were as determined as the motions of the planets. He canvassed Alan’s opinion as to whether quantum mechanics had affected the argument – so much the problem to which Alan had addressed himself five or so years before! But now he gave the impression that he had long been happy with the Russellian view, that at some level the world must evolve in a mechanistic way. He was not now very interested in philosophical, as opposed to scientific, discussions of the problem of free will. Perhaps the trace of his former conflict lay in his very vehemence in the materialist direction. ‘I think of people as pink-coloured collections of sense-data,’ he once joked. If only it were so easy! Symbolically, the Research fountain pen that Mrs Morcom had given him in 1932 was lost on the voyage.

  Will Jones also had Alan explain to him some of the theory of numbers, and enjoyed the way that Alan did it, showing how from the most simple axioms, all the properties could be precisely derived – an approach quite different from the rote-learning of school mathematics. Alan never talked to Will about his emotional problems, but it might well be that he derived moral support in a much more general way, for Will appreciated in him the embodiment of the moral philosophy of G. E. Moore and Keynes.

  Alan and Will had become aquainted through being members of the same circle of friends the previous year, and another of the circle had also returned to Princeton. This was Malcolm MacPhail, a Canadian physicist, who became involved in a sideline that Alan took up.22

  It was probably in the fall of 1937 that Turing first became alarmed about a possible war with Germany. He was at that time supposedly working hard on his famous thesis but nevertheless found time to take up the subject of cryptanalysis with characteristic vigour…. on this topic we had many discussions. He assumed that words would be replaced by numbers taken from an official code book and messages would be transmitted as numbers in the binary scale. But, to prevent the enemy from deciphering captured messages even if they had the code book, he would multiply the number corresponding to a specific message by a horrendously long but secret number and transmit the product. The length of the secret number was to be determined by the requirement that it should take 100 Germans working eight hours a day on desk calculators 100 years to discover the secret factor by routine search!

  Turing actually designed an electric multiplier and built the first three or four stages to see if it could be made to work. For the purpose he needed relay-operated switches which, not being commercially available at that time, he built himself. The Physics Department at Princeton had a small but well equipped machine shop for its graduate students to use, and my small contribution to the project was to lend Turing my key to the shop, which was probably against all the regulations, and show him how to use the lathe, drill, press etc. without chopping off his fingers. And so, he machined and wound the relays; and to our surprise and delight the calculator worked.

  Mathematically, this project was not advanced, for it used only multiplication. But although it used no advanced theory, it involved applications of ‘dull and elementary’ mathematics which were by no means well known in 1937.

  For one thing, the binary representation of numbers would have seemed a novelty to anyone then engaged in practical computations. Alan had used binary numbers in Computable Numbers. There they brought in no point of principle, but made it possible to represent all the computable numbers as infinite sequences of 0s and 1s alone. In a practical multiplier, however, the advantage of binary numbers was more concrete: it was that the multiplication table then reduced to:

  The binary multiplication table being so trivial, the work of a multiplier would be reduced to carrying and adding operations.

  A second aspect of his project was its connection with elementary logic. The arithmetical operations with 0s and ls could be thought of in terms of the logic of propositions. Thus the trivial multiplication table, for instance, could be considered as equivalent to the function of the word and in logic. For if p and q were propositions, then the following ‘truth-table’ would show in what circumstances ‘p and q’ was true:

  It was the same game, with a different interpretation. All of this would have been entirely familiar to Alan, the calculus of propositions appearing on the first page of any text on logic. It was sometimes called ‘Boolean Algebra’ after George Boole, who had formalised what he optimistically called ‘the laws of thought’ in 1854. Binary arithmetic could all be expressed in terms of Boolean algebra, using AND, OR, and NOT. His problem in designing the multiplier would be to use Boolean algebra to minimise the number of these elementary operations required.

  This, as a paper exercise, would be very similar to that of designing a ‘Turing machine’ for the same problem. But in order to embody it in working machinery, it required some means of arranging for different physical ‘configurations’. This was achieved by the switches, for the whole point of a switch would be that it could be in one of two states, ‘on’ or ‘off’, ‘0’ or ‘1’, ‘true’ or ‘false’. The switches that he used were operated by relays, and in this way electricity played its first direct part in his urge to connect logical ideas with something that physically worked. There was nothing new about the electromagnetic relay, which had been invented by the American physicist Henry a hundred years earlier. Its physical principle was the same as that of the electric motor, an electric current, passing through a coil, causing a magnetic head to move. However, the point of a relay was that the magnetic head would either open or close another electrical circuit. It would act as a switch. The name ‘relay’ derived from its use in early telegraph systems, to allow an enfeebled electric signal to set off a fresh, clean click. It was this all-or-nothing logical function of relays that made them necessary by the million in the a
utomatic telephone exchanges proliferating in the United States and Britain alike.

  It was not well known in 1937 that the logical properties of combinations of switches could be represented by Boolean algebra, or by binary arithmetic, but this was not hard for a logician to see. Alan’s task was to embody the logical design of a Turing machine in a network of relay-operated switches. The idea would be that when a number was presented to the machine, presumably by setting up currents at a series of input terminals, the relays would click open and closed, currents would pass through, and emerge at output terminals, thus in effect ‘writing’ the enciphered number. It would not actually use ‘tapes’ but from a logical point of view it came to the same thing. Turing machines were coming to life, for the first stages of his relay multiplier actually worked. Alan’s rather surreptitious access to the physics workshop was, however, symbolic of the problem that he faced in creating that life, by overcoming the line drawn between mathematics and engineering, the logical and the physical.

  As a cipher the idea was surprisingly feeble, the more so when set against his claim of a year earlier. Did he not credit the Germans with being able to find the highest common factor of two or more numbers in order to find the ‘secret number’ used as key? Even if some added sophistication removed this loophole, it would still suffer from the crippling practical disadvantage that a single incorrectly transmitted digit would render the entire message indecipherable.

  It might be that it was never intended very seriously, and that he had gone off at a tangent in meeting the challenge of designing a binary multiplier. But as a reader of the New Statesman,* sent to him from England, he had no particular reason to be frivolous in speaking of Germany. Every week there were frightening articles about German policy inside and outside the new Reich. Even if the prospect of war work was more the excuse to take up a ‘dull and elementary’ (but fascinating) sideline than anything like the call of duty, he would not have been alone if he found that Nazi Germany had resolved his qualms about ‘morality’.

 

‹ Prev