Cellular Automaton
Introduction
A cellular automaton (CA) is a discrete model studied in computational mathematics, theoretical physics, computer science, complex systems, and bioinformatics. It consists of a regular grid of cells, each in one of a finite number of states, such as on and off. The grid can be in any finite number of dimensions.
History
The concept of cellular automaton was originally discovered in the 1940s by John Von Neumann while he was attempting to find a theoretical model for self-replicating machines. Von Neumann's initial cellular automaton allowed for a universal constructor that could theoretically create any output that the cellular automaton could compute, given the correct initial state.
Definition
A cellular automaton consists of a regular grid of cells, each in one of a finite number of states. The grid can be in any finite number of dimensions. Time is also discrete, and the state of a cell at time t is a function of the states of a finite number of cells (called its neighborhood) at time t - 1. These rules are then applied iteratively for as many time steps as desired.
Classification
Cellular automata can be classified into a number of different types based on their properties. Some of the most common classifications include totalistic, outer totalistic, and isotropic. Totalistic cellular automata are those in which the future state of a cell depends only on the total number of cells in a particular state in its neighborhood, while outer totalistic cellular automata are those in which the future state of a cell depends on the total number of cells in a particular state in its neighborhood, as well as its own current state. Isotropic cellular automata are those in which the future state of a cell depends only on the number of cells in each state in its neighborhood, regardless of their relative positions.
Applications
Cellular automata have been used in a wide variety of scientific and mathematical fields. They have been used to model biological and chemical systems, to simulate physical phenomena, and to perform computations. Some of the most well-known cellular automata include the Game of Life, a cellular automaton devised by the British mathematician John Horton Conway in 1970, and the Rule 110 cellular automaton, which was proven to be Turing complete by Matthew Cook in 2004.