Hilbert, Gödel, and Turing

The impact of Gödel's and Turing's breakthroughs in the 1930s is best understood against the background of the mathematical ambitions definitively expressed by David Hilbert in the 1920s (though foreshadowed in a famous address that he gave in 1900). Hilbert – founder of the "formalist" approach in Philosophy of Mathematics – advocated in 1921 that researchers' primary aim should be to establish mathematics on a solid and provably consistent foundation of axioms, from which, in principle, all mathematical truths could be deduced (by the standard methods of first order or "predicate" logic). Then in 1928 he formulated his Entscheidungsproblem or "decision problem": could an effective procedure be devised which would demonstrate – in a finite time – whether any given mathematical proposition was, or was not, provable from a given set of axioms?

Consistency, Completeness, and Decidability

Here we can see three distinguishable concerns. First, consistency: the set of axioms should be consistent, and provably so. Secondly, completeness: all mathematical truths should – in principle – be deducible from those axioms. Thirdly, decidability: there should be a clearly formulated procedure which is such that, given any statement of mathematics, it can definitively establish within a finite time whether or not that statement follows from the given axioms.

In formal treatments of these notions, they are standardly interpreted syntactically (i.e. in terms of the structural relationships between formulae) rather than semantically (i.e. in terms of truth and meaning). Thus understood, a consistent system is one in which it is never possible to prove both a proposition P and its negation not(P). And a complete system is one in which it is always possible to prove either P or not(P), for any proposition P that is expressible within the system. So consistency and completeness are closely related, and can be understood quite independently of the issue of whether or not the axioms are true and the rules valid (i.e. truth-preserving). If, however, we were able to achieve a consistent and complete system of arithmetic, with true axioms and valid rules, then any arithmetical proposition would be provable if, and only if, it is true. A major part of Hilbert's dream would thus be realised.

Gödel's Incompleteness Theorems

(This outline is very simplified – for more detail, see the Mind-Crafts introduction to Gödel's Theorem or the Apronus outline of Gödel's Theorem, or the Nagel and Newman book listed under Books on Philosophy and Theory of Computation.)

In a famous paper published in 1931, Gödel proved that in any true (and hence consistent) axiomatic theory sufficiently rich to enable the expression and proof of basic arithmetic propositions, it will be possible to construct an arithmetical proposition G such that neither G, nor its negation, is provable from the given axioms. Hence the system must be incomplete. This is known as Gödel's First Incompleteness Theorem. Moreover it follows from Gödel's reasoning that G must, in fact, be a true statement of arithmetic.

Gödel's proof ingeniously shows how statements about mathematical relationships (e.g. that a particular sequence of propositions provides a proof of some proposition P) can be encoded as statements within arithmetic. This encoding, moreover, is truth-preserving, so that the encoded "meta-mathematical" statement will be true if, and only if, the encoding statement of arithmetic is true. He then cleverly derives an arithmetical proposition G which encodes the statement that G itself is unprovable within the system. Now if G were false, then it would follow (from this encoding) that it was not unprovable: hence it would have to be provable within the system. But then, given the conditions of the encoding, its negation not(G) – which encodes the statement that G is provable – would itself have to be true and hence provable if the system is complete. It follows that if the system is complete, it cannot be consistent, since both G and not(G) would then be provable within it. Hence no system that is complete can also be consistent. QED.

Recall, now, that the system of axioms is in fact consistent: as we have just seen, it follows that the system cannot be complete, since neither G nor not(G) will be provable within it. But then it follows from the conditions of the encoding that G, which encodes the proposition that G is not provable, must after all be true!

Gödel's Second Incompleteness Theorem, also published in the same article, follows from the first. It states – in effect – that no consistent axiomatic theory sufficiently rich to enable the expression and proof of basic arithmetic propositions (and of basic results about formal provability) can prove its own consistency.

In outline, the Second Incompleteness Theorem follows from the first as follows, though making all this precise is deep and complex, requiring the rigorous formalisation of sophisticated informal notions. Suppose that a system were able to prove its own consistency. Then since statement G follows from the system's consistency, statement G must itself be provable within the system. But since G encodes the statement that G is unprovable within the system, we have a contradiction. It follows that the system cannot after all prove its own consistency.

Turing's Theorem

Gödel's incompleteness theorems left the Entscheidungsproblem as unfinished business. Although he had shown that any consistent axiomatic system of arithmetic would leave some arithmetical truths unprovable, this did not in itself rule out the existence of some "effectively computable" decision procedure which would infallibly, and in a finite time, reveal whether or not any given proposition P was, or was not, provable. Turing's landmark contribution, in his paper of 1936 "On Computable Numbers, with an Application to the Entscheidungsproblem", was to devise a rigorous notion of effective computability based on the "Turing Machine". He then showed that there exist problems – notably the famous "Halting Problem" for Turing Machines – that cannot be effectively computed by this means. That is, he proved the impossibility of devising a Turing Machine program that can determine infallibly (and within a finite time) whether or not a given Turing Machine T will eventually halt given some arbitrary input I.

Hence Turing proved that Hilbert's Entscheidungsproblem was unsolvable. Hilbert's dream was shattered: any consistent axiomatic theory sufficiently rich to enable the expression and proof of basic arithmetic propositions could be neither complete (as Gödel had shown) nor effectively decidable.

Kurt Gödel

Kurt Gödel

Proved fundamental incompleteness results