patternMinor
Explicit form of Hofstadters bluediag in floop
Viewed 0 times
explicithofstadtersbluediagformfloop
Problem
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 come
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 come
Solution
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.
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.
Context
StackExchange Computer Science Q#145610, answer score: 2
Revisions (0)
No revisions yet.