Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

computer within a predictable length of time is also decidable inside TNT. Or, one final restatement of the same thing: If a Blo ...

Program being # 1, the second shortest being #2, etc. Of course, there will be many programs tied for each length. To break such ...

The Diagonal Method Very well-now we apply the "twist": Cantor's diagonal method. We shall take this catalogue of Blue Programs ...

ing the length of calculation of B luediag [N]. This is an "infinite conspira- cy", related to the Tortoise's notion of "infinit ...

example, that we subtract 1 from the diagonal digits (with the convention that 1 taken from 0 is 9). Then our number d will be: ...

FIGURE 73. Georg Cantor. Cantor's proof uses a diagonal in the literal sense of the word. Other "diagonal" proofs are based on a ...

the whole trick, lock, stock, and barrel, including its insidious repeatability, into account somehow. It is an interesting exer ...

This feature will allow us to write tests in FlooP for such properties as wondrousness and the Tortoise property-tests which we ...

a very long Godel number. For instance, the shortest BlooP function (which is also a terminating FlooP program)- DEFINE PROCEDUR ...

program and then waving a termination tester over the program is not unlike the idea of testing a koan for genuineness by coding ...

A complete pool of all call-less FlooP programs which calculate functions of exactly one input parameter, and which terminate fo ...

is called the Church-Turing Thesis. If we accept the CT-Thesis, we have to conclude that "GlooP" is a myth-there are no restrict ...

vided into two realms: (1) those which are computable by terminating FlooP programs: these are said to be general recursive; and ...

Air on G's String The Tortoise and Achilles have just completed a tour of a porridge factory. Achilles: You don't mind if I chan ...

FIGURE 74. Above and Below, by M. C. Escher (lithograph, 1947). ...

(Achilles opens the door. They enter, and begin climbing the steep helical staircase inside the tower.) Tortoise (puffing slight ...

"preceded" to the idea of precedence on a printed sheet, rather than elaborate entries into a banquet room. Achilles: All right. ...

Achilles: Because it's so pointless. Here's another one for you: "WILL BE BOYS" WILL BE BOYS. Now what does that mean? Honestly, ...

Tortoise: What do you mean? Sentences can't talk. Achilles: No, but they REFER to things-and this one refers directly- unambiguo ...

sort of accident. Usually Sentences Q and P are entirely unlike each other; but with the right choice for the blank in Sentence ...