Alan Turing: The Enigma (33 page)

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’.

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 machine
²³
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 letter
²⁴
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,
²⁵
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 formula. 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

Mathematical reasoning may be regarded rather schematically as the exercise of a combination of two faculties, which we may call
intuition
and
ingenuity
. (We are leaving out of account that most important faculty which distinguishes topics of interest from others; in fact, we are regarding the function of the mathematician as simply to determine the truth or falsity of propositions.) The activity of the intuition consists in making spontaneous judgments which are not the result of conscious trains of reasoning. …

and he claimed that his ideas on ‘ordinal logics’ represented one way of formalising this distinction. But it was not established that ‘intuition’ had anything to do with the incompleteness of finitely defined formal systems. After all, no one knew of this incompleteness until 1931, while intuition was a good deal older. It was the same ambiguity as in
Computable Numbers
, which mechanised mind, yet pointed out something beyond mechanisation. Did this have a significance for human minds? His views were not clear at this stage.

As
for the future, his intention was to return to King’s, provided that, as expected, they renewed his Fellowship which was, in March 1938, at the end of its first three years. On the other hand, his father wrote advising him (not very patriotically, perhaps) to find an appointment in the United States. For some reason King’s College was slow in notifying him that the extension of his fellowship had been made. Alan wrote to Philip Hall on 30 March:

I am writing a thesis for a Ph.D, which is proving rather intractable, and I am always rewriting parts of it. …

I am rather worried about the fact that I have heard nothing about re-election to my Fellowship. The most plausible explanation is simply that there has been no re-election, but [I] prefer to think there is some other reason. If you would make some cautious enquiries and send me a postcard I should be very grateful.

I hope Hitler will not have invaded England before I come back.

After the union with Austria on 13 March everyone was beginning to take Germany seriously. Meanwhile, Alan did dutifully go to Eisenhart and ask him ‘about possible jobs over here; mostly for Daddy’s information, as I think it is unlikely I shall take one unless you are actually at war before July. He didn’t know of one at present, but said he would bear it all in mind.’ But then a job materialised. Von Neumann himself offered a research assistant-ship at the IAS.