This is a series on the book Gödel, Escher, Bach: An eternal golden braid by Douglas Hofstadter. I am guest diarist for this week taking over for plf515.
Earlier diaries are here.
Today, we will doggedly work our way through Chapter XIII: BlooP and FlooP and GlooP, p. 406 - 430.
BlooP, FlooP and GlooP are names for theoretical computer languages that Hofstadter has invented, with the intention of shining light on TNT's strengths and limitations from a new angle, working out some practical implications of the phrase "sufficiently powerful" as applied to formal systems.
p406 We explore whether a refrigerator is a record player, and conclude that it is too "weak" to be an interesting record player.
p407 has two sections that are linked in my mind. Hofstadter quotes a passage from Are Quanta Real? by J M Jauch which starts off by finding order among apparent chaos in numbers but more interestingly discusses finding order in "reality". It appears that Ganto's Ax operates in science also, since for any interpretation of our measurements, any number of interpretations are "reality", so all of them may be "not reality" as well. Our weapon against this uncertainty in science is Occam's Razor, a suitably edged response.
P410 we jump into understanding the BlooP language. I think that anyone with no experience of computer languages may struggle with the technical parts of this chapter but I'll provide what light I can. Anyone with extensive experience of computer languages will struggle with the restrictions and inefficiencies, so all is fair :-). There is a lot of irritating punctuation in BlooP which is simply carried over from the mind-set of the languages of the day; particularly Pascal, I'd guess.
We plunge in with an example that shows why I tagged the languages as "theoretical", since 23n will yield staggeringly huge numbers for even fairly small values of n. For n=15, for example, the result starts with "2.." and carries on for more than 4 million digits.
A simpler example might have been two-to-the-n (I am using "<=" for that left pointing arrow):
DEFINE PROCEDURE "TWO-TO-THE" [N]:
BLOCK 0: BEGIN
CELL(0) <= 1;
LOOP N TIMES:
BLOCK 1: BEGIN
CELL(0) <= CELL(0) x 2;
BLOCK 1: END;
OUTPUT <= CELL(0);
BLOCK 0: END.
or equivalently, accumulating the result directly in the OUTPUT space rather than an internal store:
DEFINE PROCEDURE "TWO-TO-THE" [N]:
BLOCK 0: BEGIN
OUTPUT <= 1;
LOOP N TIMES:
BLOCK 1: BEGIN
OUTPUT <= OUTPUT x 2;
BLOCK 1: END;
BLOCK 0: END.
By the same token we can exponentiate on 3:
DEFINE PROCEDURE "THREE-TO-THE" [N]:
BLOCK 0: BEGIN
OUTPUT <= 1;
LOOP N TIMES:
BLOCK 1: BEGIN
OUTPUT <= OUTPUT x 3;
BLOCK 1: END;
BLOCK 0: END.
which is trivially different from above, and then combine the two:
DEFINE PROCEDURE "TWO-TO-THE-THREE-TO-THE" [N]:
BLOCK 0: BEGIN
OUTPUT <= TWO-TO-THE [THREE-TO-THE [N]];
BLOCK 0: END.
which shows to some extent how to use procedures. Once we get to multi-parameter procedures we can recode these more simply again:
DEFINE PROCEDURE "POWER" [M,N]:
BLOCK 0: BEGIN
OUTPUT <= 1;
LOOP N TIMES:
BLOCK 1: BEGIN
OUTPUT <= OUTPUT x M;
BLOCK 1: END;
BLOCK 0: END.
and
DEFINE PROCEDURE "TWO-TO-THE-THREE-TO-THE" [N]:
BLOCK 0: BEGIN
OUTPUT <= POWER [2,POWER [3,N]];
BLOCK 0: END.
These procedures take the place of functions in number theory, allowing more and more complex properties of numbers to be investigated.
Hofstadter introduces conditional statements (IF statements) and a couple of loop-exit mechanisms, although the syntax is a little confusing in my opinion. He is extremely careful to avoid any mechanism which will allow arbitrary jumps, of the sort beloved by BASIC pranksters:
10 PRINT "You're stuck"
20 GOTO 10
Also importantly, BlooP is extended to allow a procedure to return a truth value (YES or NO) which can than be used in an IF statement to test whether to undertake a particular action.
pp 415-416, We get on to some practical exercises to see whether given desired procedures can actually be achieved in BlooP. This is the moment of truth: How powerful is BlooP? Here are the challenges:
FACTORIAL [N]
This is straightforward in BlooP
REMAINDER [M,N] (the remainder upon dividing M by N)
The awkwardness in concocting a "MINUS" function is a good indicator of the messiness of inverse functions. Perfectly feasible, however. Building up low-level functions of this kind allows more complex properties to be considered for feasibility in BlooP. A good complement to this function would be QUOTIENT [M,N] that would give the integer division of M by N.
PI-DIGIT [N]
Before doing this, it would probably be a good idea to consider a function like RATIONAL-DIGIT [K,L,M] which outputs the Mth digit of K/L. Once that is available, there are functions which generate a rational approximation of pi which can reliably be used for the Nth digit in (much) less than N steps. So feasible, if pretty complicated.
FIBO [N] The Nth Fibonacci number
This is simple again. Here it is:
DEFINE PROCEDURE "FIBO" [N]:
BLOCK 0: BEGIN
CELL(0) <= 0;
CELL(1) <= 1;
LOOP N TIMES:
BLOCK 1: BEGIN
CELL(2) <= CELL(0) + CELL(1);
CELL(0) <= CELL(1);
CELL(1) <= CELL(2);
BLOCK 1: END;
OUTPUT <= CELL(0);
BLOCK 0: END.
PRIME-BEYOND [N]
Since there is always a prime between N and 2N (N>1), we can check this in a known number of steps.
PERFECT [N]
There is no way of knowing how big our search must be for (say) the 200th perfect number, if it even exists, so this is probably not BlooP achievable.
PRIME? [N]
We were already given this one.
PERFECT? [N]
This is straightforward, an accumulation of the factors of N
TRIVIAL? [A,B,C,N]
Equation check, this is easy.
PIERRE? [A,B,C]
Even without the knowledge that FLT is proven, it would be possible in advance to establish how big a power could be feasible for this equation to work, so this has always been BlooP-solvable. For a sufficiently large N, X^N+X^N < (X+1)^N, and it happens that N<X, so we could search powers up to the larger of A or B using TRIVIAL? above.
FERMAT? [N]
The answer to this has changed since the book was published. Now it is trivial to code this in BlooP: only "YES" when N=1 or 2.
TORTOISE-PAIR? [M,N]
Equation check, this is easy.
TORTOISE? [N]
As indicated in the previous Dialogue, a simple approach to this does not have an obvious bound to the search (for even N). I don’t know if there is any number theory result to help on this.
MIU-WELL-FORMED? [N]
Since the number of digits in N is less than N, it’s easy to write a BlooP program to break out the digits of N (into CELL() storage) using REMAINDER and QUOTIENT procedures. Once that is done we can check whether each is 3,1 or 0.
MIU-PROOF-PAIR? [N]
Whoof. Now we are getting a little more complicated, but we can imagine an intermediate function here, MIU-PROOF-STEP [M,N] which checks whether N can be obtained from M by one application of one of the rules, and apply that successively to each portion of the broken-out digits of N. So again this should be possible in BlooP.
MIU-THEOREM? [N]
There is no obvious way to make this into a predictable-length search, although like FERMAT? above I wouldn’t rule out the possibility of using a result from "outside the system" to allow a simpler BlooP test to be written.
TNT-THEOREM? [N]
FALSE? [N]
A little dig here from Douglas, trying to make us consider whether or not TNT has captured number theory. Nevertheless from a BlooP perspective both of these questions are out of reach.
Phew! Actually working through those is quite a chunk of thinking. The parallel between tests and theorems is moderately strong, in that we tend to build up the store and complexity of both by relying on the earlier, simpler results.
p 417, The terminology that Hofstadter dropped on us at the beginning of the Chapter, primitive recursive, is used now with the background of BlooP programming to more effect – that BlooP programs capture the space of primitive recursive notions/predicates/functions. We know they will take a finite time to complete because the structure of BlooP enforces this. And if we know we are dealing with a primitive recursive statement, TNT is guaranteed to assess the truth or falsity of that statement. But if we have a statement that is not primitive recursive, we cannot be so sure. So we carry on to produce a describable function that cannot be produced in BlooP, and as you might now expect, we do this by making BlooP try to talk about itself.
Effectively on p418 and 419, what we try to do is write a BlooP compiler-interpreter in BlooP – a BlooP program that will run and return the result from a number that codes for another BlooP program – then on p420 feed it with itself. We also have to make a list of all valid programs (up to a given length), but this is merely a typographical search, impossibly long but in principle straightforward (because for example the Nth valid BlooP program certainly has a length shorter than say N+100).
Unfortunately it turns out that BlooP is intrinsically not capable of doing this, because every BlooP program must terminate, and we could force a version of the interpreter to return a different result , based on the code, than the actual program coded for would. Hofstadter uses a version of Cantor’s diagonal argument, adding one to the output of the Nth-program-interpreter, and then asking the output of the program itself. While the specific example is contrived, it demonstrates the principle that not all programs can be represented in BlooP.
So we move to FlooP – more powerful because now we do not need to say how many times we will traverse each loop, via the MU LOOP construct. Now we can write the interpreter, but because we have no guarantee of termination in FlooP as we did with BlooP, the contradiction of output does not arise. However, a parallel problem arises, in that we cannot tell from examination whether or not a FlooP program will terminate. An ambitious claim for a set of all terminating FlooP programs founders on this rock, and (we are eventually forced to conclude, on p429) for both humans and computers, since it is not at all clear in advance whether any given process will terminate.
And so we attempt to move on to GlooP – but there is no obvious restriction to remove. We have nothing we can do to make FlooP intrinsically more powerful, and making it less powerful will drop us back to BlooP or indeed lower in expressive power. So GlooP is a myth.
You might feel, as I do to some extent, that Hofstadter’s opening remark on the following Dialogue’s preface is a reference to those emerging from the morass of this Chapter, or indeed this diary:
The Tortoise and Achilles have just completed a tour of a porridge factory.
See you next week fellow GEBbers!
.......
Severe delays imposed by tag-wrestling. I could not get "pre" tags to work properly and the "Publish" (but not the "Preview") insisted I had a mismatched b tag.