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

Below, I list some functions and properties, and you ought to take the time to determine whether you believe they are primitive recursive (BlooP-programmable) or not. This means that you must carefully consider what kinds of operations will be involved in the calculations which they require, and whether ceilings can be given for all the loops involved.

FACTORIAL [N] = NI (
the factorial of
N)

(e.g., FACTORIAL [4] = 24)

REMAINDER [M,N] =
the remainder upon dividing
M
by
N

(e.g., REMAINDER [24,7] = 3)

PI-DIGIT [N] =
the
N
th digit of pi, after the decimal point

(e.g. PI-DIGIT [1] = 1,

PI-DIGIT [2] = 4

PI-DIGIT [1000000] = 1

FIBO [N] =
the
N
th Fibonacci number

(
e.g
., FIBO [9] = 34)

PRIME-BEYOND [N[ =
the lowest prime beyond
N

(
e.g.,
PRIME-BEYOND [33] = 37)

PERFECT [N] =
the
N
th "perfect" number (a number such as 28 whose divisors sum up to itself: 28 = 1 + 2 + 4 + 7 + 14
)

(
e.g.,
PERFECT [2] = 28)

PRIME? [N] = YES
if
N
is prime, otherwise
NO
.

PERFECT? [N] = YES
if
N
is perfect, otherwise
NO.

TRIVIAL? [A,B,C,N] = YES
if
A"+B" = Cn
is correct; otherwise
NO.

(e.g.,
TRIVIAL? [3,4,5,2] = YES,

TRIVIAL? [3,4,5,3] = NO)

PIERRE? [A,B,C] = YES if A"+B" = C"
is satisfiable for some value of
N
greater
than 1, otherwise
NO.

(e.g.,
PIERRE? [3,4,5] = YES,

PIERRE? [1,2,3] = NO)

FERMAT? [N] = YES if A"+B" = CN
is satisfied by some positive values of
A, B, C;
otherwise
NO.

(e.g.,
FERMAT? [2] = YES)

TORTOISE-PAIR? [M,N] = YES
if both
M
and
M + N
are prime, otherwise
NO.

(e.g.,
ORTOISE-PAIR [5,1742] = YES,

TORTOISE-PAIR [5,100] = NO)

TORTOISE? [N] = YES
if
N
is the difference of two primes, otherwise
NO.

(e.g.,
TORTOISE [1742] = YES,

TORTOISE [7] = NO)

MIU-WELL-FORMED? [N] = YES
if
N,
when seen as a string of the
MIU-System,
is well-formed; otherwise
NO.

(e.g.,
MIU-WELL-FORMED? [310] = YES,

MIU-WELL-FORMED? [415] = NO)

MIU-PROOF-PAIR? [M,N] = YES
If
M,
as seen as a sequence of strings of the
MIU-system
,
is a derivation of
N,
as seen as a string of the
MIU-
system; otherwise
NO.

(e.g.,
MIU-PROOF-PAIR? [3131131111301,301] = YES,

MIU-PROOF-PAIR? [311130,30] = NO)

MIU-THEOREM? [N] = YES
if
N,
seen as a
MIU-
system string, is a theorem; otherwise
NO.

(e.g.,
MIU-THEOREM? [311] = YES,

MIU-THEOREM? [30] = NO,

MIU-THEOREM? [701] = NO)

TNT-THEOREM? [N] = YES
if
N,
seen as a
TNT-
string, is a theorem.

(e.g.,
TNT-THEOREM? [666111666] = YES,

TNT-THEOREM? [123666111666] = NO,

TNT-THEOREM? [7014] = NO)

FALSE? [N] = YES
if
N,
seen as a
TNT-
string, is a false statement of number theory; otherwise
NO.

(e.g., FALSE? [6661 1 1666] = NO,

FALSE? [2236661 1 1666] = YES,

FALSE? [7014] = NO)

The last seven examples are particularly relevant to our future metamathematical explorations, so they highly merit your scrutiny.

Expressibility and Representability

Now before we go on to some interesting questions about BlooP and are led to its relative, FlooP, let us return to the reason for introducing BlooP in the first place, and connect it to
TNT
. Earlier, I stated that the critical mass for Gödel’s method to be applicable to a formal system is attained when all primitive recursive notions are representable in that system. Exactly what does this mean? First of all, we must distinguish between the notions of representability and expressibility.
Expressing
a predicate is a mere matter of translation from English into a strict formalism. It has nothing to do with theoremhood. For a predicate to be
represented
, on the other hand, is a much stronger notion. It means that

(1) All true instances of the predicate are theorems;

(2) All false instances are nontheorems.

By "instance", I mean the string produced when you replace all free variables by numerals. For example, the predicate
m + n = k
is represented in the pq-system, because each true instance of the predicate is a theorem, each false instance is a nontheorem. Thus any specific addition, whether true or false, translates into a
decidable
string of the pqsystem. However, the pq-system is unable to express-let alone represent-any other properties of natural numbers. Therefore it would be a weak
candidate
indeed in a competition of systems which can do number theory.

Now
TNT
has the virtue of being able to
express
virtually any number-theoretical predicate; for example, it is easy to write a
TNT
-string which expresses the predicate "
b
has the Tortoise property". Thus, in terms of expressive power,
TNT
is all we want.

However, the question "Which properties are
represented
in TNT?" is Precisely the question "How powerful an axiomatic system is
TNT
?" Are all Possible predicates represented in
TNT
? If so, then
TNT
can answer any question of number theory; it is complete.

Primitive Recursive Predicates Are Represented in TNT

Now although completeness will turn out to be a chimera.
TNT
is at least complete with respect to
primitive recursive
predicates. In other words, any statement of number theory whose truth or falsity can be decided by a

computer within a predictable length of time is also decidable inside
TNT
. Or, one final restatement of the same thing:

If a BlooP test can be written for some property of natural numbers, then that property is represented in
TNT
.

Are There Functions Which Are Not Primitive Recursive?

Now the kinds of properties which can be detected by BlooP tests are widely varied, including whether a number is prime or perfect, has the Goldbach property, is a power of 2, and so on and so forth. It would not be crazy to wonder whether
every
property of numbers can be detected by some suitable BlooP program. The fact that, as of the present moment, we have no way of testing whether a number is wondrous or not need not disturb us too much, for it might merely mean that we are ignorant about wondrousness, and that with more digging around, we could discover a universal formula for the upper bound to the loop involved. Then a BlooP test for wondrousness could be written on the spot. Similar remarks could be made about the Tortoise property.

So the question really is, "Can upper bounds always be given for the length of calculations-or, is there an inherent kind of jumbliness to the natural number system, which sometimes prevents calculation lengths from being predictable in advance?" The striking thing is that the latter is the case, and we are about to see why. It is the sort of thing that would have driven Pythagoras, who first proved that the square root of 2 is irrational, out of his mind. In our demonstration, we will use the celebrated
diagonal
method,
discovered by Georg Cantor, the founder of set theory.

Pool B, Index Numbers, and Blue Programs

We shall begin by imagining a curious notion: the pool of all possible BlooP programs.

Needless to say, this pool-"Pool B"-is an infinite one. We want to consider a subpool of Pool B, obtained by three successive filtering operations. The first filter will retain for us only
call-less
programs. From this subpool we then eliminate all tests, leaving only
functions
. (By the way, in call-less programs, the
last
procedure in the chain determines whether the program as a whole is considered a test, or a function.) The third filter will retain
only functions which have exactly one input parameter
. (Again referring to the final procedure in the chain.) What is left?

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

Let us call these special BlooP programs
Blue Programs
.

What we would like to do now is to assign an unambiguous
index
number
to each Blue Program. How can this be done? The easiest way—we shall use it—

is to list them in order of length: the shortest possible. Blue

Program being # 1, the second shortest being #2, etc. Of course, there will be many programs tied for each length. To break such ties, we use alphabetical order. Here,

"alphabetical order" is taken in an extended sense, where the alphabet includes all the special characters of BlooP, in some arbitrary order, such as the following: A B C D E F G H I J K L M N

O P Q R S T U V W X Y Z + x

0 1 2 3 4 5 6 7 8 9 <= = < >

( ) [ ] { } - ´ ? : ; , .

-and at the end comes the lowly blank! Altogether, fifty-six characters. For convenience's sake, we can put all Blue Programs of length 1 in Volume 1, programs of 2 characters in Volume 2, etc. Needless to say, the first few volumes will be totally empty, while later volumes will have many, many entries (though each volume will only have a finite number). The very first Blue Program would be this one:

DEFINE PROCEDURE "A" [B]:

BLOCK 0: BEGIN

BLOCK 0: END.

This rather silly meat grinder returns a value of 0 no matter what its input is. It occurs in Volume 56, since it has 56 characters (counting necessary blanks, including blanks separating successive lines).

Soon after Volume 56, the volumes will get extremely fat, because there are just so many millions of ways of combining symbols to make Blue BlooP programs. But no matter-we are not going to try to print out this infinite catalogue. All that we care about is that, in the abstract, it is well-defined, and that each Blue BlooP program therefore has a unique and definite index number. This is the crucial idea.

Let us designate the function calculated by the kth Blue Program this way: Blueprogram{# k} [N]

Here, k is the index number of the program, and
N
is the single input parameter. For instance, Blue Program # 12 might return a value twice the size of its input: Blueprogram{#12} [N] = 2 x N

The meaning of the equation above is that the
program
named on the left-hand side returns the same value as a human would calculate from the ordinary algebraic expression on the right-hand side. As another example, perhaps the 5000th Blue Program calculates the cube of its input parameter:

Blueprogram{#5000} [N] = N3

The Diagonal Method

Very well-now we apply the "twist": Cantor's diagonal method. We shall take this catalogue of Blue Programs and use it to define a new function of one variable-
Bluediag

[N]-which will turn out not to be anywhere in the list (which is why its name is in italics).

Yet Bluediag will clearly be a well-defined, calculable function of one variable, and so we will have to conclude that functions exist which simply are not programmable in BlooP.

Here is the definition of Bluediag ~N]:

Equation (1) ... Bluediag [N] = 1 + Blueprogram{#N} [N]

The strategy is: feed each meat grinder with its own index number, then add 1 to the output. To illustrate, let us find Bluediag [12]. We saw that Blueprogram{# 12} is the function 2N; therefore, Bluediag [12] must have the value 1 + 2 x 12, or 25. Likewise, Bluediag [5000] would have the value 125,000,000,001, since that is 1 more than the cube of 5000. Similarly, you can find
Bluediag
of any particular argument you wish.

The peculiar thing about Bluediag [N] is that it is not represented in the catalogue of Blue Programs. It cannot be. The reason is this. To be a Blue Program, it would have to have an index number-say it were Blue Program # X. This assumption is expressed by writing

Equation (2) ...

Bluediag
[N] = Blueprogram{# X} [N]

But there is an inconsistency between the equations (1) and (2). It becomes apparent at the moment we try to calculate the value of Bluediag [ X], for we can do so by letting N

take the value of X in either of the two equations. If we substitute into equation (1), we get:

Bluediag
[ X] = 1 + Blueprogram{# X} [ X]

But if we substitute into equation (2) instead, we get:

Bluediag
[ X] = Blueprogram{# X} [ X]

Now
Bluediag
[ X] cannot be equal to a number and also to the successor of that number.

But that is what the two equations say. So we will have to go back and erase some assumption on which the inconsistency is based. The only possible candidate for erasure is the assumption expressed by Equation (2): that the function
Bluediag
[
N
] is able to be coded up as a Blue BlooP program. And that is the proof that
Bluediag lies outside the
realm of primitive recursive functions
. Thus, we have achieved our aim of destroying Achilles' cherished but naive notion that every number-theoretical function must be calculable within a predictable number of steps.