What is metamathematics? Cantor's theory of infinite sets. Russell on the paradoxes. Hilbert on formal systems. Gödel's incompleteness theorem. Turing on uncomputability. My work on randomness & complexity. Is mathematics quasi-empirical?... The computer & programming languages were invented by logicians as the unexpected by-product of their unsuccessful effort to formalize reasoning completely. Formalism failed for reasoning, but it succeeded brilliantly for computation. In practice, programming requires more precision than proving theorems!... Each step Gödel ⇒ Turing ⇒ Chaitin makes incompleteness seem more natural, more pervasive, more ubiquitous—and much more dangerous!

*
*

Independently an earlier revolution, the statistical viewpoint, has continued, and now almost all physics, classical or modern, is statistical. And we are at the beginning of yet another conceptual shift in physics, the emphasis on chaos and complexity, where we realize that everyday objects, a dripping faucet, a compound pendulum, the weather, can behave in a very complicated and unpredictable fashion.

What's not much known by outsiders is that the world of pure mathematics hasn't been spared, it's not immune. We've had our crises too. Outsiders may think that mathematics is static, eternal, perfect, but in fact this century has been marked by a great deal of anguish, hand-wringing, heartache and controversy regarding the foundations of mathematics, regarding its most basic tenets, regarding the nature of mathematics and what is a valid proof, regarding what kinds of mathematical objects exist and how mathematics should be done.

In fact, there is a new field of mathematics called
*metamathematics,* in which you attempt to use mathematical
methods to discuss what mathematics can and cannot achieve, and to
determine what is the power and what are the limitations of
mathematical reasoning. In metamathematics, mathematicians examine
mathematics itself through a mathematical microscope. It's like the
self-analysis that psychiatrists are supposed to perform on
themselves. It's mathematics looking at itself in the mirror, asking
what it can do and what it can't do.

In this book I'm going to tell you the story of this century's controversies regarding the foundations of mathematics. I'm going to tell you why the field of metamathematics was invented, and to summarize what it has achieved, and the light that it sheds—or doesn't—on the fundamental nature of the mathematical enterprise. I'm going to tell you the extent to which metamathematics clarifies how mathematics works, and how different it is or isn't from physics and other empirical sciences. I and a few others feel passionately about this.

It may seem tortured, it may seem defeatist for mathematicians to question the ability of mathematics, to question the worth of their craft. In fact, it's been an extraordinary adventure for a few of us. It would be a disaster if most mathematicians were filled with self-doubt and questioned the basis for their own discipline. Fortunately they don't. But a few of us have been able to believe in and simultaneously question mathematics. We've been able to stand within and without at the same time, and to pull off the trick of using mathematical methods to clarify the power of mathematical methods. It's a little bit like standing on one leg and tying yourself in a knot!

And it has been a surprisingly dramatic story. Metamathematics was promoted, mostly by Hilbert, as a way of confirming the power of mathematics, as a way of perfecting the axiomatic method, as a way of eliminating all doubts. But this metamathematical endeavor exploded in mathematicians' faces, because, to everyone's surprise, this turned out to be impossible to do. Instead it led to the discovery by Gödel, Turing and myself of metamathematical results, incompleteness theorems, that place severe limits on the power of mathematical reasoning and on the power of the axiomatic method.

So in a sense, metamathematics was a fiasco, it only served to deepen
the crisis that it was intended to resolve. But this self-examination
**did** have wonderful and totally unexpected consequences in an
area far removed from its original goals. It played a big role in the
development of the most successful technology of our age, the
computer, which after all is just a mathematical machine, a machine
for doing mathematics. As E.T. Bell put it, the attempt to soar above
mathematics ended in the bowels of a computer!

So metamathematics did not succeed in shoring up the foundations of mathematics. Instead it led to the discovery in the first half of this century of dramatic incompleteness theorems. And it also led to the discovery of fundamental new concepts, computability & uncomputability, complexity & randomness, which in the second half of this century have developed into rich new fields of mathematics.

That's the story I'm going to tell you about here, and it's one in which I'm personally involved, in which I'm a major participant. So this will not be a disinterested historian's objective account. This will be a very biased and personal account by someone who was there, fighting in the trenches, shedding blood over this, lying awake in bed at night without being able to sleep because of all of this!!

What provoked all this? Well, a number of things. But I think it's fair to say that more than anything else, the crisis in the foundations of mathematics in this century was set off by G. Cantor's theory of infinite sets. Actually this goes back to the end of the previous century, because Cantor developed his theory in the latter decades of the 19th century. So let me start by telling you about that.

And he asked himself, ``Why don't we add another number after all of these? Let's call it ω!'' That's the lowercase Greek letter omega, the last letter of the Greek alphabet. So now we've got this:

But of course we won't stop here. The next number will be ω+1, then comes ω+2, etc. So now we've got all this:

And what comes after ω+1, ω+2, ω+3, ... ? Well, says Cantor, obviously 2ω, two times ω!

Then we continue as before with 2ω+1, 2ω+2, etc. Then what comes? Well, it's 3ω.

So, skipping a little, we continue with 4ω, 5ω, etc. Well, what comes after all of that? Says Cantor, it's ω squared!

Then we eventually have ω cubed, ω to the fourth power, etc.

Then what? Well, says Cantor, it's ω raised to the power ω!

Then a fair distance later, we have this:

Then much later we start having trouble naming things, because we have
ω raised to the ω an infinite number of times.
This is called *epsilon* nought.

It's the smallest solution of the equation

Well, you can see that this is strong stuff! And as disturbing as it
is, it's only half of what Cantor did. He also created another set of
infinite numbers, the **cardinal** numbers, which are harder to
understand. I've shown you Cantor's **ordinal** numbers, which
indicate positions in infinite lists. Cantor's cardinal numbers
measure the size of infinite sets. A set is just a collection of
things, and there's a rule for determining if something is in the set
or not. [*Note for experts:* To simplify matters, I'm assuming
the generalized continuum hypothesis.]

Cantor's first infinite cardinal is *aleph* nought

which measures the size of the set of natural numbers (non-negative integers). ℵ is the first letter of the Hebrew alphabet. Then comes ℵ one

which measures the size of the set of all subsets of the natural numbers, which turns out to be the same as the size of the set of all real numbers, numbers like π = 3.1415926... Then comes ℵ two

which measures the size of the set of all subsets of the set of all subsets of the natural numbers. Continuing in this manner, you get

Then you take the union of the set of natural numbers with the set of all its subsets, with the set of all the subsets of the set of all its subsets, etc., etc. How big is this set? Well, its size is

Proceeding in this manner, we get bigger and bigger cardinal numbers,
and you'll notice that the subscripts of Cantor's **cardinal**
numbers are precisely all of Cantor's **ordinal** numbers! So,
far, far away in never-never land, is a **very** big cardinal
number

that's used to measure the size of very big sets indeed!

So you see, Cantor invented his ordinal numbers to have names for his cardinal numbers, to have names for how big infinite sets can be.

Well, you can see that this is an outstanding feat of the imagination,
but is it mathematics? Do these things really exist? The reactions
of Cantor's contemporaries were extreme: they either **liked** it
very much or they **disliked** it very much! ``No one shall expel
us from the paradise which Cantor has created for us!'' exclaimed
David Hilbert, an outstanding German mathematician. On the other
hand, an equally distinguished French mathematician, Henri
Poincaré, declared that ``Later generations will regard set
theory as a disease from which one has recovered!'' Many admired
Cantor's audacity, and the extreme generality and abstractness he had
achieved. But the reaction of many others can be summarized in the
phrase ``That's not mathematics, it's theology!'' (which was actually
a reaction to some very non-constructive work of Hilbert's, not to
Cantor's theory).

It didn't help matters that some very disturbing paradoxes began to emerge. These were cases in which apparently valid set-theoretic reasoning led to conclusions that were obviously false. ``Set theory isn't sterile, it engenders paradoxes!'' gloated Poincaré.

The most famous, or infamous, of these paradoxes was discovered by the English philosopher Bertrand Russell, which Gödel later described as the discovery of ``the amazing fact that our logical [and mathematical] intuitions are self-contradictory.'' Let me tell you how Russell did it.

So why, Russell asked himself, do things fall apart when you apply to
the universal set Cantor's proof that the set of all subsets of a
given set is bigger than the original set? Russell analyzed Cantor's
proof as it applies to the universal set. He discovered that in this
special case the key step in Cantor's proof is to consider **the set
of all sets that are not members of themselves**. The key step in
the proof is to ask if this set is a member of itself or not. The
problem is that neither answer can be correct, because it's a member
of itself iff (if and only if) it's not a member of itself!

Maybe some examples will help. The set of all thinkable concepts is a thinkable concept, and therefore a member of itself, but the set of all red cows is not a red cow!

It's like the paradox of the village barber who shaves every man in the village who doesn't shave himself. But then who shaves the barber?! He shaves himself iff (if and only if) he doesn't shave himself. Of course, in the case of the barber, there is an easy way out. We either deny the existence of such a barber, for he can't apply the rule to himself, or else the barber must be female! But what can be wrong with Russell's set of all sets that are not members of themselves?

The Russell paradox is closely related to a much older paradox, the
liar paradox, which is also called the Epimenides paradox and goes
back to classical Greece. That's the paradox **``This statement is
false!''** It's true iff it's false, and therefore it's neither true
nor false!

Clearly, in both cases the paradox arises in some way from a self-reference, but outlawing all self-reference would be throwing out the baby with the bath water. In fact, self-reference will play a fundamental role in the work of Gödel, Turing, and my own that I'll describe later. More precisely, Gödel's work is related to the liar paradox, and Turing's work is related to the Russell paradox. My work is related to another paradox that Russell published, which has come to be called the Berry paradox.

What's the Berry paradox? It's the paradox of **the first natural
number that can't be named in less than fourteen words**. The
problem is that I've just named this number in thirteen words! (Note
that the existence of this number follows from the fact that only
finitely many natural numbers can be named in less than fourteen
words.)

This paradox is named after G.G. Berry, who was a librarian at Oxford
University's Bodleian library (Russell was at Cambridge University),
because Russell stated in a footnote that this paradox had been
suggested to him in a letter from Berry. Well, the Mexican
mathematical historian Alejandro Garciadiego has taken the trouble to
find that letter, and it's a rather different paradox. Berry's letter
actually talks about **the first ordinal that can't be named in a
finite number of words**. According to Cantor's theory such an
ordinal must exist, but we've just named it in a finite number of
words, which is a contradiction.

These details may not seem too interesting to you, but they're
tremendously interesting to me, because I can see the germ of my work
in Russell's version of the Berry paradox, but I can't see it at all
in Berry's original version.
[Why not? Well, to repeat, Russell's version is along the lines of
``the first positive integer that can't be named in less than a
billion words'' and Berry's version is ``the first transfinite Cantor
ordinal that can't be named in a finite number of words''. First of
all, in the Russell version for the first time we look at **precisely
how long a text it takes to specify something** (which is close to
how large a program it takes to specify it via a computation, which is
program-size complexity). The Berry version is just based on the fact
that there are a countable (ℵ_{0}) infinity of English texts, but
uncountably many transfinite ordinals. So Russell looks at the exact
size of a text, while Berry just cares if it's finite or not.
Second, Russell is looking at the descriptive
complexity of integers, which are relatively down-to-earth objects
that you can have on the computer, while Berry is looking at
**extremely big** transfinite ordinals, which are much more
theological objects, they're totally nonconstructive. In particular,
Berry's ordinals are **much bigger** than all the ordinals that I
showed you in the previous section, which we certainly named in a
finite number of words... I hope this explanation is helpful!]

What was to be done? One reaction, or over-reaction, was to advocate a retreat to older, safer methods of reasoning. The Dutch mathematician L.E.J. Brouwer advocated abandoning all non-constructive mathematics. He was in favor of more concrete, less ``theological'' mathematics.

For example, sometimes mathematicians prove that something exists by
showing that the assumption that it doesn't exist leads to a
contradiction. This is often referred to in Latin and is called an
existence proof via *reductio ad absurdum*, by reduction to an
absurdity.

``Nonsense!'' exclaimed Brouwer. The only way to prove that something exists is to exhibit it or to provide a method for calculating it. One may not actually be able to calculate it, but in principle, if one is very patient, it should be possible.

And the paradoxes led some other mathematicians to distrust arguments
in words and flee into formalism. The paradoxes led to increased
interest in developing symbolic logic, in using artificial formal
languages instead of natural languages to do mathematics. The Italian
logician G. Peano went particularly far in this direction. And
Russell and A.N. Whitehead in their monumental 3-volume *Principia
Mathematica*, in attempting to follow Peano's lead, took an entire
volume to deduce that 1 + 1 is equal to 2! They broke the argument
into such tiny steps that a volume of symbols and words was necessary
to show that 1 + 1 = 2!
[They defined numbers in terms of sets, and sets in terms of logic,
so it took them a long time to get to numbers.]
A magnificent try, but considered by most
people to be an unsuccessful one, for a number of reasons.

At this point Hilbert enters the scene, with a dramatic proposal for a ``final solution.'' What was Hilbert's proposal? And how could it satisfy everyone?

Hilbert had a two-pronged proposal to save the day. First, he said,
let's go all the way with the axiomatic method and with mathematical
formalism. Let's eliminate from mathematics all the uncertainties and
ambiguities of natural languages and of intuitive reasoning. Let's
create an artificial language for doing mathematics in which the rules
of the game are so precise, so complete, that there is absolutely no
uncertainty whether a proof is correct. In fact, he said, it should
be completely mechanical to check whether a proof obeys the rules,
because these rules should be completely syntactic or structural, they
should not depend on the semantics or the meaning of mathematical
assertions! In other words—words that Hilbert didn't use, but that
we can use now—there should be a **proof-checking algorithm**, a
computer program for checking whether or not a proof is correct.

That was to be the first step, to agree on the axioms—principles
accepted without proof—and on the rules of inference—methods for
deducing consequences (theorems) from these axioms—for **all** of
mathematics. And to spell out the rules of the game in excruciatingly
clear and explicit detail, leaving nothing to the imagination.

By the way, why are the axioms accepted without proof? The traditional answer is, because they are self-evident. I believe that a better answer is, because you have to stop somewhere to avoid an infinite regress!

What was the second prong of Hilbert's proposal?

It was that he would include unsafe, non-constructive reasoning in
his formal axiomatic system for all of mathematics, like existence
proofs via *reductio ad absurdum.* But, then, using intuitive,
informal, safe, constructive reasoning **outside** the formal
system, he would prove to Brouwer that the unsafe traditional methods
of reasoning Hilbert allowed in his formal axiomatic system could
never lead to trouble!

In other words, Hilbert simultaneously envisioned a complete formalization of all of mathematics as a way of removing all uncertainties, and as a way of convincing his opponents using their own methods of reasoning that Hilbert's methods of reasoning could never lead to disaster!

So Hilbert's program or plan was extremely ambitious. It may seem mad
to entomb all of mathematics in a formal system, to cast it in
concrete. But Hilbert was just following the axiomatic formal
tendency in mathematics and taking advantage of all the work on
symbolic logic, on reducing reasoning to calculation. And the key
point is that once a branch of mathematics has been formalized, then
it becomes a fit subject for **metamathematical** investigation.
For then it becomes a combinatorial object, a set of rules for playing
with combinations of symbols, and we can use mathematical methods to
study what it can and cannot achieve.

This, I think, was the main point of Hilbert's program. I'm sure he
didn't think that **``mathematics is a meaningless game played with
marks of ink on paper''**; this was a distortion of his views. I'm
sure he didn't think that in their normal everyday work mathematicians
should get involved in the minutiae of symbolic logic, in the tedium
of spelling out **every** little step of a proof. But once a
branch of mathematics is formalized, once it is desiccated and
dissected, then you can put it under a mathematical microscope and
begin to analyze it.

This was indeed a magnificent vision! Formalize all of mathematics.
Convince his opponents with their own methods of reasoning to accept
his! How grand!... The only problem with this fantastic scheme, which
most mathematicians would probably have been happy to see succeed, is
that it turned out to be impossible to do. In fact, in the 1930s
K. Gödel and A.M. Turing showed that it was impossible to
formalize all of mathematics. Why? Because essentially **any**
formal axiomatic system is either inconsistent or incomplete.

Inconsistency and incompleteness sound bad, but what exactly do they
mean? Well, here are the definitions that I use.
``**Inconsistent**'' means proves false theorems, and
``**incomplete**'' means doesn't prove all true theorems. (For
reasons that seemed pressing at the time, Hilbert, Gödel & Turing
used somewhat different definitions. Their definitions are syntactic,
mine are semantical.)

What a catastrophe! If mathematics can't be formalized, if no finite set of axioms will suffice, where does that leave mathematical certainty? What becomes of mathematical truth? Everything is uncertain, everything is left up in the air!

Now I'm going to tell you how Gödel and Turing arrived at this astonishing conclusion. Their methods were very different.

Gödel began with the liar paradox, **``This statement is
false!''** If it's true, then it's false. If it's false, then it's
true. So it can neither be true nor false, which is not allowed in
mathematics. As long as we leave it like this, there's not much we
can do with it.

But, Gödel said, let's change things a little. Let's consider
**``This statement is unprovable!''** It's understood that this
means in a particular formal axiomatic system, from a particular set
of axioms, using a particular set of rules of inference. That's the
context for this statement.

Well, there are two possibilities. Either this statement is a theorem, is provable, or it isn't provable, it's not a theorem. Let's consider the two cases.

What if Gödel's statement is provable? Well, since it affirms that it itself is unprovable, then it's false, it does not correspond with reality. So we're proving a false statement, which is very, very bad. In other words, if this statement is provable, then our formal axiomatic system is inconsistent, it contains false theorems. That's very, very bad! If we can deduce false results, then our theory is useless. So let's assume this can't happen.

So, by hypothesis, Gödel's statement is unprovable. But that's not so good either, because then it's a true statement (in the sense that it corresponds with reality) that's unprovable. So our formal axiomatic theory is incomplete!

So we're in serious trouble either way! Either our theory proves
false results, or, the lesser of two evils, it can't prove true
results! Either it's inconsistent or incomplete! *Kaput!*

A technical remark: One of the complications in Gödel's proof is that for reasons that are now only of historical interest he used different definitions of consistency and completeness than the ones that I'm using here.

Two other problems: First, what kind of mathematical theory talks about whether statements are provable or not? That's metamathematics, not mathematics! Second, how can a mathematical statement refer to itself?!

Well, Gödel very cleverly numbers the symbols, the meaningful
statements (the so-called ``well-formed formulas'', wffs!), and the
axioms and proofs in a formal axiomatic system. In this manner he
converts the assertion that a specific proof establishes a specific
theorem into an arithmetical assertion. He converts it into the fact
that a certain natural number (the Gödel number of the proof) stands in a
certain very complicated numerical relationship with another natural number
(the Gödel number of the theorem). In other words, Gödel
expresses ``*x* proves *y*'' arithmetically.

This is very clever, but the basic idea, that a mathematical statement
can also be considered to be a positive integer, does not seem too
surprising today. After all, everything, every character string, is
expressed numerically in modern computers. In fact, a string of
*N* characters is just an *N*-digit number base-256, or an
8*N*-bit number base-two! It's just a great big number! So
Gödel numbering is a lot easier to understand now than it was in
the 1930s.

But one part of Gödel's proof that isn't easier to understand now
is the self-reference. **``This statement is unprovable!''** How
can a mathematical statement refer to itself? This requires major
cleverness. The idea is that the statement doesn't refer to itself
directly, by containing a quoted copy of itself. It can't! Instead
it refers to itself indirectly, by saying that if you carry out a
certain procedure, if you do a certain calculation, then the result is
a statement that can't be proved. And lo and behold, it turns out
that the statement asserts that it itself is unprovable! The
statement refers to itself, it contains itself indirectly, by calculating
itself.

The final result is that Gödel constructs a statement in Peano arithmetic that affirms its unprovability. It's a lot of hard work, very hard work! Peano arithmetic is just the standard formal axiomatic theory dealing with the natural numbers 0, 1, 2, ... and with addition, multiplication and equality, with plus +, times, and =.

But if you read his original 1931 paper with the benefit of hindsight,
you'll see that Gödel is programming in LISP, he just didn't
realize that he was doing it. So later on in this book I'll go
through the details using LISP, which is my favorite programming
language for theoretical work. If you work with LISP instead of Peano
arithmetic, then things are very easy. So in Chapter III I'll show
you how to construct a LISP expression that's
a **fixed point**, i.e., yields itself as its value. Then using
the same idea I'll put together a statement in LISP
that asserts that it's unprovable. That'll be in Chapter III,
after we learn LISP in Chapter II.

Now let's get back to Gödel. What effect did Gödel's incompleteness theorem have? How was it received by his contemporaries? What did Hilbert think?

Well, according to Gödel's biographer John Dawson, Hilbert and
Gödel never discussed it, they never spoke to each other. The
story is so dramatic that it resembles fiction. They were both at a
meeting in Königsberg in September 1930. On September 7th
Gödel off-handedly announced his epic results during a
round-table discussion. Only von Neumann immediately grasped their
significance. [This announcement is item *1931a* in volume 1 of
Gödel's *Collected Works.* See also Dawson's introductory
note for *1931a*.]

*The very next day,* September 8th, Hilbert delivered his famous
lecture on ``Logic and the understanding of nature.'' As is
touchingly described by Hilbert's biographer Constance Reid, this was
the grand finale of Hilbert's career and his last major public
appearance. Hilbert's lecture ended with his famous words: ``*Wir
müssen wissen. Wir werden wissen.*'' We must know! We shall
know!

Hilbert had just retired, and was an extremely distinguished emeritus
professor, and Gödel was a twenty-something unknown. They did
not speak to each other then, or ever. (Later I was luckier than
Gödel was with Hilbert, for I at least got to talk with
Gödel on the phone! This time I was the twenty-something unknown
and **he** was the famous one. [I tell this story in my lecture
``The Berry paradox'' published in the first issue of
*Complexity* magazine in 1995.])

But the general reaction to Gödel, once the message sank in, was shock! How was it possible!? Where did this leave mathematics? What happens to the absolute certainty that mathematics is supposed to provide? If we can never have all the axioms, then we can never be sure of things. And if we try adding new axioms, since there are no guarantees and the new axioms may be false, then math becomes like physics, which is tentative and subject to revision! If the fundamental axioms change, then mathematical truth is time dependent, not perfect, static and eternal the way we thought!

Here is the reaction of the well-known mathematician Hermann Weyl: ``[W]e are less certain than ever about the ultimate foundations of (logic and) mathematics... we have our `crisis'... it directed my interests to fields I considered relatively `safe,' and has been a constant drain on the enthusiasm and determination with which I pursued my research work.''

But with time a funny thing happened. People noticed that in their normal everyday work as mathematicians you don't really find results that state that they themselves are unprovable. And so mathematicians carried on their work as before, ignoring Gödel. The places where you get into trouble seemed too remote, too strange, too atypical to matter.

But only five years after Gödel, Turing found a deeper reason for incompleteness, a different source of incompleteness. Turing derived incompleteness from uncomputability. So now let me tell you about that.

The first thing that Turing did in his paper was to invent the general-purpose programmable digital computer. He did it by inventing a toy computer, a mathematical model of a computer called the Turing machine, not by building actual hardware (though he worked on that later). But it's fair to say that the computer was invented by the English mathematician/logician Alan Turing in the 1930s, years before they were actually built, in order to help clarify the foundations of mathematics. Of course there were many other sources of invention leading to the computer; history is always very complicated. That Turing deserves the credit is as true, or truer, than many other historical ``truths.''

(One of the complications is that Turing wasn't the only inventor of what is now called the Turing machine. Emil Post came up with similar ideas independently, a fact known only to specialists.)

How does Turing explain the idea of a digital computer? Well, according to Turing the computer is a very flexible machine, it's soft hardware, it's a machine that can simulate any other machine, if it's provided with a description of the other machine. Up to then computing machines had to be rewired in order to undertake different tasks, but Turing saw clearly that this was unnecessary.

Turing's key idea is his notion of a **universal** digital machine.
I'll have much more to say about this key notion of ``computational
universality'' later. Now let's move on to the next big contribution
of Turing's 1936 paper, his discussion of the halting problem.

What is the halting problem? Well, now that Turing had invented the
computer, he immediately asked if there was something that can't be
done using a computer, something that no computer can do. And he
found it right away. There is no algorithm, no mechanical procedure,
no computer program that can determine in advance if **another**
computer program will ever halt. The idea is that before running a
program *P*, in order to be sure that *P* will eventually
stop, it would be nice to be able to give *P* to a halting
problem program *H*. *H* decides whether *P* will halt
or not. If *H* says that *P* halts, then we run *P*.
Otherwise, we don't.

Why, you may ask, is there a problem? Just run the program *P*
and see if it halts. Well yes, it's easy to decide if a program halts
in a fixed amount of time by running it for that amount of time. And
if it does halt, eventually we can discover that. The problem is how
to decide that it never halts. You can run *P* for a million
years and give up and decide that it will never halt just five minutes
before it was going to!

(Since there's no time limit the halting problem is a theoretical problem, not a practical problem. But it's also a very concrete, down-to-earth problem in a way, because we're just trying to predict if a machine will eventually do something, if something eventually happens. So it's almost like a problem in physics!)

Well, it would be nice to have a way to avoid running bad programs that get stuck in a loop. But here is Turing's proof that there's no way to do it, that it's uncomputable.

The proof, which I'll give in detail in Chapter IV in LISP, will be a
*reductio ad absurdum.* Let's assume that we have a way to solve
the halting problem. Let's assume that we have a subroutine *H*
that can take any program *P* as input, and that *H* returns
``will halt'' or ``never halts'' and always gets it right.

Then here's how we get into trouble with this halting problem
subroutine *H.* We put together a computer program *P*
that's self-referential, that calculates itself. We'll do this by
using the same self-reference trick that I use in Chapter III to prove
Gödel's theorem. Once this program *P* has calculated
itself, *P* uses the halting problem subroutine *H* to
decide if *P* halts. Then, just for the heck of it, *P*
does the **opposite** of what *H* predicted. If *H* said
that *P* would halt, then *P* goes into an infinite loop,
and if *H* said that *P* wouldn't halt, then *P*
immediately halts. And we have a contradiction, which shows that the
halting problem subroutine *H* cannot exist.

And that's Turing's proof that something very simple is uncomputable.
The trick is just self-reference—it's like Russell's set of all sets
that are not members of themselves. The
paradoxical program *P* halts iff it doesn't! And the trick
that enables *P* to calculate itself is the same fixed-point
construction that we'll use in Chapter III. It's
a LISP expression that gives itself as its
value.

So that's all there is to it, that's Turing's proof of the
unsolvability of the halting problem! That's how it's stated, but
it's really the **uncomputability** of the halting problem. And
from this Turing immediately deduces as a corollary that not only is
there no way to compute whether an arbitrary program will ever halt,
there's also no way to use a formal axiomatic system to settle the
matter. Why not?

Well, let's assume the opposite of what we want to prove and derive a contradiction.

If we could always **prove** whether individual programs halt or
not, that would give us a way to **compute** whether an arbitrary
program *P* eventually halts. How? By running through all
possible proofs in size order and applying Hilbert's proof-checking
algorithm to each one until we find a proof that *P* halts or a
proof that *P* never will. We just look through all possible
proofs in size order, one character long, two, three, etc., until we
settle the matter!

Of course, in practice this would be very, very slow! But it would
work in principle, and Turing has shown that it **can't**. Hence
if a formal axiomatic system with a proof-checking algorithm
*à la* Hilbert only proves true theorems, then it can't
settle all instances of the halting problem. In other words, if it's
truthful, then the formal axiomatic system must be incomplete.

So that's how Turing derives incompleteness from uncomputability. The halting problem is uncomputable, therefore no finite set of axioms will do.

That's the negative part of Turing's famous paper. But there's also a
positive message. At that same time that Turing shows that any
formalism for reasoning is incomplete, he exhibits a universal
formalism for computing: the machine language of Turing machines. At
the same time that he gives us a better proof of Gödel's
incompleteness theorem, he gives us a way out. Hilbert's mistake was
to advocate **artificial languages for carrying out
proofs**. This doesn't work because of incompleteness, because
of the fact that every formal axiomatic system is limited in power.
But that's not the case with

Hilbert almost got it right. He advocated using artificial languages to avoid ambiguity, he espoused formalism. But it's not reasoning, it's computation where formalism has triumphed! Mathematicians today still use natural languages to express their proofs. But when they write a computer program they have to be much more careful than when they prove a theorem. As Bill Thurston put it, much more attention to detail is required to get a computer program to run properly than in writing up a proof for publication. That's where formalism is triumphant, in computing, not in reasoning!

Many of the logicians who worked in the first half of this century were actually the first inventors of programming languages. Gödel uses a scheme for expressing algorithms that is much like the high-level language LISP that we'll study in the next chapter. Turing employs a low-level machine language. Other logicians invented other programming formalisms, some of which are still used today, like combinators and the lambda calculus. So Hilbert's project succeeded brilliantly, but in formalizing computation, not deduction!

Two final comments on Turing's paper.

First of all, Wolfram on computational universality.

In a massive work in progress tentatively entitled *A New Kind of
Science*, the mathematical physicist Stephen Wolfram, the creator
of *Mathematica,* has assembled a great deal of experimental
evidence that almost any combinatorial system that isn't trivial is
computationally universal. I believe he refers to this as the
**ubiquity of universality**. I hope Wolfram publishes this soon;
he's been working on it for a decade.

By the way, *Mathematica* is an extremely high-level language for
doing mathematics. It does symbolic and numerical computations very
well. I think that Hilbert would have loved *Mathematica*—I
know I do—because in a funny way it carries out Hilbert's dream, as
much of it as was possible. It's a single formalism that encompasses
much of mathematics, including a lot of mathematical physics. It's a
system that ``knows'' a lot of mathematics. I would argue that it's a
substantial artificial intelligence, albeit an inhuman one. It
embodies only mathematical intelligence.

One final comment on Turing's paper. There's more in it. He discusses how to do analysis on the computer, how to calculate π, roots of equations, etc., etc. This shows that Turing was already thinking about numerical analysis. This is the subject dealing with the fact that in mathematics real numbers have infinite precision, but in the computer precision is finite. J.H. Wilkinson, a well-known numerical analyst, later worked with Turing. That's why the title of Turing's paper is ``On computable numbers...'' He was talking about computing real numbers, numbers like π that go on forever digit by digit.

In summary, quite a paper! It showed the completeness (universality)
of computing formalisms, it showed the incompleteness of deductive
formalisms, and it helped to start the field of numerical analysis,
which is practical, and the field of computable analysis, which
isn't... You can see how creative Turing was.... That's how he made
such a mess of his life—he was **too** creative, too original,
too unconventional, too unworldly.

Now let's turn to my work! Let's take a look at a completely different source of incompleteness, randomness.

Initially I'm interested in physics and astronomy, in fundamental physical theory like Einstein's theory, quantum mechanics, and cosmology. But to understand physics you need to know mathematics. So I start to study mathematics on my own. And I discover that there's a subject in math just as fundamental, just as mysterious, as relativity, the quantum, and cosmology: Gödel's theorem! As a result, I get stuck with Gödel in mathematics, and I never get back to physics.

What were my sources of inspiration? Well, there were many, many! Many things caught my eye.

At fifteen I get an idea for defining randomness or lack of structure
via incompressibility.
[I still remember the exact moment. I was in my first year at the
Bronx High School of Science, and I was trying to pass the entrance
exam to get into the Columbia University Science Honors Program, a
weekend and summer science enrichment program for talented children.
There was an essay question in the entrance exam, asking what
conclusions could one draw if one found a pin on the moon? A pin on
the moon!, I said to myself, that's artificial, not natural. Why?
Because it has pattern or structure, because a description of it can
be greatly compressed into a concise Turing machine program, and it
**therefore** cannot be accidental or random. And I described this
idea in my answer, passed the exam, and got into the Science Honors
Program... Recently, discussing this with Stephen Wolfram, it didn't
seem like such a good answer to me, because **any** phenomenon on
the moon that can be explained by scientific theory is **also**
compressible in this way, e.g., a crystal. But it was a good idea
anyway, even if it didn't answer the question in the exam!]
Look at all the *N*-bit strings, and ask what is the size of the
smallest program that calculates each one. Then the *N*-bit
strings that need the largest programs are the ones without structure
or pattern. Why? Because a concise computer program for calculating
something is like an elegant theory that explains something, and if
there is no concise theory, then the object has no explanation, no
pattern, it's just what it is and that's all; there's nothing
interesting about it, no unusual features that make it stand out.

And I begin to work on developing this idea. At eighteen I write my
first major paper. At nineteen it appears in the *ACM Journal,*
then just about the only theoretical computer science publication in
the world.

That paper is on the size of Turing machine programs, which are
measured in states, and binary programs, which are measured in bits.
Then I decide that binary programs should be ``self-delimiting.''
Cambridge University Press asks me to write the first book in their
series on theoretical computer science. Then I look at LISP programs,
which are measured in characters. I'm asked to write articles for
*Scientific American,* *La Recherche* &
*New Scientist*.
I'm asked to talk in Gödel's old classroom in the
Mathematics Institute at the University of Vienna...

And one thing leads to another, and when I look up to catch my breath, I have grey hair and I'm in my fifties. I've made some progress, yes, but I'm still trying to develop the same ideas, I'm still trying to understand what's really going on!

Enough reminiscing! Let's get down to business!

Now the most interesting thing about the idea of **program-size
complexity**, of measuring the complexity of something by the size
of the smallest program for calculating it, is that almost every
question you ask leads straight to incompleteness. Wherever you turn,
you immediately smash into a stone wall. Incompleteness turns up
everywhere in this theory!

For example, you **can't** calculate the program-size complexity of
anything, it's uncomputable. You can't even prove any lower bounds,
not if you're interested in the program-size complexity of a specific
object. (But you can prove upper bounds on its complexity, by
exhibiting programs that calculate it.) And even though **most**
bit strings turn out to be random and can't be compressed into small
programs, you can never be sure that a **particular** bit string is
random!

My incompleteness results are very different from Gödel's and
Turing's. First of all, in my case the connection is with the Berry
paradox, not with the liar paradox nor the Russell paradox. And
Gödel exhibits a **specific** assertion that's true but
unprovable. I can't do that. I can't exhibit specific true,
unprovable assertions. But I **can** show that there are a lot of
them out there. I can show that with overwhelmingly high probability
you can generate true, unprovable assertions just by tossing a coin.

The general flavor of my work is like this. You compare the complexity of the axioms with the complexity of the result you're trying to derive, and if the result is more complex than the axioms, then you can't get it from those axioms.

Now let's get down to the nitty gritty and begin to look at the incompleteness result that we'll study in more detail in Chapter V. I've picked it because it's my easiest incompleteness result. Before I can state it we need the following definition.

Let's call a program **elegant** if no smaller program written in
the same programming language has the same output. Here we're
thinking of a specific programming language. In fact, in Chapter V
it'll be LISP. But in LISP one talks about evaluating expressions
instead of running programs. Evaluating an expression yields its
value, not output. So if it's LISP we're talking about, we'll say
that a LISP expression is elegant if no smaller LISP expression has
the same value.

Okay, there have got to be a lot of elegant programs out there, infinitely many. Why? Because for any computational task, for any specific output, there must be at least one elegant program.

But what if you want to exhibit an elegant program? What if you want to prove that a specific program is elegant, that no smaller program has the same output?

Well, it turns out that you can't, it's impossible! The precise
result we'll get in Chapter V is this. If a formal axiomatic system
*A* has LISP program-size complexity *N*, then you can't use
*A* to prove that any LISP expression more than *N* + 356
characters long is elegant.

So *A* can only prove that finitely many expressions are elegant!

What's the LISP program-size complexity of a formal axiomatic system
*A*? Well, it's the size of a LISP subroutine that looks at a
proof, sees if it's correct, and either returns an error message or
the theorem established by the proof. In other words, it's the size
in LISP of *A*'s proof-checking algorithm.

How do I prove this incompleteness result?

Well, consider the self-referential LISP expression *B* (for
Berry) defined to be **the value of the first LISP expression larger
than B that can be proved to be elegant in A**.
You can easily write this expression

How does this expression *B* work? *B* has a fixed part
that's 356 characters and a variable part, the proof-checking
algorithm, that's *N* characters. *B* determines its own
size, *N* + 356, by adding 356 to the size of the proof-checking
algorithm. Then *B* uses the proof-checking algorithm to run
through all possible proofs in *A* in size order, until it finds
a proof that an expression *E* is elegant and *E*'s size is
greater than *N* + 356. Then *B* evaluates *E* and
returns the value of *E* as *B*'s value.

Okay, so *B* has **the same value as an elegant expression
E that's larger than B**. But that's impossible,
because it contradicts the definition of elegance! The only way out,
the only way to avoid a contradiction, is if the formal axiomatic
system

Note that we've got self-reference here, but it's rather weak. The
self-reference in the paradoxical LISP expression *B* that proves
my incompleteness theorem, is that *B* has to know it's own size.
You have to put the constant 356 in *B* by hand, that's how you
get this to work.

Also note that my approach makes incompleteness more natural, because you see how what you can do depends on the axioms. The more complex the axioms, the better you can do. To get more out, you have to put more in. To exhibit large elegant LISP expressions, you're going to need to use a very complicated formal axiomatic system.

Well, this has been a lot of work! We've looked at three completely different approaches to incompleteness. It's time to step back and think about what it all means.

What I think it all means is that mathematics is different from
physics, but it's not **that** different. I think that math is
**quasi-empirical**. It's different from physics, but it's more a
matter of degree than an all or nothing difference. I don't think
that mathematicians have a direct pipeline to God's thoughts, to
absolute truth, while physics must always remain tentative and subject
to revision. Yes, math is less tentative than physics, but they're
both in the same boat, because they're both human activities, and to
err is human.

Now physicists used to love it when I said this, and mathematicians either hated it and said I was crazy or pretended not to understand.

But a funny thing has happened. I'm not alone anymore.

Now there's a journal called *Experimental Mathematics*. At
Simon Fraser University in Canada there's a *Centre for Experimental
and Constructive Mathematics.* And Thomas Tymoczko has published
an anthology called *New Directions in the Philosophy of
Mathematics* with essays by philosophers, mathematicians and
computer scientists that he says support a quasi-empirical view of
math. I'm happy to say that two of my articles are in his book.

By the way, the name ``quasi-empirical'' seems to come from Imre Lakatos. He uses it in an essay in Tymoczko's anthology. I used to say that ``perhaps mathematics should be pursued somewhat more in the spirit of an experimental science,'' which is a mouthful. It's much better to say ``maybe math is quasi-empirical!''

And I've seen computer scientists do some things quasi-empirically.
They've added ** P** ≠

The computer has expanded mathematical experience so greatly, that in order to cope, mathematicians are behaving differently. They're using unproved hypotheses that seem to be true.

So maybe Gödel was right after all, maybe incompleteness is a serious business. Maybe the traditional view that math gives absolute certainty is false.

Enough talking! Let's do some computer programming!
[Readers who **hate** computer programming should skip
directly to Chapter VI.]