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)