a very long Godel 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,
DE FIN E END
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 ingen-
ious argument given by Alan Turing shows that no BlooP program can
make this distinction infallibly. The trick is actually much the same as
Godel'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 termina-
tion 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 ap-
proach, 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 Tor-
toise 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(^426) BlooP and F100P and GlooP