By analogy to electronic circuit layouts he realized however that 2D should be enough. … (An example was the so-called Garden of Eden result that there can be configurations in cellular automata that arise only as initial conditions; see page 961 .) … (In 1978 as a possible 1D analog of Life easier to implement on early personal computers Jonathan Millen did however briefly consider what turns out to be the code 20 k = 2 , r = 2 totalistic rule from page 283 .)

The last axiom is a schema (see page 1156 ) that states the principle of mathematical induction: that if a statement is valid for a = 0 , and its validity for a = b implies its validity for a = b + 1 , then it follows that the statement must be valid for all a . … It is not universal, although it makes statements of size n potentially take as many as about 2 2 n steps to prove (though see page 1143 ).

And the point is that if computational irreducibility is present, then there is in a sense all sorts of information about the behavior of a system that can only be found from its rules by doing an irreducibly large amount of computational work. And the analog of this in an axiom system is that there are theorems that can be reached only by proofs that are somehow irreducibly long. So what this suggests is that a theorem might be considered interesting not only if it cannot be derived at all from simpler theorems but also if it cannot be derived from them except by some long proof.

Each gate performs a simple logic operation; for example, letting charge pass in one channel only if charge is present in the other channel. … The memory consists of an array of cells, with the presence or absence of a lump of charge at gates in each cell representing a 1 or 0 value for the bit of data associated with that cell. … Numbers for example are typically represented in base 2 by sequences of 32 or more bits.

The only way to get a random pattern therefore is to have an infinite number of randomly placed black cells in the initial conditions. … Any initial condition that contains black cells only in a limited region will thus lead to a pattern that ultimately has a simple nested form. … Note that the pictures above show only half as many steps of evolution as the corresponding pictures of rule 22 on the previous page .

And this can be achieved in only two ways: either the pattern must be essentially uniform, or it must have a nested structure—just like we see in rule 90. … But there are rather few additive rules, and indeed with two colors and nearest neighbors the only fundamentally different ones are precisely rules 90 and 150. Ultimately, however, additive rules are not the only ones that can emulate themselves.

A blank indicates that I know only that no solution exists below a billion. … Practical methods for resolving the so-called elliptic curve equations in the second column were developed only in the 1980s.

With two possible colors and blocks of size two the only kinds of block cellular automata that conserve the total number of black cells are the ones shown in the second set of pictures—and all of these exhibit rather trivial behavior. … Block cellular automata with two possible colors and blocks of size two that conserve the total number of black cells (the last example has this property only on alternate steps). It so happens that all but the second of the rules shown here not only conserve the total number of black cells but also turn out to be reversible.

The point is that these initial conditions in effect contain only blocks for which rule 126 behaves like rule 90. … Sometimes this will happen, say, for any initial condition that has black cells only in a limited region. But in other cases—like the example of rule 22 on page 263 —rule 90 behavior is obtained only with rather specific initial conditions.

The first picture below shows an extreme example of a class 1 cellular automaton in which after just one step the only sequences that can occur are those that contain only black cells. … The second picture below shows a class 2 cellular automaton that once again evolves to an attractor after just one step. … In the first case, the sequences that can occur are ones that involve only black cells.