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

There is no single agreed-upon definition of "halting" for cellular automaton. Each possible definition of halting produces different busy beaver functions. Here are some examples.

• All 0s: A cellular automaton is said to halt if it reaches a state where every cell has state 0.

• Still life: A cellular automaton is said to halt if it reaches a fixed point in the rule's update function. This definition of halting allows busy beaver functions which count the maximum number of on cells a halting cellular automaton can produce.

• Oscillator: A cellular automaton is said to halt if it reaches a cycle of repeated states. Busy beaver functions for the "longest running" starting pattern or rule can measure the time until the first state which gets repeated, or the time until a state appears twice (which gives a bonus to cellular automata that end up in a long-period oscillator). Busy beaver functions counting the number of "on" states can measure the minimum population, or the maximum population, or the average population, or the population in the first repeating state.

• Oscillating population: A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic.

In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.