Gödel, Escher, Bach: An Eternal Golden Braid (75 page)

There are some subtle things going on here. You might ponder this, for instance: the number of steps involved in the calculation of
Bluediag
[N],for each
specific
value of N, is predictable—but the different methods of prediction cannot all be united into a
general
recipe for predict

ing the length of calculation of
Bluediag
[
N
]. This is an "infinite conspiracy", related to the Tortoise's notion of "infinite coincidences", and also to w-incompleteness. But we shall not trace out the relations in detail.

Cantor's Original Diagonal Argument

Why is this called a diagonal argument? The terminology comes from Cantor's original diagonal argument, upon which many other arguments (such as ours) have subsequently been based. To explain Cantor's original argument will take us a little off course, but it is worthwhile to do so. Cantor, too, was concerned with showing that some item is not in a certain list. Specifically, what Cantor wanted to show was that if a "directory" of real numbers were made, it would inevitably leave some real numbers out-so that actually, the notion of a complete directory of real numbers is a contradiction in terms.

It must be understood that this pertains not just to directories of finite size, but also to directories of infinite size. It is a much deeper result than the statement "the number of reals is infinite, so of course they cannot be listed in a finite directory". The essence of Cantor's result is that there are (at least) two distinct types of infinity: one kind of infinity describes how many entries there can be in an infinite directory or table, and another describes how many real numbers there are (i.e., how many points there are on a line, or line segment)-and this latter is "bigger", in the sense that the real numbers cannot be squeezed into a table whose length is described by the former kind of infinity. So let us see how Cantor's argument involves the notion of diagonal, in a literal sense.

Let us consider just real numbers between 0 and 1. Assume, for the sake of argument, that an infinite list could be given, in which each positive integer N is matched up with a real number r(N) between 0 and 1, and in which each real number between 0

and 1 occurs somewhere down the line. Since real numbers are given by infinite decimals, we can imagine that the beginning of the table might look as follows: r(1):

.
1

4

1

5

9

2

6

5

3

r(2):

.3

3

3

3

3

3

3

3

3

r(3):

.7

1

8

2

8

1

8

2

8

r(4):

.4

1

4

2

1

3

5

6

2

r(5):

.5

0

0

0

0

0

0

0

0

The digits that run down the diagonal are in boldface: 1, 3, 8, 2, 0.... Now those diagonal digits are going to be used in making a special real number
d
, which is between 0 and 1

but which, we will see, is not in the list. To make
d,
you take the diagonal digits in order, and change each one of them to some other digit. When you prefix this sequence of digits by a decimal point you have
d
. There are of course many ways of changing a digit to some other digit, and correspondingly many different
d
ś. Suppose for, example, that we
subtract 1 from the diagonal digits
(with the convention that 1 taken from 0 is 9). Then our number d will be:

.0 2 7 1 9 .

Now, because of the way we constructed it,

d'
s 1st digit is not the same as the 1st digit of r(1);
d'
s 2nd digit is not the same as the 2nd digit of r(2);
d'
s 3rd digit is not the same as the 3rd digit of r(3);

... and so on.

Hence,

d
is different from r(1);

d
is different from r(2);

d
is different from r(3);

... and soon.

In other words,
d
is not in the list!

What Does a Diagonal Argument Prove?

Now comes the crucial difference between Cantor's proof and our proofit is in the matter of what assumption to go back and undo. In Cantor's argument, the shaky assumption was that such a table could be drawn up. Therefore, the conclusion warranted by the construction of d is that no exhaustive table of reals can be drawn up after all-which amounts to saying that the set of integers is just not big enough to index the set of reals.

On the other hand, in our proof, we know that the directory of Blue BlooP programs can be drawn up-the set of integers is big enough to index the set of Blue BlooP programs.

So, we have to go back and retract some shakier idea which we used. And that idea is that
Bluediag
[N] is calculable by some program in BlooP. This is a subtle difference in the application of the diagonal method.

It may become clearer if we apply it to the alleged "List of All Great Mathematicians" in the Dialogue-a more concrete example. The diagonal itself is

"Dboups". If we perform the desired diagonal-subtraction, we will get "Cantor". Now two conclusions are possible. If you have an unshakable belief that the list is
complete
, then you must conclude that Cantor is not a Great Mathematician, for his name differs from all those on the list. On the other hand, if you have an unshakable belief that Cantor is a Great Mathematician, then you must conclude that the List of All Great Mathematicians is incomplete, for Cantor's name is not on the list! (Woe to those who have unshakable beliefs on both sides!) The former case corresponds to our proof that Bluediag [N] is not primitive recursive; the latter case corresponds to Cantorś proof that the list of reals is incomplete;

FIGURE 73. Georg Cantor

Cantor's proof uses a diagonal in the literal sense of the word. Other "diagonal" proofs are based on a more general notion, which is abstracted from the geometric sense of the word. The essence of the diagonal method is the fact of using one integer in two different ways-or, one could say,
using one integer on two different levels
-thanks to which one can construct an item which is outside of some predetermined list. One time, the integer serves as a
vertical
index, the other time as a
horizontal
index. In Cantor's construction this is very clear. As for the function
Bluediag
[N], it involves using one integer on two different levels-first, as a Blue Program index number; and second, as an input parameter.

The Insidious Repeatability of the Diagonal Argument

At first, the Cantor argument may seem less than fully convincing. Isn't there some way to get around it? Perhaps by throwing in the diagonally constructed number
d,
one might obtain an exhaustive list. If you consider this idea, you will see it helps not a bit to throw in the number d, for as soon as you assign it a specific place in the table, the diagonal method becomes applicable to the new table, and a new missing number d' can be constructed, which is not in the new table. No matter how many times you repeat the operation of constructing a number by the diagonal method and then throwing it in to make a "more complete" table, you still are caught on the ineradicable hook of Cantor’s method. You might even try to build a table of reals which tries to outwit the Cantor diagonal method by taking

the whole trick, lock, stock, and barrel, including its insidious repeatability, into account somehow. It is an interesting exercise. But if you tackle it, you will see that no matter how you twist and turn trying to avoid the Cantor "hook", you are still caught on it. One might say that any self-proclaimed "table of all reals" is hoist by its own petard.

The repeatability of Cantor's diagonal method is similar to the repeatability of the Tortoise's diabolic method for breaking the Crab's phonographs, one by one, as they got more and more "hi-fi" and-at least so the Crab hoped-more "Perfect". This method involves constructing, for each phonograph, a particular song which that phonograph cannot reproduce. It is not a coincidence that Cantor's trick and the Tortoise's trick share this curious repeatability; indeed, the Contracrostipunctus might well have been named

"
Cantorcrostipunctus
" instead. Moreover, as the Tortoise subtly hinted to the innocent Achilles, the events in the Contracrostipunctus are a paraphrase of the construction which Gödel used in proving his Incompleteness Theorem; it follows that the Gödel construction is also very much like a diagonal construction. This will become quite apparent in the next two Chapters.

From BlooP to FlooP

We have now defined the class of primitive recursive functions and primitive recursive properties of natural numbers by means of programs written in the language BlooP. We have also shown that BlooP doesn't capture all the functions of natural numbers which we can define in words. We even constructed an "unBlooPable" function, Bluediag [N], by Cantor's diagonal method. What is it about BlooP that makes Bluediag unrepresentable in it? How could BlooP be improved so that Bluediag became representable?

BlooP's defining feature was the boundedness of its loops. What if we drop that requirement on loops, and invent a second language, called "FlooP" (`F' for "free")?

FlooP will be identical to BlooP except in one respect: we may have loops without ceilings, as well as loops with ceilings (although the only reason one would include a ceiling when writing a loop-statement in FlooP would be for the sake of elegance). These new loops will be called
MU-LOOPS
. This follows the convention of mathematical logic, in which "free" searches (searches without bounds) are usually indicated by a symbol called a "µ-operator" (mu-operator). Thus, loop statements in FlooP may look like this:

MU-LOOP:

BLOCK n: BEGIN

.

.

BLOCK n: END

This feature will allow us to write tests in FlooP for such properties as wondrousness and the Tortoise property-tests which we did not know how to program in BlooP because of the potential open-endedness of the searches involved. I shall leave it to interested readers to write a FlooP test for wondrousness which does the following things: (1) If its input, N, is wondrous, the program halts and gives the answer
YES
.

(2) If N is unwondrous, but causes a closed cycle other than 1-4-2-1-4-2-1- ... , the program halts and gives the answer
NO
.

(3) If N is unwondrous, and causes an "endlessly rising progression", the program never halts. This is FlooP's way of answering by not answering. FlooP's nonanswer bears a strange resemblance to Joshu's nonanswer "
MU
".

The irony of case 3 is that
OUTPUT
always has the value
NO
, but it is always inaccessible, since the program is still grinding away. That troublesome third alternative is the price that we must pay for the right to write free loops. In all FlooP programs incorporating the
MU-LOOP
option, nontermination will always be one theoretical alternative. Of course there will be many FlooP programs which actually terminate for all possible input values. For instance, as I mentioned earlier, it is suspected by most people who have studied wondrousness that a FlooP program such as suggested above will always terminate, and moreover with the answer
YES
each time.

Terminating and Nonterminating FlooP Programs

It would seem extremely desirable to be able to separate FlooP procedures into two classes:
terminators
and
nonterminators
. A terminator will eventually halt no matter what its input, despite the "
MU
-ness" of its loops. A nonterminator will go on and on forever, for
at least one
choice of input. If we could always tell, by some kind of complicated inspection of a FlooP program, to which class it belonged, there would be some remarkable repercussions (as we shall shortly see). Needless to say, the operation of class-checking would itself have to be a terminating operation-otherwise one would gain nothing!

Turing's Trickery

The idea springs to mind that we might let a BlooP procedure do the inspection. But BlooP procedures only accept numerical input, not programs! However, we can get around that ... by coding programs into numbers! This sly trick is just Gödel-numbering in another of its many