Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

down. But this faith may be wrong. Perhaps every consistent formalization

of number theory which humans invent will imply the existence of super-

naturals, by being w-inconsistent. This is a queer thought, but it is conceiv-

able.

If this were the case-which I doubt, but there is no disproof avail-

able-then G would not have to be undecidable. In fact, there might be no

undecidable formulas of TNT at all. There could simply be one unbifur-

cated theory of numbers-which necessarily includes supernaturals. This is

not the kind of thing mathematical logicians expect, but it is something

which ought not to be rejected outright. Generally, mathematical logicians

believe that TNT-and systems similar to it-are w-consistent, and that the

Gode! string which can be constructed in any such system is undecidable

within that system. That means that they can choose to add either it or its

negation as an axiom.

Hilbert's Tenth Problem and the Tortoise

I would like to conclude this Chapter by mentioning one extension of

Godel's Theorem. (This material is more fully covered in the article "Hil-

bert's Tenth Problem" by Davis and Hersh, for which see the Bibliog-

raphy.) For this, I must define what a Diophantine equation is. This is an

equation in which a polynomial with fixed integral coefficients and expo-

nents is set to O. For instance,

a=O

and

5x + 13y - 1 = 0

and

5p5 + (^17) ql7 - 177 = 0
and
aI23.666.111.666 + bI23.666.111.666 _ CI23.666.111.666 = 0
are Diophantine equations. It is in general a difficult matter to know
whether a given Diophantine equation has any integer solutions or not. In
fact, in a famous lecture at the beginning of the century, Hilbert asked
mathematicians to look for a general algorithm by which one could deter-
mine in a finite number of steps if a given Diophantine equation has integer
solutions or not. Little did he suspect that no such algorithm exists!
On Formally Undecidable Propositions 459