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

a very long Gödel number. For instance, the shortest BlooP function (which is also a terminating FlooP program)

DEFINE PROCEDURE "A" [B]:

BLOCK 0: BEGIN

BLOCK 0: END.

-would get the Godel number partially shown below:

904, 905, 906, 909, 914, 905

905, 914.904, 955,

D E F I N E

E N D .

Now our scheme would be to write a BlooP test called
TERMINATOR
? which says
YES
if its input number codes for a terminating FlooP program,
NO
if not. This way we could hand the task over to a machine and with luck, distinguish terminators from nonterminators. However, an ingenious argument given by Alan Turing shows that no BlooP program can make this distinction infallibly. The trick is actually much the same as Gödel’s trick, and therefore closely related to the Cantor diagonal trick. We shall not give it here-suffice it to say that the idea is to feed the termination tester its own Godel number. This is not so simple, however, for it is like trying to quote an entire sentence inside itself. You have to quote the quote, and so forth; it seems to lead to an infinite regress. However, Turing figured out a trick for feeding a program its own Godel number. A solution to the same problem in a different context will be presented next Chapter. In the present Chapter, we shall take a different route to the same goal, which is namely to prove that a termination tester is impossible. For readers who wish to see an elegant and simple presentation of the Turing approach, I recommend the article by Hoare and Allison, mentioned in the Bibliography.

A Termination Tester Would Be Magical

Before we destroy the notion, let us delineate just why having a termination tester would be a remarkable thing. In a sense, it would be like having a magical dowsing rod which could solve all problems of number theory in one swell FlooP. Suppose, for instance, that we wished to know if the Goldbach Variation is a true conjecture or not. That is, do all numbers have the Tortoise property? We would begin by writing a FlooP test called
TORTOISE
? which checks whether its input has the Tortoise property. Now the defect of this procedure-namely that it doesn't terminate if the Tortoise property is absent-here turns into a virtue! For now we run the termination tester on the procedure
TORTOISE
?.

If it says
YES
, that means that
TORTOISE
? terminates for all values of its input-in other words, all numbers have the Tortoise property. If it says
NO
, then we know there exists a number which has the Achilles property. The irony is that we never actually
use
the program
TORTOISE
at all—we just inspect it.

This idea of solving any problem in number theory by coding it into a program and then waving a termination tester over the program is not unlike the idea of testing a khan for genuineness by coding it into a folded string and then running a test for Buddha-nature on the string instead. As

Achilles suggested, perhaps the desired information lies "closer to the surface" in one representation than in another.

Pool F, Index Numbers, and Green Programs

Well, enough daydreaming. How can we prove that the termination tester is impossible?

Our argument for its impossibility will hinge on trying to apply the diagonal argument to FlooP, just as we did to B1ooP. We shall see that there are some subtle and crucial differences between the two cases.

As we did for BlooP, imagine the pool of all FlooP programs. We shall call it

"Pool F". Then perform the same three filtering operations on Pool F, so that you get, in the end:

A complete pool of all call-less FlooP programs which calculate functions of exactly one input parameter.

Let us call these special FlooP-programs
Green Programs
(since they may go forever).

Now just as we assigned index numbers to all Blue Programs, we can assign index numbers to Green Programs, by ordering them in a catalogue, each volume of which contains all Green Programs of a fixed length, arranged in alphabetical order.

So far, the carry-over from BlooP to FlooP has been straightforward. Now let us see if we can also carry over the last part: the diagonal trick. What if we try to define a diagonal function?

Greendiag
[
N
] = 1 + Greenprogram{#
N
} [
N
]

Suddenly, there is a snag: this function
Greendiag
[
N
] may not have a well-defined output value for all input values
N.
This is simply because we have not filtered out the nonterminator programs from Pool F, and therefore we have no guarantee that we can calculate
Greendiag
[
N
] for all values of
N
. Sometimes we may enter calculations which never terminate. And the diagonal argument cannot be carried through in such a case, for it depends on the diagonal function having a value for all possible inputs.

The Termination Tester Gives Us Red Programs

To remedy this, we would have to make use of a termination tester, if one existed. So let us deliberately introduce the shaky assumption that one exists, and let us use it as our fourth filter. We run down the list of Green Programs, eliminating one by one all nonterminators, so that in the end we are left with:

A complete pool of all call-less FlooP programs which calculate functions of exactly one input parameter, and which terminate for all values of their input..

Let us call these special FlooP programs Red Programs (since they all must stop). Now, the diagonal argument will go through. We define

Reddiag
[N] = 1 + Redprogram(#N} [N]

and in an exact parallel to Bluediag, we are forced to conclude that
Reddiag
[N] is a well-defined, calculable function of one variable which is not in the catalogue of Red Programs, and is hence not even calculable in the powerful language FlooP. Perhaps it is time to move on to GlooP?

GlooP ...

Yes, but what is GlooP? If FlooP is BlooP unchained, then GlooP must be FlooP

unchained. But how can you take the chains off twice% How do you make a language whose power transcends that of FlooP? In
Reddiag
, we have found a function whose values we humans know how to calculate-the method of doing so has been explicitly described in English-but which seemingly cannot be programmed in the language FlooP.

This is a serious dilemma because no one has ever found any more powerful computer language than FlooP.

Careful investigation into the power of computer languages has been carried out.

We need not do it ourselves; let it just be reported that there is a vast class of computer languages all of which can be proven to have
exactly the same expressive power
as FlooP

does, in this sense: any calculation which can be programmed in any one of the languages can be programmed in them all. The curious thing is that almost any sensible attempt at designing a computer language ends up by creating a member of this class-which is to say, a language of power equal to that of FlooP. It takes some doing to invent a reasonably interesting computer language which is weaker than those in this class. BlooP

is, of course, an example of a weaker language, but it is the exception rather than the rule.

The point is that there are some extremely natural ways to go about inventing algorithmic languages; and different people, following independent routes, usually wind up creating equivalent languages, with the only difference being style, rather than power.

... Is a Myth

In fact, it is widely believed that there cannot be any more powerful -language for describing calculations than languages that are equivalent to FlooP. This hypothesis was formulated in the 1930's by two people, independently of each other: Alan Turing—about whom we shall say more later—and Alonzo Church, one of the eminent logicians of this century. It

is called the
Church-Turing Thesis
. If we accept the CT-Thesis, we have to conclude that

"GlooP" is a myth-there are no restrictions to remove in FlooP, no ways to increase its power by "unshackling" it, as we did BlooP.

This puts us in the uncomfortable position of asserting that
people
can calculate
Reddiag
[N] for any value of
N
, but there is no way to program a
computer
to do so. For, if it could be done at all, it could be done in FlooP-and by construction, it can't be done in FlooP. This conclusion is so peculiar that it should cause us to investigate very carefully the pillars on which it rests. And one of them, you will recall, was our shaky assumption that there is a decision procedure which can tell terminating from nonterminating FlooP

programs. The idea of such a decision procedure already seemed suspect, when we saw that its existence would allow all problems of number theory to be solved in a uniform way. Now we have double the reason for believing that any termination test is a myth-that there is no way to put FlooP programs in a centrifuge and separate out the terminators from the nonterminators.

Skeptics might maintain that this is nothing like a rigorous proof that such a termination test doesn't exist. That is a valid objection; however, the Turing approach demonstrates more rigorously that no computer program can be written in a language of the FlooP class which can perform a termination test on all FlooP programs.

The Church-Turing Thesis

Let us come back briefly to the Church-Turing Thesis. We will talk about it-and variations on it-in considerable detail in Chapter XVII; for now it will suffice to state it in a couple of versions, and postpone discussion of its merits and meanings until then. Here, then, are three related ways to state the CT-Thesis:

(1) What is human-computable is machine-computable.

(2) What is machine-computable is FlooP-computable.

(3) What is human-computable is FlooP-computable

(i.e., general or partial recursive).

Terminology: General and Partial Recursive

We have made a rather broad survey, in this Chapter, of some notions from number theory and their relations to the theory of computable functions. It is a very wide and flourishing field, an intriguing blend of computer science and modern mathematics. We should not conclude this Chapter without introducing the standard terminology for the notions we have been dealing with.

As has already been mentioned, “BlooP-computable” is synonymous with

“primitive recursive”. Now FlooP computable functions can be di-

vided into two realms: (1) those which are computable by
terminating
FlooP programs: these are said to be
general recursive
; and (2) those which are computable only by
nonterminating
FlooP programs: these are said to be partial recursive. (Similarly for predicates.) People often just say "recursive" when they mean "general recursive".

The Power of TNT

It is interesting that
TNT
is so powerful that not only are all primitive recursive predicates represented, but moreover all general recursive predicates are represented. We shall not prove either of these facts, because such proofs would be superfluous to our aim, which is to show that
TNT
is incomplete. If
TNT
could not represent some primitive or general recursive predicates, then it would be incomplete in an
uninteresting
way-so we might as well assume that it can, and then show that it is incomplete in an interesting way.

Air on G's String

The Tortoise and Achilles have just completed a tour of a porridge factory.

Achilles: You don't mind if I change the subject, do you? Tortoise: Be my guest.

Achilles: Very well, then. It concerns an obscene phone call I received a few days ago.

Tortoise: Sounds interesting.

Achilles: Yes. Well-the problem was that the caller was incoherent, at least as far as I could tell. He shouted something over the line and then hung up-or rather, now that I think of it, he shouted something, shouted it again, and then hung up.

Tortoise: Did you catch what that thing was?

Achilles: Well, the whole call went like this:

Myself
: Hello?

Caller (shouting wildly
): Yields falsehood when preceded by its quotation! Yields falsehood when preceded by its quotation!

(
Click
.)

Tortoise: That is a most unusual thing to say to somebody on an obscene phone call.

Achilles: Exactly how it struck me.

Tortoise: Perhaps there was some meaning to that seeming madness.

Achilles: Perhaps.

(They enter a spacious courtyard framed by some charming three-story stone
houses. At its center stands a palm tree, and to one side is a tower. Near the
tower there is a staircase where a boy sits, talking to a young woman in a
window.)

Tortoise: Where are you taking me, Achilles?

Achilles: I would like to show you the pretty view from the top of this tower.

Tortoise: Oh, how nice.

(They approach the boy, who watches them with curiosity, then says something to
the young woman-they both chuckle. Achilles and Mr. T, instead of going up the
boy's staircase, turn left and head down a short flight of stairs which leads to a
small wooden door.)