Gödel in effect does this by first converting the statement to one about recursive functions and then—by using tricks of number theory such as the beta function of page 1120 —to one purely about arithmetic.

In general, if one looks along a diagonal n cells in from either edge of the pattern, then the period of repetition can be at most 2 n . … The probability for a block of n adjacent white cells (corresponding to a row in a white triangle) seems quite accurately to approach 2 -n , with the first length 10 such block occurring at step 67 and the first length 20 one occurring at step 515.

If one looks at the history of a single row of cells, it typically looks much like the complete histories we have seen in 1D class 4 cellular automata. … A simpler kind of unbounded growth occurs if one starts from an infinite line of black cells.

Having seen this, one might then wonder whether in fact any system that involves randomness will ultimately produce smooth overall patterns of growth.

regardless of the path one chooses, the overall form of causal network will be essentially the same.

And it is one of the striking observed regularities of the universe that all particles of a given kind—say electrons—seem to be absolutely identical in their properties.

Or do we have no choice but just to specify explicitly the color of every one of the cells it contains?

One might imagine perhaps that while there could in principle be methods of perception that would recognize features beyond, say, repetition and nesting, any single such feature might never occur in a sufficiently wide range of systems to make its recognition generally useful to a biological organism.

And this means that even if the book mentions a term only in passing, I have tended to include it if for one reason or another I think it is likely to be memorable to people with certain experience or interests.

Scanning the digit sequences from the left, one starts with 0 open parentheses, then adds 1 whenever corresponding digits in the x and y coordinates differ, and subtracts 1 whenever they are the same.