3
$\begingroup$

In " Gödel, Escher, Bach" Hofstadter introduces the programming languages Bloop and Floop. Relevant here is mostly that Floop is Turing complete, while Bloop differs from Floop in one aspect: all loops must be bounded. So only for-loops, no while-loops.

Hofstadter shows that not all computable functions are computable by a Bloop program (so that Bloop is apparently really weaker than floop) by exhibiting a function called BLUEDIAG that is not computable by a bloop program. While the function itself is quite explicit, the proof (reproduced below) of why this is not programmable in Bloop somehow seems to never use any other property of Bloop except that there are only countably infinitely many Bloop programs. In particular it is not clear to me where in the proof it is used that loops must be bounded. To make this point clearer, my question is this:

If I would explicitly code a program to compute the BLUEDIAG function in Floop, where would I use an unbounded loop?

I will show where I got stuck in my own attempt. First a summary of the proof. (If my notation differs from Hofstadter's it is because I am translating back to English from a translated version of the book)

BLUEPROGRAMS is a list of all Bloop programs that take one integer input and have one integer output for each input. The programs on the list are sorted by length and within that alphabetically so that there is no ambiguity about the order.

BLUEPROGRAMS{N} denotes the Nth entry on this list.

BLUEPROGRAMS{N}[M] denotes the output of the program BLUEPROGRAMS{N} when fed the input M.

The function BLUEDIAG is defined by BLUEDIAG[N] = BLUEPROGRAMS{N}[N] + 1.

Now if BLUEDIAG were computable by a Bloop program then this program should appear somewhere on the list BLUEPROGRAMS, say at position $X$. We then get the strange situation that BLUEPROGRAMS{X}[X] = BLUEDIAG[X] = BLUEPROGRAMS{X}[X] + 1, where the first equality represents the assumption that BLUEPROGRAMS{X} calculates BLUEDIAG and the second comes from the definition of BLUEDIAG. Since no number Y satisfies Y = Y + 1 the number BLUEPROGRAMS{X}[X] cannot exist, hence the program BLUEPROGRAMS{X} does not exist.

So far so good. As far as proofs go this is really easy, but at the price of obfuscating what about all this is special to Bloop.

Now for the quest of making a program that computes BLUEDIAG. My plan of attack is to make three programs.

Program 1 takes as input a natural number and as output the code of the Nth blueprogram.

Program 2 takes as in put the code of a blueprogram B and a number M and outputs the same number this program B would produce when given the input M

Program 3 takes as input a number K and outputs the number K + 1.

I convinced myself that program 1 can be written in Bloop: we can show that the Nth blue program has no more than N + 100 characters, so we can just loop through the huge but bounded list of gibberish strings of at most N + 100 characters and count how many of those are bloop programs.

I also convinced myself that program 3 is in bloop.

So this isolates the problem of needing unbounded loops to program 2.

But here I get stuck. When I try to write a program that simulates a different program whose code it is given as input I don't see how to do it - not with unbounded loops and also not without it. It seems to require the program to 'break free' from its domain of well defined software and start talking to the hardware in some sort of meta-language: 'stop treating this in the way I treat it (as a string) but view it in the same way you view me'. I'm not sure how floop (or any language really) would have this power, let alone how unbounded loops come into play.

Any help is appreciated!

$\endgroup$
2
  • $\begingroup$ While I have given a general answer, I did not include an explicit form of bluddiag in Floop. An expert on register machine could give a better answer that shows where unbounded loops are sort of unavoidably used. $\endgroup$
    – John L.
    Nov 12, 2021 at 2:49
  • 1
    $\begingroup$ Each BlooP program can use constant-many cells. The number of cells used by a BlooP program can be arbitrarily large. So there is no BlooP program that can simulate all BlooP programs. This is the easy answer why a BlooP program cannot simulate every BlooP program when the latter is given as input. However, this does not prove why a BlooP program can output the same number by another way. $\endgroup$
    – John L.
    Nov 12, 2021 at 2:55

3 Answers 3

2
$\begingroup$

Great question!

You are wondering how "to write a program that simulates a different program whose code it is given as input".

That kind of program can be roughly understand as "an interpreter of a language." For example, the Python interpreter, i.e., python.exe (together with supporting libraries ) can read a Python program and execute it. Note that python.exe is written in machine code (roughly speaking), instead of in Python.

If the source code is also written in the same language, that kind of program will be called "a universal machine" of that language. The most famous universal machine is the universal Turing machine, which can read the textual representation of another Turing machine and simulates what it does.

As the above examples indicate, it may not be an easy task to write an interpreter or program a universal machine, conceptually or practically. That explains why you "don't see how to do it". Had you taken a course on assembly languages or compilers, you would have known how to do it. Basically, your code should read the input program as text, translate/compile it into "executable code" and then (or at the same time) execute the code. The "executable code" will define/allocate variables that record the current running state as it runs, as well as variables that track the next statement to execute.


Program 2, if written in Bloop, would be a "universal machine" of BlooP. You are right to assert that, in fact, there is no universal machine of Bloop.

Since FlooP is Turing complete, it is possible to write program 2 in FlooP. (Turing completeness means roughly the statement "what is machine-computable is FlooP-computable" in the book.)


You are wondering how unbounded loops come into play, which enables FlooP to "have this power".

This is, in fact, not easy to answer. Most computable functions, especially the "ordinary" ones, that are studied in mathematics can be computed by a BlooP program. It is difficult to devise or prove a computable function that cannot be computed by a BlooP program. In fact, instead of "at the price of obfuscating what about all this is special to Bloop", the proof given in the book tells clearly what is special to Bloop, i.e., there are countably-enumerable many programs written in Bloop and "addition by 1" is allowed in a Bloop program. It is only unfortunate/fortunate that to beginners, that characterization may not appear intuitive or familiar at all.

$\endgroup$
10
  • $\begingroup$ Also see stored-program computer $\endgroup$
    – John L.
    Nov 10, 2021 at 20:16
  • $\begingroup$ Hm, it looks like this answer did not answer the question. $\endgroup$
    – John L.
    Nov 10, 2021 at 20:31
  • $\begingroup$ This is a useful answer nevertheless, but I have a question about the last paragraph. In the question I was complaining that the proof doesn't use any special properties of Bloop except there being only countably many programs, and now you tell me 'yes but that is the special property'. So I guess my question is: doesn't Floop also have only countably many programs? So wouldn't the same argument apply to Floop then, if that is all that is needed? $\endgroup$
    – Vincent
    Nov 10, 2021 at 21:27
  • 1
    $\begingroup$ If a program/function is not total, then "addition by 1" does not make sense for those program that does not return. $\endgroup$
    – John L.
    Nov 10, 2021 at 23:04
  • 1
    $\begingroup$ However, what we wanted here might be less than "an interpreter of BlooP" since the size of the Bloop program as input is a bounded by a given number $(N+100)$ before we run the interpreter. I am still wondering/thinking "how unbounded loops come into play"... $\endgroup$
    – John L.
    Nov 11, 2021 at 21:05
2
$\begingroup$

Program 2 can be a FlooP interpreter.

When started in a state in which the source code of a FlooP program is in internal memory, it will execute it.

It can do this by keeping its internal memory subdivided into three parts:

  1. The FlooP program's source code (represented as a sequence of numbers according to some representation you have chosen, e.g. ASCII, or a more concise bytecode representation).
  2. A sequence of numbers representing the current point of execution within that program (e.g., if ASCII is used, there might be an index into the sequence of ASCII characters, but for each loop we're in, we want to store the start of the loop to jump back to after an iteration has finished, and for each bounded loop we're in, we also need to count the number of iterations executed thus far).
  3. The contents of the variables of the FlooP program being executed (OUTPUT and CELL(i) for each i)

Part 1 is fixed, but 2 and 3 are variable in size and they can grow arbitrarily large (depending on the program being interpreted). This is not a blocking issue, e.g. they can be interleaved.

The FlooP program implementing the interpreter will alternate between scanning statements in the source code (within memory area #1) and executing them (on memory area #3). For each type of statement, a function can be defined to execute that statement; for control structures, more than one function may be required. The interpreter will scan the source code, find a statement or control structure, and invoke the functions defined to execute them.

I'm not filling in the functions, but I hope this will suffice to convince you that it's doable.

(Doesn't Hofstadter explain this? I do not have a copy handy.)

$\endgroup$
3
  • $\begingroup$ Thanks! In the last long paragraph (starting with 'The BlooP program implementing the interpreter...') did you mean to write FlooP program, or is it really inteded as BlooP program? $\endgroup$
    – Vincent
    Nov 10, 2021 at 21:18
  • 1
    $\begingroup$ Both. However, only writing FlooP program will succeed. Some steps along the way will break down if we write in Bloop program. $\endgroup$
    – John L.
    Nov 10, 2021 at 23:23
  • $\begingroup$ My bad ... I had the names backwards. Thanks! Fixed. $\endgroup$ Nov 12, 2021 at 11:59
1
$\begingroup$

I think the crux of the problem is this: Consider an arbitrary BlooP program. It may contain no loops. It may contain one or more loops in sequence, where the body of each loop has no loops. It may contain one or more loops with sub-loops. It may contain loops within loops within loops. ... It may contain an arbitrary number of nested loops.

Now consider a program which interprets an arbitrary BlooP program. It may need to interpret an arbitrary number of nested loops. I do not believe this can be done with a program that itself uses only bounded loops -where those loops were written before the interpreter ever saw a BlooP program-. There would always be a degree of nesting not interpretable.

$\endgroup$
1
  • $\begingroup$ I am afraid this answer is flawed. The number of loops in the BlooP program given as input is bounded by $N+100$. So while it can be arbitrarily large, it is still bounded and given. $\endgroup$
    – John L.
    Nov 12, 2021 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.