Jtdylktuy

Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid".

I'm unclear whether cell variables require constant indices or whether indirection is allowed.

The four examples shown in the book show constants. For example:

CELL(0) ⇐ 2;

What is unclear is whether this would be allowed:

CELL(CELL(0)) ⇐ 2;

The question is important to understanding the chapter. If indirection is not allowed, is that because it would defeat the objective of the language which is intentionally limited so that it can only express primitive recursive functions.

Another way of asking the question is: "Does support for indirect addressing turn BlooP into FlooP, something that can express μ-recursive functions?"

The converse of the question is: "Would the absence of indirect addressing from BlooP prevent it from writing sorts or turing machines, both of which need indirect addressing?"

Well, first of all you might see that these programs came about from this paper (actually, I don't know, but I think so). So, in terms of the required computational strength, all you really need is a command to (1) zero out a variable (2) add by 1 (3) make a loop.

So, for example, if we used a command like $C[100]=C[100]+1$, we could simply replace them with a command like $t_{100}=t_{100}+1$ etc. But it seems that your question is certainly more complicated. For example, can we introduce a command like $C[C[100]]:=50$ without altering the strength of the our programs. Let's write the previous command simply as $C^2 [100]:=50$ from now on.

Below is a very brief and rough sketch. Honestly, partly why this is so brief is because I am not smart enough to see through the most important parts without writing out all the details. But this is essentially the usual reduction argument.

For example, first of all (for convenience) let's talk about commands with just one level of indirection is allowed. So $C^2 [100]$ would be allowed but not $C^3[100]$. Now it seems that the most important commands we need to be able to emulate would be of the format: $(1)$ $C^2[100]:=0$ $(2)$ $C^2[100]:=C^2 [100]+1$ $(3)$ $Loop,,,,C^2[100] $.

What we really want is that for any given program $N$ which allows nested commands (such as the three mentioned above), to be able to convert into a program $P$ which simply doesn't use any of the nested commands. So my suggestion is to use two lists $L_1$ and $L_2$ in our program $P$ (alternatively, we could just use a simple list of pairs). Both $L_1$ and $L_2$ will be of same length. $L_1$ doesn't have any repetition in its elements and $L_2$ only contains positive numbers. As as example, if we had $L_1=[0,2,4]$ and $L_2=[1,3,3]$, this is supposed to represent $C[0]=1,C[2]=3,C[4]=3$ (and furthermore, all other cell positions are $0$).

Now normally the programs $N$ and $P$ will be the same, except for those lines where $N$ makes reference to its cells. For example, if $C[100]$ or $C^2[100]$ are used in some line in $N$ we have to be careful about how it will be converted in $P$. Let's first consider what happens when $N$ uses a command such as $C[100]:=C[100]+1$ or $C[100]:=0$. Well, in that case, the program $P$ can just modify the lists $L_1$ and $L_2$ appropriately. Now what happens if $N$ uses a command such as $Loop,,,, C[100]$. Well we first find the position in $L_1$ (if it exists) which contains $100$ and look at the corresponding position in $L_2$. For example, suppose we had $L_1(3)=100$, $L_2(3)=50$. In our program $P$ we can just write the command "$Loop,,,,50$" now. If it happened that $L_1$ didn't contain $100$, then we could just write "$Loop,,,,0$" in our program $P$.

The situation shouldn't be very different (I think) when $N$ uses something like $C^2[100]$. For example, here is a rough sketch as to how we might proceed (in our program $P$): In our program $P$ check whether $L_1$ contains $100$ or not (meaning we are checking whether $C[100]$ is $0$ or not). Hypothetically suppose $L_1$ did contain $100$. Suppose we had $L_1(3)=100$. Now check whether the value in $L_2(3)$ (this corresponds to $C[100]$) is contained in $L_1$ or not? Meaning that now we are trying to check whether $C[C[100]]$ is $0$ or not. Suppose it was contained in $L_1$ at index/position $5$. Now $L_2(5)$ will correspond to $C[C[100]]$.

And now depending on the command we take the appropriate action. For example, if the command was $C^2[100]:=C^2[100]+1$ and $C[100]$ wasn't present in $L_1$, then the program $P$ will add it to $L_1$ and set the corresponding position in $L_2$ to $1$. If $C[100]$ was present in $L_1$, then $P$ will add $1$ to corresponding position in $L_2$. That is, set $L_2(i):=L_2(i)+1$ where $L_1(i)=C[100]$.