One-dimensional cellular automaton

From LifeWiki
Jump to navigation Jump to search

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