cellular automaton (CA)

Characteristics of a cellular automaton

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.

Cellular automaton shapes and states

Cellular automata come in different shapes and varieties. The simplest CA is one-dimensional, with cells on a straight line, where each cell can have only two possible states (such as high/low or black/white). However, other shapes are also possible. In a two-dimensional space, common cell shapes are squares, hexagons and cubes.

In theory, a CA can have any number of dimensions, and each cell can have any number of possible states. The state of each cell changes in discrete steps at regular time intervals. At any given time, this state depends on the following:

• its own state in the previous time step; and
• the states of its immediate neighbors in the previous time step.

When a graphical rendition of a CA is viewed, it looks like a "quantized" animated object.

A CA may be constructed on Cartesian grids in arbitrary numbers of dimensions.

Common types of cellular automata

There are many types of CA. The simplest type is a binary, nearest-neighbor, one-dimensional automaton called elementary cellular automata. There are 256 such CAs.

Another type of CA is the nearest-neighbor, k-color, one-dimensional totalistic cellular automata. In the simplest type of this CA, k = 3.

In two dimensions, two of the most well-known CAs are the following:

• H. Conway's Game of Life, a binary totalistic CA
• WireWorld

Understanding elementary cellular automata

Elementary CA is the simplest non-trivial class of CA. In this CA, cells can have two possible values, either 0 or 1. As a result, this CA can be described by a table specifying the state a cell will have in the next generation based on the value of:

• the cell to its left
• the cell itself
• the cell to its right

There are eight possible binary states for the three cells neighboring a particular cell, which means that there are 2⁸ = 256 elementary CA, where each can be indexed with an 8-bit binary number.

The following are key characteristics of elementary CA:

• It is one-dimensional.
• Cells can have only one of two possible values: 0 or 1.
• Here, any cell on the grid depends on the cell itself and two adjacent neighbors, the left and right.
• The state of cells can vary based on generations. The evolution of a one-dimensional CA can be illustrated by starting with the initial state ("generation zero") in the first row, the first generation on the second row, etc.

Classification of cellular automata

Cellular automata were studied as early as the 1950s as a possible model for biological systems. However, it wasn't until the 1980s that research into this area took off, thanks to Stephen Wolfram, a British-American computer scientist. In his book, A New Kind of Science, Wolfram classified CA into the following four classes based on their behavior:

• Class 1. Almost all patterns evolve into a stable, homogenous state.
• Class 2. Almost all initial patterns transform into stable or oscillating.
• Class 3. All initial patterns transform in a chaotic or pseudo-random Local changes to the initial pattern may spread indefinitely.
• Class 4. All initial patterns transform into complex structures that interact with each other in interesting ways.

Two-dimensional CA: John Conway's Game of Life

John Conway's Game of Life (also known simply as Life) is a two-dimensional, totalistic CA that introduces more complexity than an elementary CA, since each cell in the grid has a bigger neighborhood. It is a "universal" (or computation-universal) CA since it can effectively emulate any CA, Turing machine or other system that can be translated into a system known to be universal.

Instead of a one-dimensional line of cells, this two-dimensional CA consists of a matrix of cells. Each generation switches cells on or off, depending on the state of the cells that surround it.

In Life, eight cells surround a given cell. All eight of these cells are checked to see if they are on. On cells are counted, and this count is used to determine what will happen to the current cell. Based on the count, the rules defining Life are as follows:

• Death: If the count is < 2 or > 3, the current cell is switched off.
• Survival: If the count = 2 or the count = 3 and the current cell is on, it is left unchanged.
• Birth: If the current cell is off and the count = 3, it is switched on.

In the Life CA, a pattern that does not change from one generation to the next is known as a still life. It has a period 1. A pattern that cycles through a set of configurations is known as an oscillator. A life pattern with no father pattern is known as a Garden of Eden.

Real-world applications of CA

Below are some of the most popular applications of CA.

Epidemiology

Cellular automata are used to study the evolution of disease epidemics through computer modeling.

Anthropology

In anthropology, CA with fundamental space-time representations are used to model the formation of civil societies.

Sociology

CAs are used to study the causes and effects of civil violence.

Biology

Several biological processes and systems are simulated using CA, including the patterns of some seashells, moving wave patterns on the skin of cephalopods and the behaviors of brain neurons.

Physics

CAs are used to simulate and study physical phenomena, such as gas and fluid dynamics.

Cryptography

CA automata are proposed for use in public key cryptography. They can be utilized to construct pseudorandom number generators, and to design error correction codes.

See also data science applications and use cases, how data science and machine learning platforms advance analytics, how to address the hidden risks of algorithmic decision making and cryptography basics.