Cellular automaton: binary life

Cellular automaton (CA) is a discrete system consisting of separate cells. Those cells are located close to each other on a grid. Every cell can be in one of the defined states, and the number of states must be finite. The state of each cell is updated according to a rule which says how the new state depends on the actual state of the cell and states of cells in the neighborhood. Neighborhood may be defined in many ways, but usually the Moore neighborhood or the Neumann neighborhood is used. States of all cells are updated synchronously.

Moore (8) i Neumann (4) neighborhoods. State of the red cell depends on states of green cells.

Those surnames are surnames of pioneers of cellular automata theory – John von Neumann and Edward F. Moore. Of course, one can design many rules for the automaton, many states, neighborhood types and configurations. The choice of the automaton setup depends on its application. You will need different setups for image processing and restoration, for simulation of tumor cells, and for simulation of forest fire.

The program

Users can change the size of a board, the type of automaton, and the neighborhood type. There are 8 predefined setups of the cellular automaton. The Randomize button gives a possibility of random initialization of all cell states with one of possible states. The Clear button sets the zero'th state for all cells. Buttons Fast, Medium, Slow control the speed of computation. Step performs one step. Left mouse button cycles through possible states of a cell, while right mouse button sets the state to zero.

To run the program, choose your language:

Available automata

The program implements three definitions of automatons: Life, Invasion and March. Every automaton has itd default world state, but it can be changed by the user using button Clear and mouse to "paint" new configurations.

The The Game of Life automaton was created by John Horton Conway in 1970. It is considered by its exceptionality. The definition is very simple; it is based only on two states and three rules, but the behavior is extremely complex. The Game of Life is often compared with the automaton defined by von Neumann. Neumann's automaton is also able to simulate any function using only logical rules, but is founded on 29 states of a cell. The set of cell states includes only two elements "1" and "0". "1" means that a cell is alive (gray), "0" cell is dead.
Rules of the automaton:
1. A dead cell with exactly three live neighbors becomes a live cell.
2. A live cell with two or three live neighbors stays alive.
3. In all other cases, a cell dies or remains dead.

Note that EACH cell follows THE SAME rules in EACH simulation step!

The predefined simple objects found in the simulation grid have their own names:

Blinker	Block	Clock	Glider
Gliders by the Dozen	Light-weight spaceship	Pi Heptomino	R Pentomino
Thunderbird	Toad	Tub

The automata Invasion and March were placed in program for their interesting visual effects. For March automaton the cell can be in one of two states: active (gray) and dormant (white).
Rules of the automaton:
1. If active cell has at least four activated neighbors, it changes state to dormant.
2. If a cell is dormant and has two activated neighbors, it changes state to active.
3. If a cell has three activated neighbor, it changes state to active.
4. In all other cases, a cell is dormant.

For the Invasion (see picture below), there are three states: dormant (white), active (gray), sub-active (dark).
Rules of the automaton:
1. If a cell is active and has at least three activated or sub-activated neighbors, it changes state to sub-active.
2. If a cell is dormant and has at least three activated or sub-activated neighbors, it changes state to active.
3. If a cell is active and has one or two activated or sub-activated neighbors, the cell is still active.
4. In all other cases, a cell is dormant.

Program and text: Magdalena Ławrynowicz

Mentor: Maciej Komosinski