Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

r ~~:edu~'1

I definition I

I #1 I

FIGURE 72. The structure of a call-less

BlooP program. For this program to be

self-contained, each procedure definition

may only call procedures defined above it.

l _____ J

{ ~r~c:d~r~ :

definition I

l _____ #2 J I

(-----,

I proced ure I

I I d e fi mtlon.. I I

l _ -.:~~ __ j

etc.

INPUT >:>:>---~f>~r~c;d:r~ -:

: definitIOIl!

l _____ #k ;:)~>--...,:»> ..J OUTPUT

Suggested Exercises

Can you write a similar BlooP procedure which tests for the presence or

absence of the Tortoise property (or the Achilles property)? If so, do it. If

not, is it merely because you are ignorant about upper bounds, or could it

be that there is a fundamental obstacle preventing the formulation of such

an algorithm in BlooP? And what about the same questions, with respect to

the property of wondrousness, defined in the Dialogue?

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 Nth digit of 7T, after the decimal point

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

PI-DIGIT [2] = 4,

PI-DIGIT [1000000] 1)

BlooP and AooP and GlooP^415