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. CAs have been suggested for possible use in public key cryptography, as well as for applications in geography, anthropology, political science, sociology and physics, among others.
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:
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:
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.
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:
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:
There are eight possible binary states for the three cells neighboring a particular cell, which means that there are 28 = 256 elementary CA, where each can be indexed with an 8-bit binary number.
The following are key characteristics of elementary CA:
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:
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:
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.
Below are some of the most popular applications of CA.
Cellular automata are used to study the evolution of disease epidemics through computer modeling.
In anthropology, CA with fundamental space-time representations are used to model the formation of civil societies.
CAs are used to study the causes and effects of civil violence.
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.
CAs are used to simulate and study physical phenomena, such as gas and fluid dynamics.
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.
23 Dec 2021