[ Pobierz całość w formacie PDF ]

real numbers. So, the concept of computable numbers,
Turing (A Novel about Computation) 127
and their inability to be listed, reveals the fatal flaw in
Hilbert s project.
To recapitulate: The Don contemplated the problem of
listing all computable real numbers, and he established
that it can t be done a modern version of Cantor s di-
agonal argument. But Hilbert s project, if brought to
fruition, would imply that computable numbers can be
listed. So, Hilbert s project is impossible. There is no
machine that proves all theorems.
But this implies something devastating about maths: It
must forever be incomplete. No matter how meticulously
we strive to axiomatise maths, how sophisticated and
ambitious the proof systems we design are, there will
always be gaps, statements that are true but unprov-
able. Because, if every conjecture has either a proof or a
disproof, then it would be possible to let a computer
loose on it to search for one or the other. So, there is no
axiom system that is good for all theorems.
 I am confused, Alexandros interrupts.  Didn t
Euclid provide axioms that prove all theorems in his
geometry? Was he wrong?
|
Good point. Euclidean geometry is a happy exception, a
mathematical system that is interesting and rich, and
still all its true sentences, all its theorems, have proofs
from five simple axioms. In fact, there is an algorithm
that can in principle prove or disprove any statement
in Euclidean geometry. And you know why Euclidean
geometry is so well behaved? The reason is that in
geometry you don t have whole numbers; your triangles
and circles float in the continuum of the plane.
But mathematical systems that deal with whole num-
bers are too powerful for their own good; they are ex-
128 Christos H. Papadimitriou
pressive enough to capture the Don s argument. Such
mathematical systems must be incomplete, must con-
tain theorems that are unprovable. Mathematicians
have to invent increasingly clever proofs to make prog-
ress, and they must always be on their toes, tortured
by insecurity not an altogether bad thing, if you
ask me.
But we have been reversing history here. This particular
implication of the Don s result, that all mathematical
systems must be incomplete, actually predated it. It
had been proved a couple of years earlier by another
young mathematician, Kurt Gödel, using a very differ-
ent method, one that did not involve computation and
code at least not in such a direct way. An ingenious
variant of Eubulides paradox. Remember? This state-
ment is false.
In fact, Kurt created a statement that says This statement
is unprovable. Think about it, this variant is even more
lethal than Eubulides . Because, presumably, in any
decent mathematical system you cannot express
Eubulides paradox; it would mean that the system is
nonsense, that you can write in it statements that are
neither true nor false. But if you have a mathematical
system that is expressive enough can talk about the
integers, for example then Kurt showed that in this
system you can write a statement that says exactly this:
Kurt s statement: Kurt s statement is unprovable. p. 257
He constructed it by a brilliant manoeuvre, his famous
Gödel number idea you can do it a million other ways,
of course, but his stuck. So, look at Kurt s statement,
Alexandros, is it true or false? Which one is a theorem,
Kurt s statement or its negation?
 I don t think I have enough information to tell.
Turing (A Novel about Computation) 129
|
Yes you do. Since Kurt s statement says that it s unprov-
able, there are only two possibilities: It is either true and
unprovable, or false and provable right? But the com-
bination of false and provable is terrible news: It means
the axiomatic system is inconsistent; it proves rubbish,
false statements. How can a false statement be prov-
able? So, if we further assume that our system is
consistent, then there is only one possibility: Kurt s
statement is true but unprovable. And this is Gödel s fa-
mous incompleteness theorem: Any consistent mathe-
matical system that includes the integers must be
incomplete: There must be perfectly true theorems in it
that are unprovable.
So, there you have it, the one-two punch that destroyed
Hilbert s dream, now told in its true historical sequence:
First Gödel proved that any mathematical system so-
phisticated enough to include the integers must be in-
complete in terrible ways. But this allowed for a ray of
hope: That, even though certain artificial, far-fetched
theorems like Kurt s may be unprovable, all other theo-
rems are provable; and perhaps we can construct a ma-
chine that discovers their proofs automatically. The
Don s argument destroyed this hope as well.
Depressing news, you may think. Actually, it was one of
the most fortunate, most productive moments in the his-
tory of science. From the ashes of Hilbert s dream, a new
world was born. Because, you see, in carrying out his
destructive plan, the Don had spelt out the details of
computation of his clumsy machines more clearly
and powerfully than anybody else before him. His [ Pobierz całość w formacie PDF ]