Relation to 1D cellular automata A picture that shows the evolution of a 1D cellular automaton can be thought of as a 2D array of cells in which the color of each cell satisfies a constraint that relates it to the cells above according to the cellular automaton rule.

This will not happen, however, for size ratios ≤ 2/ √ 3 - 1 ≃ 0.15 , since then the small circles can fit into the interstices of an ordinary hexagonal pattern, yielding a filling fraction 1/18(17 √ 13 - 24) π ≃ 0.95 . … At step t , 3 t-1 circles are added for each original circle, and the network of tangencies among circles is exactly example (a) from page 509 . … In the limit of an infinite number of steps the filling fraction tends to 1, while the region left unfilled has a fractal dimension of about 1.3057.

In Cantor's theory ω + 1 is still larger (though 1 + ω is not), as are 2 ω , ω 2 and ω ω . … Subsequent solutions ( ε 1 , ..., ε ω , ..., ε ε 0 , ...) define larger ordinals, and one can go on until one reaches the limit ε ε ε ... , which is the first solution to ε α  α . … Yet as discussed on page 1127 , one can also consider larger cardinal numbers, such as ℵ 1 , considered in connection with the number of real numbers, and so on.

Indeed, even after say 1,048,576 steps—or any number of steps that is a power of two—the array of cells produced always turns out to correspond just to a simple superposition of two or three shifted copies of the initial conditions.

The left edge of the pattern moves 1 cell every 2 steps; the boundary between repetition and randomness moves on average 0.17 cells per step.

[Structures in] other 2D cellular automata The general problem of finding persistent structures is much more difficult in 2D than in 1D, and there is no completely general procedure, for example, for finding all structures of any size that have a certain repetition period.

The examples shown in detail in the main text all have the feature that the block size b and number of steps t are matched, so that r t = b (where the range r = 1 for elementary rules). … In any 1D cellular automaton the color of a particular cell can always be determined from the colors t steps back of a block of 2 r t + 1 cells (compare pages 605 and 960 ).

Multidimensional multiway systems As a generalization of multiway systems based on 1D strings one can consider systems in which rules operate on arbitrary blocks of elements in an array in any number of dimensions.

And this number increases very rapidly with the size n : for 5 cells there are already 32 states, for 10 cells 1024 states, for 20 cells 1,048,576 states, and for 30 cells 1,073,741,824 states.

History [of universality in 1D cellular automata] The fact that 1D cellular automata can be universal was discussed by Alvy Ray Smith in 1970—who set up an 18-color nearest-neighbor cellular automaton rule capable of emulating Marvin Minsky 's 7-state 4-color universal Turing machine (see page 706 ). ( Roger Banks also mentioned in 1970 a 17-color cellular automaton that he believed was universal.) But without any particular reason to think it would be interesting, almost nothing was done on finding simpler universal 1D cellular automata. … A piece published in Scientific American in 1985 describing my interest in finding simple 1D universal cellular automata led me to receive a large number of proofs of the fact (already well known to me) that 1D cellular automata can in principle emulate Turing machines.