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.

Cellular automata may have:

• Multiple number of dimensions.
• Multiple "alive" cell states.
• Various neighborhood radius and shape.

Busy Beaver function

Halting conditions

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.

• Oscillating population relative to a background pattern: In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.

The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ether. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.