BlooP and FlooP and GlooP

The most important thing to understand about Chapter XIII is that "computable" is not one idea but two, and the line between them has nothing to do with speed. A procedure whose total amount of work can be calculated from its inputs before it starts is a fundamentally different animal from a procedure that searches until it finds what it is looking for. The first kind always finishes. The second kind may finish quickly, may finish after an absurd amount of work, or may never finish at all — and no amount of watching it run will tell you which.

That distinction is the whole chapter. Hofstadter builds two toy programming languages to make it concrete: BlooP, in which every loop must declare a ceiling before it begins, and FlooP, which adds one construct — a loop with no ceiling. He then asks whether a third language, GlooP, could be stronger than FlooP, and answers with the Church–Turing thesis.

Today's boundary is deliberately narrow. Inside: what a ceiling on a loop buys you, what it costs, and how to prove that the ceilinged class is genuinely missing something. Outside: computational complexity (nothing here is about how fast anything runs), the halting problem as a formal theorem, and the machinery of formal proof, which is tomorrow's subject.

One thing carries in from the previous day. A running system can be described at several levels at once — the hardware, the machine instructions, the source language, and the chunked level at which we say "it sorts the list" — and a level may be sealed off from the one beneath it only while the detail beneath is genuinely irrelevant. Today that rule is put under pressure, because whether a loop has a ceiling is a fact recorded at exactly one level, and it is invisible from the levels above and below it.

Three boxes are the whole model, and everything below expands one of them. The question in the middle box is the only one that matters, and it is answerable by reading the procedure rather than by running it.

BlooP is a language with exactly one restriction, and the restriction is severe enough to change the class of things the language can express. Every loop must be written as loop at most C times, where C is a value already computed when the loop is reached. A loop may finish early, but it may never run longer than the ceiling it declared.

A bounded loop is a loop whose maximum number of repetitions is a value already in hand when the loop begins. Hofstadter's phrase for what such loops can express is a predictably long search: a search that may be enormous, but whose length you could write down, from the inputs alone, before starting. Searching for the largest prime below a trillion is a predictably long search; you know it takes at most a trillion tests. Searching for the first perfect number above a trillion is not, because nobody can name a point at which you may stop looking.

Here is a BlooP-style procedure that counts hailstone steps — repeatedly halve an even number, or triple an odd number and add one — but only up to a declared ceiling. Braces mark annotations, not BlooP syntax.

DEFINE PROCEDURE "HAILSTONE-STEPS-WITHIN" [N, CEILING]:
BLOCK 0: BEGIN
  CELL(0) <= N;             {the running value}
  CELL(1) <= 0;             {steps taken so far}
  OUTPUT <= 0;              {0 stands for "1 was not reached in time"}
  LOOP AT MOST CEILING TIMES:
  BLOCK 1: BEGIN
    IF CELL(0) = 1, THEN:
    BLOCK 2: BEGIN
      OUTPUT <= CELL(1);
      ABORT LOOP 1;
    BLOCK 2: END;
    CELL(2) <= REMAINDER [CELL(0), 2];
    IF CELL(2) = 0, THEN:
    BLOCK 3: BEGIN
      CELL(0) <= QUOTIENT [CELL(0), 2];
    BLOCK 3: END;
    IF CELL(2) = 1, THEN:
    BLOCK 4: BEGIN
      CELL(0) <= 3 × CELL(0) + 1;
    BLOCK 4: END;
    CELL(1) <= CELL(1) + 1;
  BLOCK 1: END;
BLOCK 0: END.

Read the ceiling as a promise made in advance. CELL(2) holds the parity so that a number halved on this pass is not also tripled on the same pass. ABORT LOOP 1 leaves the loop entirely once the value reaches 1. Whatever N is, this procedure performs at most CEILING passes and then stops, because there is no construct in BlooP that can extend a loop past its declared count.

That single restriction gives BlooP its defining property: every BlooP program halts on every input. This is not an empirical observation about the programs people happen to write; it follows structurally, because a program is a finite nest of loops, each of which is individually bounded, so the total work is bounded too.

The class of functions BlooP computes has a standard name. The primitive recursive functions are the functions you can build from the basics using only ceilinged loops. Formally, they are the functions built from the constant zero, the successor function n → n + 1, and the projections that pick one argument out of several, closed under composition and under one recursion rule: define f at n + 1 from its value at n and from already-defined functions. Every function you are likely to have met — addition, multiplication, exponentiation, factorial, primality testing, the n-th prime, integer division — is primitive recursive. BlooP computes exactly this class: every BlooP program computes a primitive recursive function, and every primitive recursive function is computed by some BlooP program.

A guarantee stated in prose is easy to nod along with and hard to feel. The lab below runs a ceilinged computation step by step and reports the two facts that the ceiling buys: that termination is guaranteed, and what the worst case costs.

Protocol. Leave the input where it is and move the ceiling slider from its lowest setting upward one notch at a time. At each setting, record two numbers: the length of the visible step trace, and the reported worst-case step count. Confirm that the worst case never exceeds the ceiling and that the termination: guaranteed readout never changes, at any setting of either slider. Then hold the ceiling fixed and move the input slider across its whole range, and record whether any input makes the trace longer than the ceiling allows.

Limits. The lab establishes that this particular ceilinged procedure stops, which is the weakest possible version of the claim. It does not prove that all BlooP programs halt — that argument is structural, not experimental — and a guaranteed halt is not the same as a useful answer. A ceiling that is too small returns the "not reached in time" marker, which is a legitimate output of a program that terminated and told you nothing. The lab also says nothing about running time in seconds; a bounded loop can declare a ceiling of 2 raised to a power large enough that the guarantee is of no practical comfort.

FlooP is BlooP plus exactly one new construct, and the addition is small enough to write on one line while being large enough to break the halting guarantee outright. The new construct is the MU-LOOP: a loop with no ceiling at all, whose only exit is finding what it is looking for.

Here is the same task, written as an open search. Everything else is unchanged.

DEFINE PROCEDURE "HAILSTONE-STEPS" [N]:
BLOCK 0: BEGIN
  CELL(0) <= N;
  CELL(1) <= 0;
  MU-LOOP:
  BLOCK 1: BEGIN
    IF CELL(0) = 1, THEN:
    BLOCK 2: BEGIN
      OUTPUT <= CELL(1);
      ABORT LOOP 1;
    BLOCK 2: END;
    CELL(2) <= REMAINDER [CELL(0), 2];
    IF CELL(2) = 0, THEN:
    BLOCK 3: BEGIN
      CELL(0) <= QUOTIENT [CELL(0), 2];
    BLOCK 3: END;
    IF CELL(2) = 1, THEN:
    BLOCK 4: BEGIN
      CELL(0) <= 3 × CELL(0) + 1;
    BLOCK 4: END;
    CELL(1) <= CELL(1) + 1;
  BLOCK 1: END;
BLOCK 0: END.

Compare the two listings line by line. The arithmetic is identical, the cells are identical, the exit condition is identical. Two things changed: the CEILING parameter is gone, and LOOP AT MOST CEILING TIMES became MU-LOOP. The second version is shorter and, on the face of it, cleaner — it does not ask the caller for a number the caller has no way to supply. What it gave up in exchange is the only guarantee the first version had. There is no longer any argument, structural or otherwise, that this procedure ever returns.

The functions FlooP computes are the partial recursive functions: the class you get by adding one operator, the search operator, which given a condition returns the smallest number satisfying it and is undefined when no such number exists. "Partial" is the honest word — such a function may simply have no value at some inputs, because the program that computes it runs forever there. The general recursive functions are the partial recursive functions that happen to be total, meaning defined at every input. Every primitive recursive function is general recursive; the converse fails, which is what the second half of this lesson proves.

The upper half of this picture is unchanged; the lower half is what the MU-LOOP adds. The bounded branch has one outcome. The free branch has two, and the reader watching from outside cannot tell which one they are in, because a run that has not halted yet is indistinguishable from a run that never will.

The open search below is the hailstone rule with no ceiling: keep applying the rule until the value reaches 1. It is the standard example because the question of whether it always reaches 1 — the Collatz conjecture — is genuinely unsolved, which is precisely why the loop cannot be rewritten with a ceiling.

Protocol. Set the step budget high and move the starting number slider through small values, recording for each one how many steps the trace takes and what the termination readout says. Then find a starting number whose trace is long — values near 27 are dramatic — and lower the step budget below its step count. Record the moment the readout flips from unknown to not within budget. Finally, record the highest value the trace reaches for a starting number of 27 and compare it with the starting number itself.

Limits. Read the unknown label carefully, because it is the point of the lab. When the search halts inside the budget, the lab does not report "terminates"; it reports unknown, because halting on this input proves exactly nothing about the others. And not within budget is not evidence of non-termination either — it means only that the budget ran out first. The lab cannot settle the Collatz conjecture, and no amount of sliding will; computational verification has already checked every starting value below 2 to the power 68, roughly 2.95 × 10^20, without finding a counterexample and without producing a proof.

The abstract claim is that the free version loses a guarantee. Tracing both versions on one input shows exactly which line of the table the guarantee dies on. Take N = 7 and run the hailstone rule by hand.

BlooP was too weak, and FlooP repaired it by adding one construct. The obvious next question is whether the same move works again: is there a GlooP, a language that stands to FlooP as FlooP stands to BlooP? Hofstadter's answer is that GlooP is a myth, and the reason is not a proof.

The Church–Turing thesis is the claim that the informal notion of "a procedure a person could carry out mechanically, given unlimited paper and time" coincides exactly with the formal class that FlooP captures. It is a thesis and not a theorem, and the distinction matters. A theorem is proved from definitions; this claim has an informal notion on one side of the equals sign, and an informal notion cannot be an argument's premise. What supports it is convergence. Alonzo Church's lambda calculus, Alan Turing's machines, the general recursive functions of Gödel and Herbrand, Post's rewriting systems, register machines, and every subsequent model that was not deliberately restricted, all define the same class of functions — and the proofs that they coincide are ordinary mathematics. Nobody has proposed a mechanical procedure that falls outside it.

So the thesis is very well supported and remains falsifiable in principle: exhibit a procedure that is mechanical by any reasonable standard and computes something outside the class, and the thesis is dead. Ninety years of trying have not produced one. Treat it as the best-supported empirical claim in the subject rather than as a settled theorem, and be careful of arguments that quietly promote it to one.

Everything so far has said that BlooP is weaker than FlooP, but not proved it. The proof is a diagonal argument, and it is worth following slowly because tomorrow's chapter runs the identical move at the level of proof rather than computation.

Start with the fact that makes the argument possible: a BlooP program is a finite string over a finite alphabet. So the programs can be put in a list — sort by length, and sort strings of equal length alphabetically. Skip any string that is not a legal BlooP program, which is a decision a parser makes in bounded time, and restrict attention to programs taking a single numeric input. What remains is an infinite list with a definite first entry, second entry, and so on. Call the N-th one Blue #N, following Hofstadter's naming.

Every entry on this list halts on every input, because it is a BlooP program. So the following definition is unambiguous:

Bluediag[N] is 1 plus the result of running Blue #N on the input N.

Follow the last box carefully, because it carries the entire result. Suppose Bluediag were computed by some BlooP program. Then it appears somewhere on the list, say as Blue #k. Ask what happens at the input k. By assumption Blue #k run on k gives Bluediag[k]. By definition Bluediag[k] is 1 plus the result of running Blue #k on k. So that number equals itself plus one, which no number does. The assumption is false.

State the conclusion exactly. Bluediag is a total, well-defined function — total because every listed program halts everywhere, well defined because the list is fixed and the arithmetic is addition — and no BlooP program computes it. The bounded class is therefore genuinely incomplete: it omits a function that is perfectly computable in the ordinary sense. Bluediag is computable, in fact, by a FlooP program, which builds the list, runs the N-th entry, and adds one. What FlooP has that BlooP lacks is precisely the ability to run a search whose length depends on N in a way no single ceiling can cover.

The classic witness to the same gap, discovered long before Hofstadter wrote, is Ackermann's function, defined by three lines:

• A(0, n) = n + 1
• A(m + 1, 0) = A(m, 1)
• A(m + 1, n + 1) = A(m, A(m + 1, n))

Every value is defined and the recursion always bottoms out, so A is total and computable. But it grows faster than any primitive recursive function, so it is not primitive recursive and no BlooP program computes it. The growth is not a figure of speech: A(4, 0) = 13, A(4, 1) = 65533, and A(4, 2) is 2 to the power 65536, minus 3 — a number with nearly twenty thousand digits.

A reader who has just watched BlooP fall to a diagonal argument should immediately suspect FlooP of the same weakness. Running the identical construction against FlooP is the fastest way to see what the ceiling was actually doing.

The setup transfers without change. FlooP programs are also finite strings, so list them as Red #0, Red #1, and define Reddiag[N] as 1 plus the result of running Red #N on the input N. Now try to derive the contradiction. Suppose Reddiag is computed by Red #k and look at the input k.

The argument stalls at once, and it stalls at exactly one word. In the BlooP case, "the result of running Blue #k on k" was guaranteed to be a number. In the FlooP case it need not be: Red #k may run forever on k, in which case Reddiag[k] has no value, Red #k computing Reddiag is not contradicted by anything, and there is no equation to derive. Diagonalization needs the diagonal to exist, and the diagonal of a list of partial functions has holes in it.

This is the chapter's most useful asymmetry. The halting guarantee that made BlooP feel safe is exactly the property that made it vulnerable: a class of programs that all halt can be diagonalized out of, and a class that does not have that guarantee cannot. FlooP survives not by being cleverer but by being unable to promise anything. That is one concrete reason to expect no GlooP above it — the obvious escape route is closed.

The diagonal argument is short enough to follow on paper and slippery enough that most readers want to see the grid. The lab lays the listed programs against the inputs and lets you build the contradicting row yourself.

Protocol. Start at the smallest table size and read down the diagonal, writing out the diagonal entries before touching anything else. Set the diagonal offset to 1 and check the constructed row cell by cell against each listed program's row: for row N, the two should differ at column N and may agree anywhere else. Record which cell is marked as the contradiction cell and why that particular cell is the one that cannot be satisfied. Then raise the table size and confirm the constructed row is still absent from the grid, and change the offset to a value other than 1 and record whether the argument still goes through.

Limits. The grid is finite and the real list is infinite, so the lab illustrates the construction rather than proving anything; the proof is the one-line contradiction above, and it needs no grid at all. The grid also does not show real BlooP programs in real enumeration order — the ordering is a device to make "the N-th program" meaningful, and any effective ordering works equally well. Above all, the lab shows a gap in the bounded class, not a defect in any particular program on the grid. Every listed program is perfectly correct at what it does.

With both languages defined and the gap proved, the classes can be drawn in one picture, which is worth having because the containments are easy to state backwards.

Read the two boxes on the left as the constructs from the earlier diagrams and the arrows into prim and partial as "this construct is what defines this class". The two labelled containments are both strict, and each strictness is a theorem with a witness. Bluediag and Ackermann's function witness the first: total, computable, not primitive recursive. Any function whose program fails to halt somewhere witnesses the second: partial recursive but not total. The gloop box has no arrow leaving it because, if the thesis holds, there is nowhere for it to go.

The ceiling is the most important fact about a procedure today, and it is recorded at exactly one level of description. That makes it a sharp test of the sealing-off rule, because a level that seals off the one beneath it seals off this fact along with everything else.

The middle line is the only one that records the distinction. Above it, the two procedures have the same description, the same name, and — on every input where both halt — the same output. Below it, both compile to a comparison and a backward jump; the machine executing them has no notion of a ceiling and no way to represent one. So the ceiling is a fact about the source text, and observing the running system at any other level cannot recover it.

This is the practical consequence for anyone reasoning about a described procedure. Watching the output tells you nothing about whether the guarantee is there, and neither does watching the instructions execute. If someone hands you a procedure that has always finished, you have learned that it finished, which is a statement about the inputs tried and not about the procedure. The question "is there a ceiling" is answered by reading the definition, and by nothing else.

An argument this clean invites overstatement, so it is worth naming precisely what has and has not been shown.

The diagonal argument shows that the bounded class is missing a function. It does not show that any particular useful program fails to halt, and it does not suggest that programs written with ceilings are somehow unsafe. Bluediag is a construction built specifically to escape a specific list, and encountering something like it by accident in ordinary work is not a live risk.

An unbounded search does not mean "will not halt". It means only that no ceiling is known in advance. The hailstone procedure halts on every value anyone has tested; what it lacks is a proof, and the difference between "always halted so far" and "guaranteed to halt" is the entire subject of the day.

The enumeration argument depends on programs being finite strings over a finite alphabet, and on the property that legality can be checked mechanically. Both hold for BlooP and for every real programming language. They would fail for a notional system whose programs were infinite objects, which is worth knowing as a boundary of the technique rather than as a practical loophole.

The Church–Turing thesis remains a thesis. It is not proved, it is supported by the convergence of independently invented formalisms, and treating it as a theorem in an argument is a mistake that a careful reader should catch.

Finally, none of today's material is about efficiency. A bounded loop with a ceiling of A(4, 2) halts, guaranteed, and will not finish before the sun does. "Guaranteed to terminate" and "practical" are unrelated properties, and conflating them wastes the distinction the chapter was built to draw.

The capability to take from today is a reading habit: given a procedure in any notation, decide whether it is guaranteed to finish, and say what the answer rests on. The rule is short, because the deciding question is short.

Chapter XIII splits one word into two and shows the split is real rather than a matter of degree.

• "Computable" covers both procedures whose work is bounded in advance and procedures that search until they find; the difference is structural, not a matter of speed.
• BlooP allows only ceilinged loops, so every BlooP program halts on every input, and BlooP computes exactly the primitive recursive functions.
• FlooP adds the MU-LOOP, an unbounded search, and computes the partial recursive functions; those that are total are the general recursive functions.
• Bounded programs are finite strings, so they can be listed, and a diagonal construction defines Bluediag, a total function that no bounded program computes.
• Ackermann's function is the classic independent witness: total, computable, and not primitive recursive.
• The same diagonal fails against FlooP, because a list of partial functions has a diagonal with holes in it — the halting guarantee was what made BlooP vulnerable.
• GlooP, a language stronger than FlooP, is expected not to exist, on the strength of the Church–Turing thesis, which is a well-supported claim rather than a theorem.
• Whether a loop has a ceiling is recorded at the source level only, and is invisible both from the chunked description above it and from the machine instructions below it.

A reader is ready to continue when they can classify a described procedure and reconstruct the escape argument without notes.

• [ ] Can you state the difference between a bounded loop and a free loop in one sentence, without mentioning speed?
• [ ] Can you define a predictably long search and give an example that is not in this lesson?
• [ ] Can you explain why every BlooP program halts, from the structure of the language rather than from experience?
• [ ] Can you say what "primitive recursive" means in plain language and name three functions in the class?
• [ ] Can you rewrite a ceilinged procedure as an open search and name exactly what was given up?
• [ ] Can you explain why halting on one input tells you nothing about the others?
• [ ] Can you reconstruct the Bluediag construction and state where the contradiction lands?
• [ ] Can you explain why the same construction fails against FlooP?
• [ ] Can you say why the Church–Turing thesis is not a theorem, and what would refute it?
• [ ] Can you name a fact about a procedure that is invisible at both the level above and the level below the source?

The chapter compresses several results that were separately hard-won, and the primary papers are short and readable.

• Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, Chapter XIII.
• Alan M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society s2-42, 1937.
• Alonzo Church, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics 58(2), 1936.
• Wilhelm Ackermann, "Zum Hilbertschen Aufbau der reellen Zahlen", Mathematische Annalen 99, 1928 — the original fast-growing function.
• Stephen C. Kleene, Introduction to Metamathematics, North-Holland, 1952 — the standard treatment of the search operator and the general recursive functions.
• Jeffrey C. Lagarias, "The 3x + 1 Problem and its Generalizations", American Mathematical Monthly 92(1), 1985 — the survey of the open problem behind the free-loop lab.

Read Turing and Church side by side if you read only two: they were published months apart, reached the same class by entirely different routes, and the convergence is the evidence the thesis rests on.

Today produced one result and one habit. The result is the escape: some total, well-defined functions lie outside every bounded system, and the escape was performed by listing the system's own contents and constructing something that differs from every entry. The habit is the reading test — ask what value bounds the work before the work starts, and say what the answer rests on.

The next day runs the same escape at the level of proof rather than computation. In place of a list of programs there will be a list of provable statements; in place of "add one to the diagonal" there will be a sentence that describes its own position in that list; and in place of a function no program computes there will be a statement no proof reaches. The move is identical, and having watched it work once on computation is the whole reason it will be recognizable when it arrives.