Mr. Turing’s amazing machines - The Computing Universe: A Journey through a Revolution - page 104

Many years later, at the Bologna International Conference of Mathematicians
in 1928, Hilbert made this question more precise. In Andrew Hodges's words,
Hilbert's three questions were the following:

First, was mathematics complete, in the technical sense that every statement
(such as “every integer is the sum of four squares”) could either be proved or
disproved? Second, was mathematics consistent, in the sense that the statement
“2+2 = 5” could not be arrived at by a sequence of valid steps of proof ? And
thirdly, was mathematics decidable? By this he meant, did there exist a definite
method which could, in principle, be applied to any assertion, and which was
guaranteed to produce a correct decision as to whether that assertion was true. 5

Fig. 6.1. Who is going to shave the bar-
ber? Illustration of barber's paradox.

This last question came to be known as the decision problem - more often
known by its more intimidating German name as the Entscheidungsproblem.
Hilbert clearly believed that the answer to all of these questions would be
“yes” - but within a few years, Kurt Gödel ( B.6.4 ) had dealt Hilbert's newly
announced program a fatal blow.
Gödel was known for being extremely meticulous - in his secondary
school he was famous for never making a single grammatical error. He went
to the University of Vienna in 1924 and wrote his famous paper on the incom-
pleteness of mathematics in 1931. In that paper Gödel proved a startling result.
He showed that mathematics must be incomplete - in that there are statements
that can neither be proved nor disproved starting from a given set of axioms.
In order to prove this result, Gödel first showed how the rules of procedure of
any formal mathematical system, and the use of its axioms, could be encoded
as purely arithmetical operations. Having done this, Gödel was able to reduce
things like the property of “being a proof” or of “being provable” to arithmetic
statements. He could then construct arithmetical statements that referred to
themselves, rather like Russell's use of “sets of all sets” arguments. In particu-
lar, Gödel was able to construct a mathematical statement that effectively said
“This statement is unprovable.” The statement cannot be proved true , for this
would immediately be a contradiction. But similarly, it cannot be proved false ,
because this also leads to a contradiction. This is reminiscent of the famous liar
paradox: when a man says “I am lying,” is he telling the truth or not?
Gödel was also able to show that arithmetic could not be proved to be con-
sistent with just the use of its own axioms. In one remarkable paper, Gödel had
answered the first two questions of Hilbert's program in the negative! This left

B.6.4. Kurt Gödel (1906-78) with Albert Einstein in Princeton. John von Neumann had a
very high respect for Gödel and at Princeton he helped him to get a permanent position.
Allegedly he said “How can any of us be called professor when Gödel is not?” B1 Despite
their age difference, Einstein and Gödel were close friends. They used to walk together to
the Institute for Advanced Studies every morning and toward the end of his life, Einstein
remarked that “his own work no longer meant much, that he came to the Institute
merely to have the privilege of walking home with Gödel.” B2