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

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 al-

phabetical 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:

ABCDE FGH I J K LMN

OPQRSTUVWXYZ+x

o t 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 parame-

ter:

Blueprogram{#5000} [N] = N3

BlooP and AooP and GlooP^419