A cellular automaton is a collection of cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired. Von Neumann was one of the first people to consider such a model, and incorporated a cellular model into his "universal constructor." Cellular automata were studied in the early 1950s as a possible model for biological systems. Comprehensive studies of cellular automata have been performed by S. Wolfram starting in the 1980s, and Wolfram's fundamental research in the field culminated in the publication of his book A New Kind of Science (Wolfram 2002) in which Wolfram presents a gigantic collection of results concerning automata, among which are a number of groundbreaking new discoveries.

The simplest cellular automaton is one-dimensional. The construction rules of a one-dimensional cellular automaton are based on the current state of a cell and its neighboring cells, where the neighbors are the cells to its right and to its left.

One-dimensional rule 30.

Since there are 2 x 2 x 2 = 2^3 = 8 possible binary states for the three cells neighboring a given cell, there are a total of 2^8 = 256 one-dimensional cellular automata, each of which can be indexed with an 8-bit binary number (Wolfram 1983, 2002). For example, the table giving the evolution of rule 30 (30 = 00011110_2) is illustrated above.

Evolution of rule 30.

The evolution of a one-dimensional cellular automaton can be illustrated by starting with the initial state (generation zero) in the first row, the first generation on the second row, and so on. For example, the figure above illustrated the first 20 generations of the rule 30 elementary cellular automaton starting with a single black cell.

The best-known two-dimensional cellular automaton is the Game of Life, introduced by John H. Conway. This cellular automaton runs by placing a number of filled cells on a two-dimensional grid. For each generation, the cells switch on or off depending on the state of their surrounding cells. For a given cell, its eight neighboring cells have their states checked, counting the number of on cells. This amount is then used to determine what will happen to the current cell in the next time step according to the following rules:

1. Death: if the amount is less than 2 or greater than 3, the current cell is switched off.
2. Survival: if the amount is exactly 2, or the amount is exactly 3 and the current cell is on, the current cell is left unchanged.
3. Birth: if the current cell is off and the amount is exactly 3, the current cell is switched on.

Below we have an example of the Game of Life:

Game of Life.

Checkout the code on GitHub for one- and two-dimensional cellular automata.