IV. Cellular Automaton

An automaton (/ɔːˈtɒmətən/; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.

A cellular automaton (CA) is a collection of cells arranged in a grid of specified shape, such that each cell changes state as a function of time, according to a defined set of rules driven by the states of neighboring cells.

A CA is a collection of colored cells or atoms on a grid of a specified shape. Each cell is in one of a finite number of states. This computational model is both abstract and spatially and temporally discrete.

Computational means the model can compute functions and solve algorithmic problems. Abstract refers to the fact that a CA can be specified in purely mathematical terms. A CA is discrete in both space and time, which means that in each time unit, the cells that constitute the CA represent one of a finite set of states. Additionally, the cells in a grid evolve in parallel at discrete time steps by considering the states of neighboring cells.

As a result, the evolution of the CA through several discrete time steps occurs based on a set of rules founded on the states of neighboring cells. These rules can be iteratively applied for as many time steps as required.

Typical characteristics of a CA are the following:

• The cells in a CA reside on a grid which has a specified shape (square, triangle, hexagon, etc.) and exist in a finite number of dimensions.
• Each cell on the grid has a state. While there are numerous finite possibilities of the state, the simplest state form is usually ON or OFF (or TRUE/FALSE or 1/0).
• The cells adjacent to one cell constitute its neighborhood. Cells in a neighborhood affect each other, and each cell on the CA grid has a neighborhood.