[Edu-sig] Hofstadter, Escher via Python

[David Scherer]

This has nothing to do with plane tilings, but this subject line
reminded me of this, which I wrote a while ago while reading
Hofstadter's "Godel, Escher, Bach."  I'll throw it out here in case
anyone finds it interesting:

Hofstadter defines a language "BlooP" which permits only bounded loops,
and therefore can express only "primitive recursive" functions.  A test
for the Goldbach property looks like this:

DEFINE PROCEDURE "GOLDBACH?" [N]:
BLOCK 0: BEGIN
	CELL(0) <= 2;
	LOOP AT MOST N TIMES:
	BLOCK 1: BEGIN
		IF {PRIME? [CELL(0)]
			AND PRIME? [MINUS [N, CELL(0)]]},
		THEN:
		BLOCK 2: BEGIN
			OUTPUT <= YES;
			QUIT BLOCK 0;
		BLOCK 2: END
		CELL(0) <= CELL(0) + 1
	BLOCK 1: END
BLOCK 0: END

After a while this language got on my nerves.  It occurred to me that
Python, restricted to using only 'for i in range(???):' for iteration,
can express exactly the same kinds of functions as BlooP (and fails to
express the same kinds of functions).  Recursion is not allowed, of
course.  In Python, the above algorithm is considerably more terse and
readable:

def goldbach(N):
	for i in range(2, N-2):
		if prime(i) and prime(N-i):
			return 1
	return 0

It would be nice to see the examples in GEB rewritten this way.

The reason that non-primitive-recursive functions can't be expressed in
this subset of Python is because, as in BlooP, the program has to decide
how many times it may loop before it begins looping.  Therefore every
program is guaranteed to terminate.

Separately, here's a "proof" of a very well-known theorem of computer
science:

>>> from oracles import halt
>>> print halt.__doc__

halt(f) returns 1 if f() will return, and 0 otherwise

>>> def yes():
...     return "yes"

>>> yes()
"yes"

>>> halt(yes)
1

>>> def no():
...    while 1:
...        pass

>>> halt(no)
0

>>> def mu():
...     if halt(mu):
...         while 1:
...             pass

>>> halt(mu)