# Cellular automata

## Cellular automata Topics

Sort by:

### Rule 126

Rule 126 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).Rule 126 is amphichiral, and its complement is rule129.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 27, 127, 387, 1935, 6579, 32767, ... in binary, namely 1, 111, 11011, 1111111, 110000011, ....

### Rule 110

Rule 110 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (OEIS A075437; Wolfram 2002, p. 55).250 iterations of rule 110 are illustrated above.The mirror image is rule 124, the complement is rule 137, and the mirrored complement is rule 193.Starting with a single black cell, successive generations are given by interpreting the numbers 1, 6, 28, 104, 496, 1568, 7360, 27520, ... (OEIS A117999) in binary. Omitting trailing zeros (since the right cells in step of the triangle are always 0) gives the sequence 1, 3, 7, 13, 31, 49, 115, 215, 509, 775, 1805, ... (OEIS A006978), which are simply the previous numbers divided by , and the..

### Game of life

The game of life is the best-known two-dimensional cellular automaton, invented by John H. Conway and popularized in Martin Gardner's Scientific American column starting in October 1970. The game of life was originally played (i.e., successive generations were produced) by hand with counters, but implementation on a computer greatly increased the ease of exploring patterns.The life cellular automaton is run by placing a number of filled cells on a two-dimensional grid. Each generation then switches cells on or off depending on the state of the cells that surround it. The rules are defined as follows. All eight of the cells surrounding the current one are checked to see if they are on or not. Any cells that are on are counted, and this count is then used to determine what will happen to the current cell. 1. Death: if the count is less than 2 or greater than 3, the current cell is switched off. 2. Survival: if (a) the count is exactly 2, or (b) the count..

### Rule 102

Rule 102 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (OEIS A075439; Wolfram 2002, p. 55).Starting with a single black cell, successive generations are given by interpreting the numbers 1, 6, 20, 120, 272, 1632, 5440, 32640, ... (OEIS A117998) in binary. Omitting trailing zeros (the right cells in step of the triangle are always 0) gives 1, 3, 5, 15, 17, 51, 85, 255, 257, 771, ... (OEIS A001317), which are simply the previous numbers divided by and which have binary representation 1, 11; 101, 1111, 10001, ... (OEIS A047999). Surprisingly, this is precisely the Sierpiński sieve.The mirror image is rule 60, the complement..

By choosing appropriate rules, it is possible to achieve many forms of synchronization within cellular automata. One version, known as the firing squad synchronization problem, was introduced by J. Myhill in 1957, although the first published reference did not appear until five years later (Moore 1962). The firing squad synchronization problem seeks to determine a rule in which all cells in a region go into a special state after the same number of steps. The problem was first solved by Moore (1962). A solution using six colors and a minimal number of steps, illustrated above, was subsequently discovered by Mazoyer (1988), who also determined that no similar four-color solutions exist (Wolfram 2002, p. 1035).

### Wireworld

WireWorld is a two-dimensional four-color cellular automaton introduced by Brian Silverman in 1987. The rule for the automaton uses the cell's old value together with the number of its eight neighbors that are set to 1 according to a system that roughly models the flow of currents in wires according to the following rules. 0. The color 0 is considered background, and always stays as background. 1. The color 1 is considered an electron head, and always turns into an electron tail. 2. The color 2 is an electron tail, and always turns into wire. 3. The color 3 is wire, which remains wire unless is 1 or 2, in which case it becomes an electron head. With these rules, digital logic circuits can be constructed, as illustrated above for OR, XOR, and AND gates.In 2002, Nick Gardner demonstrated how two 8-bit binarynumbers could be multiplied with a WireWorld construction using the network above...

### Rule 94

Rule 94 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).Rule 94 is amphichiral, and its complement is 133.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 27, 119, 427, 1879, 6827, 30039, ... (OEIS A118101) in binary, namely 1, 111, 11011, 1110111, 110101011, ... (OEIS A118102). A formula for the the term is given by(1)(E. W. Weisstein, Apr. 12, 2006), so computation of rule 94 is computationally reducible for evolution from a single black cell, in which case it has generating function(2)Rule 94 is capable of exhibiting..

### Von neumann neighborhood

A diamond-shaped neighborhood that can be used to define a set of cells surrounding a given cell that may affect the evolution of a two-dimensional cellular automaton on a square grid. The von Neumann neighborhood of range is defined byvon Neumann neighborhoods for ranges , 1, 2, and 3 are illustrated above. The number of cells in the von Neumann neighborhood of range is the centered square number , the first few of which are 1, 5, 13, 25, 41, 61, ... (OEIS A001844).

### Rule 90

Rule 90 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).Starting with a single black cell, successive generations are given by interpreting the numbers 1, 5, 17, 85, 257, 1285, 4369, 21845, ... (OEIS A038183) in binary, namely as 1, 101, 10001, 1010101, 100000001, ... (OEIS A070886).Rule 90 is amphichiral, and its complement is rule165.The fractal produced by this rule was described by Sierpiński in 1915 and appearing in Italian art from the 13th century (Wolfram 2002, p. 43). It is therefore also known as the Sierpiński sieve, Sierpiński gasket, or Sierpiński triangle...

### Elementary cellular automaton

The simplest class of one-dimensional cellular automata. Elementary cellular automata have two possible values for each cell (0 or 1), and rules that depend only on nearest neighbor values. As a result, the evolution of an elementary cellular automaton can completely be described by a table specifying the state a given cell will have in the next generation based on the value of the cell to its left, the value the cell itself, and the value of the cell to its right. Since there are possible binary states for the three cells neighboring a given cell, there are a total of elementary 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 () is illustrated above. In this diagram, the possible values of the three neighboring cells are shown in the top row of each panel, and the resulting value the central cell takes in the next generation is shown below in the center...

### Universal cellular automaton

A universal cellular automaton is a cellular automaton which, like a Turing machine, exhibits universality. von Neumann proved that an automaton consisting of cells with four orthogonal neighbors and 29 possible states would be capable of simulating a Turing machine for some configuration of about cells (Gardner 1983, p. 227).The outlines of a proof that the two-dimensional game of life outer-totalistic cellular automaton is universal were given by Berlekamp, Conway, and Guy (1982) and independently by Gosper (Gardner 1983, pp. 250-253). Around 2000, a Turing machine was explicitly implemented in life by P. Rendell (Rendell, Adamatzky 2001). While Rendell's machine can be made into a "true" universal computer simply by making his tape infinite, he neither noted this fact nor provided an actual construction of a universal Turing machine. Subsequently, on November 11, 2002, P. Chapman constructed..

### Rule 62

Rule 62 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).The mirror image is rule 118, complement is rule 131, and mirrored complement is rule 145.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 25, 111, 433, 1751, 7033, 28047, ... in binary, namely 1, 111, 11001, 1101111, 110110001, ....

### Totalistic cellular automaton

A totalistic cellular automaton is a cellular automata in which the rules depend only on the total (or equivalently, the average) of the values of the cells in a neighborhood. These automata were introduced by Wolfram in 1983. Like an elementary cellular automaton, the evolution of a one-dimensional totalistic cellular automaton can completely be described by a table specifying the state a given cell will have in the next generation based on the average value of the three cells consisting of the cell to its left, the value the cell itself, and the value of the cell to its right.For a -color one-dimensional totalistic automaton, there are possible states for the average of three cells neighboring a given cell, and a total of -color totalistic cellular automata, each of which can be indexed with an -digit -ary number, known as a "code." For example, the table giving the evolution of the 3-color code is illustrated above. In this diagram,..

### Rule 60

Rule 60 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (OEIS A075438; Wolfram 2002, p. 55).Starting with a single black cell, successive generations are given by interpreting the numbers 1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, ... (OEIS A001317) in binary (where left cells in step of the triangle are always 0), namely 1, 11, 101, 1111, 10001; ... (OEIS A047999).The mirror image is rule 102, the complement is rule 195, and the mirrored complement is rule 153.Rule 60 is one of the eight additive elementary cellular automata (Wolfram 2002, p. 952)...

### Rule 250

Rule 250 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (OEIS A071028; Wolfram 2002, p. 55).For initial conditions of a single black cell, this rule produces identical evolution to rules 50, 58, 114, 122, 178, 186, and 242, which are precisely those with binary representation .Rule 250 is a generalized additive elementary cellular automata under the operation OR() (Wolfram 2002, p. 952), where is the value of the neighboring cell to the left and is the value of the neighboring cell to the right...

### Rule 54

Rule 54 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55). Rule 54 is conjectured, but not proven, to be universal.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 17, 119, 273, 1911, 4369, 30583, ... (OEIS A118108) in binary, namely 1, 111, 10001, 1110111, 100010001, ... (OEIS A118109). The decimal value of the th iteration is given in closed form by(1)(E. W. Weisstein, Apr. 13, 2006), so computation of rule 54 is computationally reducible for an initial configuration consisting of a single black cell. has generating function(2)Rule..

### Rule 222

Rule 222 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).Rule 222 is amphichiral, and its complement is rule132.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 31, 127, 511, 2047, 8191, ... (OEIS A083420) in binary, namely 1, 111, 11111, 1111111, 111111111, .... The th term is given bywhich are Mersenne numbers, so rule 222 is computationallyreducible for an initial configuration consisting of a single black cell...

### Rule 50

Rule 50 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).Note that for initial conditions of a single black cell, rule 50 is equivalent to rules 58, 114, 122, 178, 186, 242, and 250, which are precisely those rules with binary representation . Variants obtained by complementing and mirror reversing and complementing are rules 160, 161, 162, 163, 176, 177, 178, and 179.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, ... (OEIS A002450) in binary, namely 1, 101, 10101, ... (OEIS A071028). The th term..

### Rule 220

Rule 220 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).The mirror image, complement, and mirror complement are rules 206, 196, and 140, respectively.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 3, 7, 15, 31, 63, 127, 255, ... (OEIS A083420) in binary, namely 1, 11, 111, 1111, .... Or including leading zeros, 1, 011, 00111, 0001111, ... (OEIS A118175). The th term is given bywhich are alternate Mersenne numbers, so rule 220 is computationally reducible for an initial configuration consisting of a single black cell...

### Rule 30

Rule 30 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).250 iterations of rule 30 are illustrated above.Starting with a single black cell, successive generations are given by interpreting the numbers 1, 7, 25, 111, 401, 1783, 6409, 28479, 102849, ... (OEIS A110240) in binary, namely 1, 111, 11001, 1101111, 110010001, ... (OEIS A070950).Rule 30 is the mirror image, complement, and mirror complement of rules 86, 135, and 149, respectively.Rule 30 is of special interest because it is chaotic (Wolfram 2002, p. 871), with central column given by 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, ... (OEIS A051023)...

### Cellular automaton

A cellular automaton is a collection of "colored" 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 (Wolfram 2002, p. 48). 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 Season 2 episode..

### Rule 190

Rule 190 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).The mirror image, complement, and mirror complement are rules 246, 130, and 144, respectively.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 29, 119, 477, 1911, 7645, 30583, ... (OEIS A037576) in binary, namely 1, 111, 11101, 1110111, 111011101, ... (OEIS A118111). The th term is given by the first terms of the quaternary sequence 131313..., or, more explicitly, by(1)(2)(E. W. Weisstein, Apr. 13, 2006). Rule 190 is therefore computationally reducible for an..

### Rule 28

Rule 28 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).The mirror image, complement, and mirror complement are rules 70, 199, and 157, respectively. For initial conditions consisting of a single black cell, it is equivalent to rule 156, since both have binary representations of the form . The mirror image, complement, and mirrored complement of rule 156 are rules 198, 198, and 156, respectively (in other words, rule 156 is invariant under the combined complementing and mirror imaging operations).Starting with a single black cell, successive generations , 1, ... are given by interpreting the Jacobsthal..

### Bootstrap percolation

A two-dimensional binary () totalistic cellular automaton with a von Neumann neighborhood of range . It has a birth rule that at least 2 of its 4 neighbors are alive, and a survival rule that all cells survive. steps of bootstrap percolation on an grid with random initial condition of density can be implemented in the Wolfram Language asWith[{n = 10, p = 0.1, s = 20}, CellularAutomaton[ {1018, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, Table[If[Random[Real] < p, 1, 0], {s}, {s}], n ]]If the initial condition consists of a random sparse arrangement of cells with density , then the system seems to quickly converge to a steady state of rectangular islands of live cells surrounded by a sea of dead cells. However, as crosses some threshold on finite-sized grids, the behavior appears to change so that every cell becomes live. Several examples are shown above on three grids with random initial conditions and different starting densities.However, this..

### Rule 188

Rule 188 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).The mirror image, complement, and mirror complement are rules 230, 194, and 152, respectively.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 3, 5, 15, 29, 55, 93, 247, 477, ... (OEIS A118173) in binary, namely 1, 011, 00101, 0001111, 000011101, ... (OEIS A118174). The th iteration has generating function(1)and closed form(2)

### Rule 182

Rule 182 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).Rule 182 is amphichiral and has mirror complementrule 146.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 21, 127, 381, 1911, 5461, 32767, 98301, ... in binary, namely 1, 111, 10101, 1111111, 101111101, ....

### Rule 158

Rule 158 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).The mirror image, complement, and mirror complement are rules 214, 134, and 148, respectively.Starting with a single black cell, successive generations , 1, ... are given by interpreting the numbers 1, 7, 29, 115, 477, 1843, 7645, ... (OEIS A118171) in binary, namely 1, 111, 11101, 1110011, 111011101, ... (OEIS A118172).The decimal value of the th iteration is given in closed form by(E. W. Weisstein, Apr. 13, 2006), so computation of rule 54 is computationally reducible for an initial configuration consisting of a single..

### Automata theory

The mathematical study of abstract computing machines (especially Turingmachines) and the analysis of algorithms used by such machines.A connection between automata theory and number theory was provided by Christol et al. (1980), who showed that a sequence is generated by a -automaton iff the formal power series with coefficients is algebraic on the field of rational elements , where and are polynomials with coefficients in the finite field .

### Rule 150

Rule 150 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (Wolfram 2002, p. 55).Starting with a single black cell, successive generations are given by interpreting the numbers 1, 7, 21, 107, 273, 1911, 5189, ... (OEIS A038184) in binary, namely 1, 111, 10101, 1101011, 100010001, ... (OEIS A118110).Rule 150 is one of the eight additive elementary cellular automata (Wolfram 2002, p. 952).

### Moore neighborhood

A square-shaped neighborhood that can be used to define a set of cells surrounding a given cell that may affect the evolution of a two-dimensional cellular automaton on a square grid. The Moore neighborhood of range is defined byMoore neighborhoods for ranges , 1, 2, and 3 are illustrated above. The number of cells in the Moore neighborhood of range is the odd squares , the first few of which are 1, 9, 25, 49, 81, ... (OEIS A016754).

An additive cellular automaton is a cellular automaton whose rule is compatible with an addition of states. Typically, this addition is derived from modular arithmetic. Additive rules allow the evolution for different initial conditions to be computed independently, then the results combined by simply adding. The results for arbitrary starting conditions can therefore be computed very efficiently by convolving the evolution of a single cell with an appropriate convolution kernel (which, in the case of two-color automata, would correspond to the set of initially "active" cells).A simple example of an additive cellular automaton is provided by the rule 90 elementary cellular automaton. As can be seen from the graphical representation of this rule, the rule as a function of left, central, and right neighbors is simply given by the sum of the rules for the left and right neighbors taken modulo 2, where white cells are assigned the..