One-dimensional cellular automaton
A one-dimensional cellular automaton operates on an infinite "tape" of cells. All Turing machines can be emulated by 1D cellular automata with properly set rules and the number of states.
To make the evolution of one-dimensional patterns more visible, they are usually emulated in software such as Golly by non-isotropic 2D automata, in which each new generation of the emulated 1D automaton is born in the line below the original 1D pattern.
Like higher-dimensional cellular automata, 1D automata may operate in different neighborhoods, be totalistic or non-totalistic, isotropic or non-isotropic. The most researched among them are so-called elementary cellular automata, where there are two possible states, labeled 0 and 1, and the rule to determine the state of a cell in the next generation depends on the current state of the cell and its two immediate neighbors, thus operating in 1D Moore neighborhood.
Although such automation may sound primitive, one elementary cellular automaton, known as Rule 110, was proven to be capable of universal computation. Emulating Rule 110 in 2D cellular automata is often used as a proof of their Turing-completeness. Another elementary automaton, known as Rule 54, is suspected of being Turing-complete as well. Both rules have natural spaceships, guns, oscillators and rakes. Breeders are obviously impossible in 1D automata, because infinite growth in 1D space can only be linear. Rule 110 is non-isotropic, while Rule 54 is isotropic. All patterns in both rules are constantly expanding, analogously to explosion in 2D automata, yet exhibiting complex behavior.
See also
External links
- Oscillators in one-dimensional rules (discussion thread) at the ConwayLife.com forums
- Wikipedia
- Elementary cellular automaton at Wikipedia
- Wolfram code at Wikipedia
- Rule 30 at Wikipedia
- Rule 90 at Wikipedia
- Rule 110 at Wikipedia
- Rule 184 at Wikipedia