Smiths Two-Dimensional Construction

Von Neumann was the first to design a cellular automaton capable of universal computation. Since then many others became interested in the problem and either improved on his original construction or have developed alternative constructions. An early example was Alvy Ray Smith (1971), who constructed a series of progressively simpler cellular automata capable of universal computation. The first in the series was a two-dimensional cellular automaton Mg that simulates a given Turing machine M in real time —that is, there is a one-to-one correspondence between the time steps of Mg and the time steps of M. 

The row of cells above the tape row contains one cell that simulates the tape head (labeled h, containing state P). It is directly above the cell (labeled s) whose symbol 5q is to be scanned at time t. Two other cells are necessary to label cells a and b, the cells directly to the left and right of cell h. All cells except the tape cells and h are in the quiescent state. 

In this way. Mg simulates any given Turing machine M in real time. As a corollary, a CA Us can be constructed in this way to simulate a universal Turing machine U in real time. (For example, Minsky (1967) described a 6-state, 6-symbol universal Turing machine, so a two-dimensional, 7-state CA can be constructed that simulates it in real time.) In his paper. Smith gives several other variations of the original construction with different number of states, different neighborhood templates, and one-dimensional architectures. 

It should be noted that this approach to universal computation in CAs differs from von Neumann s in that Smith s construction simulates a particular Turing machine M—a different construction is needed for each different Turing machine—whereas von Neumann s construction can simulate any Turing machine by setting up the initial configuration in the correct way. Von Neumann s construction, on the other hand, does not simulate Turing machines in anything like real time. 

Many alternative schemes for simulating Turing machines in cellular automata have been formulated over the years. For example, Lindgren and Nordahl (1990) constructed an r = 1, A = 7 one-dimensional CA in which tape symbols were represented by stationary cell states (as in Smith s construction) but in which the tape head (with internal state) was represented as a left- or right-moving particle —a propagating set of CA states. 

---