Universal Computation in Simple One-Dimensional Cellular Automata
Kristian Lindgren
Mats G. Nordahl
Nordita, Blegdamsvej 17, DK-2100 Copenhagen, Denmark
Abstract
The existence of computation-universal one-dimensional cellular automata with seven states per cell for a transition function depending on the cell itself and its nearest neighbors (r = 1), and four states per cell for r = 2 (when next-nearest neighbors also are included), is shown. It is also demonstrated that a Turing machine with m tape symbols and n internal states can be simulated by a cellular automaton of range r = 1 with m + n + 2 states per cell.