COPElAND | 63
Hilbert emphasized that a ‘general solution of the decision problem . . . does not yet exist’, but
his 1928 account exuded optimism, and he wrote buoyantly of moving ‘closer to the solution of
the decision problem’.^29
Just a few years later, in 1936, Turing managed to prove that no such decision process was
possible. So Hilbert’s proposal to resolve questions of consistency by means of such a process
lay in tatters. Turing put it in his usual terse way:^30
I shall show that there is no general method which tells whether a given formula is provable in K
[the engere Functionenkalkül], or, what comes to the same, whether the system consisting of K
with [a formula] adjoined as an extra axiom is consistent.
All mathematicians make mistakes, but it is a mark of Hilbert’s greatness that the mis-
takes he made were so fundamental, so profound, that exposing them changed mathematics
irrevocably.
Turing visits Church
In the autumn of 1936 Turing left England for the United States where he would write a PhD
thesis at Princeton University. His supervisor at Princeton was Alonzo Church, the third of the
three central figures in the 1930s revolution (Fig. 7.3). Church was a few years older than Turing
and a Young Turk in the Princeton mathematics department. At the end of the 1920s he had
spent six months studying with Hilbert’s group in Germany. Church’s leading contribution to
the 1930s’ revolution—he called it the λ-calculus: the Greek letter λ is pronounced ‘lambda’—
later became part of the basic toolset of computer programming.
Before Turing’s departure from England, he and Church had (almost simultaneously) pro-
posed two different mathematical definitions of the idea of computation. Gödel was not at all
impressed with Church’s definition, bluntly telling Church that his approach was ‘thoroughly
unsatisfactory’.^31 On the other hand Gödel found Turing’s definition ‘most satisfactory’.^32 Even
the modest young Turing admitted that his definition was ‘possibly more convincing’ than
Church’s.^33 It was clear from the start that the relationship between Turing and Church was not
figure 7.3 Alonzo Church
From the Alonzo Church Papers (C0948);
Manuscripts Division, Department of Rare
Books and Special Collections, Princeton
University Library; reproduced courtesy of
Princeton University