Alan Turing: The Enigma (23 page)

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 there 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 said
³²
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 published
³³
by the London Mathematical Society later in the month.

The result was a small improvement to a paper by von Neumann,
³⁴
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.
³⁵
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.
³⁶
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 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 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.

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.