Cellular automaton

Cellular automata (CA) are discrete, abstract computational systems that consist of a regular grid of cells, each in a finite number of states. The grid evolves in discrete time steps according to a local transition rule based on the states of neighboring cells. Despite their simple definition, cellular automata can exhibit complex behavior, including chaos, self-replication, and universal computation.

The simplest nontrivial CA are elementary cellular automata (1D, binary states, radius-1 neighborhood).

The rule is defined by an 8-bit lookup table (bits for patterns 111 to 000), numbered 0 to 255. For instance:

• Rule 110: Known to be Turing-complete.
• Rule 30: Produces chaotic, pseudorandom patterns.

Busy Beaver function

TODO