Affiliations: Department of Computer Science, The University of
Auckland, Private Bag 92019, Auckland, New Zealand.
cristian@cs.auckland.ac.nz | Faculty of Mathematics and Computer Science, The
University of Bucharest, Str. Academiei 14, Bucharest, Romania.
rud@funinf.cs.unibuc.ro
Note: [] Address for correspondence: Department of Computer Science, The
University of Auckland, Private Bag 92019, Auckland, New Zealand
Abstract: Gödel's incompleteness theorem states that every
finitely-presented, consistent, sound theory which is strong enough to include
arithmetic is incomplete. In this paper we present elementary proofs for three
axiomatic variants of Gödel's incompleteness theorem and we use them (a)
to illustrate the idea that there is more than "complete vs. incomplete" there
are degrees of incompleteness, and (b) to discuss the implications of
incompleteness and computer-assisted proofs for Hilbert's Programme. We argue
that the impossibility of carrying out Hilbert's Programme is a thesis and has
a similar status to the Church-Turing thesis.
