Elementary cellular automaton

elementary cellular automata
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors.wikipedia
24 Related Articles

Cellular automaton

cellular automataCACell games (cellular automaton)
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors.
In the 1980s, Stephen Wolfram engaged in a systematic study of one-dimensional cellular automata, or what he calls elementary cellular automata; his research assistant Matthew Cook showed that one of these rules is Turing-complete.

Rule 110

Rule 110 cellular automaton
Nevertheless, there is an elementary cellular automaton (rule 110, defined below) which is capable of universal computation.
The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos.

Wolfram code

binary-decimal notationRule 37R
Stephen Wolfram proposed a scheme, known as the Wolfram code, to assign each rule a number from 0 to 255 which has become standard.
When used on their own without such context, the codes are often assumed to refer to the class of elementary cellular automata, two-state one-dimensional cellular automata with a (contiguous) three-cell neighbourhood, which Wolfram extensively investigates in his book.

Stephen Wolfram

WolframS. WolframStephen
Stephen Wolfram proposed a scheme, known as the Wolfram code, to assign each rule a number from 0 to 255 which has become standard.
He produced a series of papers systematically investigating the class of elementary cellular automata, conceiving the Wolfram code, a naming system for one-dimensional cellular automata, and a classification scheme for the complexity of their behaviour.

Pascal's triangle

Pascal triangleJia Xian triangleKhayyam triangle
The sequence generated is 1, 3, 5, 15, 17, 51, 85, 255, .... This can be obtained by taking successive rows of Pascal's triangle modulo 2 and interpreting them as integers in binary, which can be graphically represented by a Sierpinski triangle.
The pattern produced by an elementary cellular automaton using rule 60 is exactly Pascal's triangle of binomial coefficients reduced modulo 2 (black cells correspond to odd binomial coefficients).

Mathematics

mathematicalmathmathematician
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors.

Computability theory

recursion theorycomputablecomputability
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors.

Turing completeness

Turing-completeTuring completeuniversal
Nevertheless, there is an elementary cellular automaton (rule 110, defined below) which is capable of universal computation.

Generating function

exponential generating functionordinary generating functiongenerating functions
In many cases these sequences have simple, closed form expressions or have a generating function with a simple form.

Jacobsthal number

Jacobsthal–Lucas numberJacobsthal numbers
. This is the sequence of Jacobsthal numbers and has generating function

Sierpiński triangle

Sierpinski triangleSierpinski gasketSierpinski
The sequence generated is 1, 3, 5, 15, 17, 51, 85, 255, .... This can be obtained by taking successive rows of Pascal's triangle modulo 2 and interpreting them as integers in binary, which can be graphically represented by a Sierpinski triangle.

Mersenne prime

Mersenne numberMersenne numbersMersenne primes
. This is the sequence of Mersenne numbers and has generating function

Turing machine

deterministic Turing machineTuring machinesuniversal computer

Rule 30

Rule 30 is an elementary cellular automaton introduced by Stephen Wolfram in 1983.

Rule 90

In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function.

Reversible cellular automaton

reversiblereversible cellular automatareversibility
The simplest possible cellular automata have a one-dimensional array of cells, each of which can hold a binary value (either 0 or 1), with each cell having a neighborhood consisting only of it and its two nearest cells on either side; these are called the elementary cellular automata.

Rule

rulesRule (disambiguation)Ruleset (disambiguation)

Sawtooth (cellular automaton)

sawtooth pattern
For instance, in Rule 90, a one-dimensional elementary cellular automaton, the population size starting from a single live cell follows Gould's sequence, which has a self-similar sawtooth pattern.

Rule 184

cellular automaton 184
Rule 184 and its reflection are the only elementary cellular automata to have this property of number conservation.

Zhegalkin polynomial

Zhegalkin normal form
As an aside, note that this method of calculation corresponds to the method of operation of the elementary cellular automaton called Rule 102.

Conway's Game of Life

Game of LifeConway's LifeConway’s Game of Life
One-dimensional square variations, known as elementary cellular automata, and 3-D square variations have been developed, as have 2-D hexagonal and 2-D triangular variations.