But the particular kinds of systems I have discussed for both strings and networks in the past few sections [ 10 , 11 , 12 ] do have a certain locality, in that each individual replacement they make involves only a few nearby elements. … For the different elements in the system are always just laid out in a one-dimensional string, with the result that local replacement rules can only ever propagate effects to nearby elements in the string—much like in a one-dimensional cellular automaton. … For as we discussed several sections ago —and will discuss again in the final sections of this chapter —there will typically be only an approximate correspondence between the structure of the network and the structure of ordinary space.

The maps shown can be thought of as being made by taking an infinitely dense limit of the array of pictures on the facing page , but keeping only what one sees in each picture by looking through a peephole at a particular position relative to the original stem.

[No text on this page] An example of how a cellular automaton with three possible colors and nearest-neighbor rules can be emulated by a cellular automaton with only two possible colors but a larger number of neighbors (in this case five on each side).

In case (a), only a limited number of cells ever become active.

And as the pictures suggest, rules which yield more complex behavior tend to be able to tolerate only smaller sizes of perturbations. … With only 2 or 3 black cells, the sequence in the center of the pattern does not change.

For even programs with some of the very simplest possible rules yield highly complex behavior, while programs with fairly complicated rules often yield only rather simple behavior. … A rather straightforward one, illustrated in the first set of pictures A sequence of elementary cellular automata whose rules differ from one to the next only at one position (a Gray code sequence).

But it seems likely that as one increases t , no ordinary Turing machine or cellular automaton will ever be able to guarantee to solve the problem in a number of steps that grows only like some power of t . … The pictures at the top show that in case (a) stripes up to height 3 can be produced, in case (b) up to height 2, and in case (c) only up to height 1. The pictures at the bottom indicate in black for which of the 2 t + 1 successive left-hand sequences of t + 1 cells it is impossible to get stripes of respectively heights 1 and 2.

The pattern continues to expand on the left forever, but only the part that fits across each page is shown.

The pattern continues to expand on the left forever, but only the part that fits across each page is shown.

The pattern continues to expand on the left forever, but only the part that fits across each page is shown.