Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  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 1s 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 automatic 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 entir
e 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’.

  There was also another machine he had in mind, but this had nothing to do with Germany, except in the very different sense that it came out of the work of Riemann. Its purpose was to calculate the Riemann zeta-function. Apparently he had decided that the Riemann hypothesis was probably false, if only because such great efforts had failed to prove it. Its falsity would mean that the zeta-function did take the value zero at some point which was off the special line, in which case this point could be located by brute force, just by calculating enough values of the zeta-function.

  This programme had already been started; indeed Riemann himself had located the first few zeroes and checked that they all lay on the special line. In 1935-6, the Oxford mathematician E.C. Titchmarsh had used the punched-card equipment which was then used for the calculation of astronomical predictions to show that (in a certain precise sense) the first 104 zeroes of the zeta-function did all lie on the line. Alan’s idea was essentially to examine the next few thousand or so in the hope of finding one off the line.

  There were two aspects to the problem. Riemann’s zeta-function was defined as the sum of an infinite number of terms, and although this sum could be re-expressed in many different ways, any attempt to evaluate it would in some way involve making an approximation. It was for the mathematician to find a good approximation, and to prove that it was good: that the error involved was sufficiently small. Such work did not involve computation with numbers, but required highly technical work with the calculus of complex numbers. Titchmarsh had employed a certain approximation which – rather romantically – had been exhumed from Riemann’s own papers at Göttingen where it had lain for seventy years. But for extending the calculation to thousands of new zeroes a fresh approximation was required; and this Alan set out to find and to justify.

  The second problem, quite different, was the ‘dull and elementary’ one of actually doing the computation, with numbers substituted into the approximate formula, and worked out for thousands of different entries. It so happened that the formula was rather like those which occurred in plotting the positions of the planets, because it was of the form of a sum of circular functions with different frequencies. It was for this reason that Titchmarsh had contrived to have the dull repetitive work of addition, multiplication, and of looking up of entries in cosine tables done by the same punched-card methods that were used in planetary astronomy. But it occurred to Alan that the problem was very similar to another kind of computation which was also done on a large practical scale – that of tide prediction. Tides could also be regarded as the sum of a number of waves of different periods: daily, monthly, yearly oscillations of rise and fall. At Liverpool there was a machine23 which performed the summation automatically, by generating circular motions of the right frequencies and adding them up. It was a simple analogue machine; that is, it created a physical analogue of the mathematical function that had to be calculated. This was a quite different idea from that of the Turing machine, which would work away on a finite, discrete, set of symbols. This tide predicting machine, like a slide rule, depended not on symbols, but on the measurement of lengths. Such a machine, Alan had realised, could be used on the zeta-function calculation, to save the dreary work of adding, multiplying, and looking up of cosines.

  Alan must have described this idea to Titchmarsh, for a letter24 from him dated 1 December 1937 approved of this programme of extending the calculation, and mentioned: ‘I have seen the tide-predicting machine at Liverpool, but it did not occur to me to use it in this way.’

  There were some diversions. The hockey playing continued, although without Francis Price and Shaun Wylie the team had lost its sparkle. Alan found himself involved in making the arrangements. He also played a good deal of squash. At Thanksgiving he drove north to visit Jack and Mary Crawford for a second time. (‘I am getting more competent with the car.’) Before Christmas, Alan took up an invitation from his friend Venable Martin to go and stay with him. He came from a small town in South Carolina.

  We drove down from here in two days and then I stayed there for two or three days before I came back to Virginia to stay with Mrs Welbourne. It was quite as far south as I had ever been – about 34°. The people seem to be all very poor down there still, even though it is so long since the civil war.

  Mrs Welbourne was ‘a mysterious woman in Virginia’ who had a habit of inviting English students from the Graduate College for Christmas. ‘I didn’t make much conversational progress with any of them,’ Alan had to confess of her family. Alan and Will Jones organised another treasure hunt, although it lacked the élan of the previous year; one of the clues was in his collected Shaw. And in April he and Will made a trip to visit St John’s College, Annapolis, and Washington. ‘We also went and listened to the Senate for a time. They seemed very informal. There were only six or eight of them present and few of them seemed to be attending.’ They looked down from the gallery and saw Jim Farley, Roosevelt’s party boss. It was another world.

  The main business of the year was the completion of his PhD thesis,25 investigating whether there was any way of escaping the force of Gödel’s theorem. The fundamental idea was to add further axioms to the system, in such a way that the ‘true but unprovable’ statements could be proved. But arithmetic, looked at in this way, had a distinctly hydra-headed nature. It was easy enough to add an axiom so that one of Gödel’s peculiar statements could be proved. But then Gödel’s theorem could be applied to the enlarged set of axioms, producing yet another ‘true but unprovable’ assertion. It could not be enough to add a finite number of axioms; it was necessary to discuss adding infinitely many.

  This was just the beginning, for as mathematicians well knew, there were many possible ways of doing ‘infinitely many’ things in order. Cantor had seen this when investigating the notion of ordering the integers. Suppose, for example, that the integers were ordered in the following way: first all the even numbers, in ascending order, and then all the odd numbers. In a precise sense, this listing of the integers would be ‘twice as long’ as the usual one. It could be made three times as long, or indeed infinitely many times as long, by taking first the even numbers, then remaining multiples of 3, then remaining multiples of 5, then remaining multiples of 7, and so on. Indeed, there was no limit to the ‘length’ of such lists. In the same way, extending the axioms of arithmetic could be done by one infinite list of axioms, or by two, or by infinitely many infinite lists – there was again no limit. The question was whether any of this would overcome the Gödel effect.

  Cantor had described his different orderings of the integers by ‘ordinal numbers’, and Alan described his different extensions of the axioms of arithmetic as ‘ordinal logics’. In one sense it was clear that no ‘ordinal logic’ could be ‘complete’, in Hilbert’s technical sense. For if there were infinitely many axioms, they could not all be written out. There would have to be some finite rule for generating them. But in that case, the whole system would still be based on a finite number of rules, so Gödel’s theorem would still apply to show that there were still unprovable assertions.

  However, there was a more subtle question. In his ‘ordinal logics’, the rule for generating the axioms was given in terms of substituting an ‘ordinal formula’ into a certain expression. This was itself a ‘mechanical process’. But it was not a ‘mechanical process’ to decide whether a given formula was an ordinal for
mula. What he asked was whether all the incompleteness of arithmetic could be concentrated in one place, namely into the unsolvable problem of deciding which formulae were ‘ordinal formulae’. If this could be done, then there would be a sense in which arithmetic was complete; everything could be proved from the axioms, although there would be no mechanical way of saying what the axioms were.

  He likened the job of deciding whether a formula was an ordinal formula to ‘intuition’. In a ‘complete ordinal logic’, any theorem in arithmetic could be proved by a mixture of mechanical reasoning, and steps of ‘intuition’. In this way, he hoped to bring the Gödel incompleteness under some kind of control. But he regarded his results as disappointingly negative. ‘Complete logics’ did exist, but they suffered from the defect that one could not count the number of ‘intuitive’ steps that were necessary to prove any particular theorem. There was no way of measuring how ‘deep’ a theorem was, in his sense; no way of pinning down exactly what was going on.

  One nice touch on the side was his idea of an ‘oracle’ Turing machine, one which would have the property of being able to answer one particular unsolvable problem (like recognising an ordinal formula). This introduced the idea of relative computability, or relative unsolvability, which opened up a new field of enquiry in mathematical logic. Alan might have been thinking of the ‘oracle’ in Back to Methuselah, through whose mouth Bernard Shaw answered the unsolvable problems of the politicians with ‘Go home, poor fool’!

  Less clear from his remarks in the paper was to what extent he regarded such ‘intuition’, the ability to recognise a true but unprovable statement, as corresponding to anything in the human mind. He wrote that