Emulating Other Systems with Cellular Automata…The pictures below show how a cellular automaton can evaluate any logic expression that is given in a certain form. … A cellular automaton which emulates basic logic circuits. The underlying rules for the cellular automaton are exactly the same in each case, and involve nearest neighbors and five possible colors for each cell.

Emulating Cellular Automata with Other Systems…The basic idea is to have the active cell in the mobile automaton sweep backwards and forwards, updating cells as it goes, in such a way that after each complete sweep it has effectively performed one step of cellular automaton evolution. Examples of mobile automata emulating cellular automata. In case (a) the rules for the mobile automaton are set up to emulate the rule 90 elementary cellular automaton; in case (b) they are set up to emulate rule 30.

So are moving structures in fact possible in the code 357 cellular automaton? … Persistent structures in the code 357 cellular automaton from page 282 obtained by testing the first two billion possible initial conditions. … No persistent structures of any size exist in this cellular automaton with repetition periods of less than 5 steps.

TEST A cellular automaton with a slightly different rule. … TEST 2 A cellular automaton that produces an intricate nested pattern. … In the numbering scheme of Chapter 3 , it is cellular automaton rule 90.

Computations in Cellular Automata…Computations in Cellular Automata I have said that the evolution of a system like a cellular automaton can be viewed as a computation. … So in effect this cellular automaton can be viewed as computing whether a given number is even or odd. … The cellular automaton follows elementary rule 132, as shown on the bottom left.

Mobile Automata One of the basic features of a cellular automaton is that the colors of all the cells it contains are updated in parallel at every step in its evolution. … Like a cellular automaton, a mobile automaton consists of a line of cells, with each cell having two possible colors. But unlike a cellular automaton, a mobile automaton has only one "active cell" (indicated here by a black dot) at any particular step.

Emulating Cellular Automata with Other Systems…And this implies that it is possible to construct for example a mobile automaton which emulates the universal cellular automata that we discussed a couple of sections ago. Such a mobile automaton must then itself be universal, since the universal cellular automaton that it emulates can in turn emulate a wide range of other systems, including all possible mobile automata. … And once again, by emulating the universal cellular automaton, it is then possible to construct a universal Turing machine.

[No text on this page] Cellular automaton evolution illustrating the phenomenon of undecidability. … The cellular automaton rule used is a 4-color totalistic one with code 1004600. Whether a pattern in a cellular automaton ever dies out can be viewed as analogous to a version of the halting problem for Turing machines.

[No text on this page] Examples of applying various rules for cellular automaton evolution to the sequences from page 594 . The picture at the left-hand end of each row is chosen to show the typical behavior of each cellular automaton, given arbitrary initial conditions. Each cellular automaton rule in effect corresponds to a different statistical analysis procedure.

And so the picture below shows what one cellular automaton does over the course of ten steps. The cellular automaton consists of a line of cells, each colored either black or white. … TEST A representation of the rule for the cellular automaton shown above.