There are however special sequential substitution systems (those with the so-called confluence property discussed on page 1036 ) in which in a certain sense the order of replacements does not matter.

Note that processes such as cellular automaton evolution do not yield networks whose properties are particularly close to those of purely random ones.

It does not help that unlike algorithms physical devices can be affected by their environment, and can also not normally be copied identically.

Using the Principle of Computational Equivalence discussed in Chapter 12 , however, I suspect that it will nevertheless be possible to develop a general theory of what natural selection typically can and cannot do.

In a sense what I do is just to require that the operation of coarse graining correspond to a computation that is less sophisticated than the actual evolution of the system being studied.

The standard way to do this is to set up an error-correcting code in which blocks of m original data elements are represented by a codeword of length n that in effect includes some redundant elements. … But in all cases they tend to be based on rather special mathematical structures which do not seem likely to occur in any system like the brain.

The method can be implemented using Module[{a = Flatten[data], r, s}, {r, s} = Dimensions[data]; Partition[Do[ a 〚 i + {1, s - 1, s, s + 1} 〛 += m (a 〚 i 〛 - If[a 〚 i 〛 < 1/2, 0, 1]), {i, r s - s - 1}]; Map[If[# < 1/2, 0, 1] &, a], s]] In its original version m = {7, 3, 5, 1}/16 , as in the first row of pictures below. … One simple way to do this appears to be to use nested patterns like the ones below.

One way to see that this is not possible is to imagine modifying m to make a machine m' that halts if its input corresponds to a machine that does not halt, but otherwise goes into an infinite loop and does not itself halt.

Note also that as discussed in the main text having maximal entropy does not by any means imply perfect randomness.

The boundaries between regions come from blocks of even numbers of black cells in the initial conditions, and if one does not allow any such blocks, the density oscillations no longer occur.