# 初等元胞自动机

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. As such it is one of the simplest possible models of computation. Nevertheless, there is an elementary cellular automaton (rule 110, defined below) which is capable of universal computation.

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. As such it is one of the simplest possible models of computation. Nevertheless, there is an elementary cellular automaton (rule 110, defined below) which is capable of universal computation.

## The numbering system

There are 8 = 23 possible configurations for a cell and its two immediate neighbors. The rule defining the cellular automaton must specify the resulting state for each of these possibilities so there are 256 = 223 possible elementary cellular automata. Stephen Wolfram proposed a scheme, known as the Wolfram code, to assign each rule a number from 0 to 255 which has become standard. Each possible current configuration is written in order, 111, 110, ..., 001, 000, and the resulting state for each of these configurations is written in the same order and interpreted as the binary representation of an integer. This number is taken to be the rule number of the automaton. For example, 110d=011011102. So rule 110 is defined by the transition rule:

There are 8 = 23 possible configurations for a cell and its two immediate neighbors. The rule defining the cellular automaton must specify the resulting state for each of these possibilities so there are 256 = 223 possible elementary cellular automata. Stephen Wolfram proposed a scheme, known as the Wolfram code, to assign each rule a number from 0 to 255 which has become standard. Each possible current configuration is written in order, 111, 110, ..., 001, 000, and the resulting state for each of these configurations is written in the same order and interpreted as the binary representation of an integer. This number is taken to be the rule number of the automaton. For example, 110d=011011102. So rule 110 is defined by the transition rule:

{ | 类“ wikitable”样式“ text-align: center”
 current pattern current pattern 电流模式 P=(L,C,R) P=(L,C,R) P (l，c，r) new state for center cell new state for center cell 中央牢房的新状态 N110d=(C+R+C*R+L*C*R)%2 N110d=(C+R+C*R+L*C*R)%2 N 子110子 d / 子(c + r + c * r + l * c * r)% 2 111 111 111 110 110 110 101 101 101 100 100 100 011 011 011 010 010 010 001 001 001 000 000 000 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0

|}

## Reflections and complements

Although there are 256 possible rules, many of these are trivially equivalent to each other up to a simple transformation of the underlying geometry. The first such transformation is reflection through a vertical axis and the result of applying this transformation to a given rule is called the mirrored rule. These rules will exhibit the same behavior up to reflection through a vertical axis, and so are equivalent in a computational sense.

Although there are 256 possible rules, many of these are trivially equivalent to each other up to a simple transformation of the underlying geometry. The first such transformation is reflection through a vertical axis and the result of applying this transformation to a given rule is called the mirrored rule. These rules will exhibit the same behavior up to reflection through a vertical axis, and so are equivalent in a computational sense.

For example, if the definition of rule 110 is reflected through a vertical line, the following rule (rule 124) is obtained:

For example, if the definition of rule 110 is reflected through a vertical line, the following rule (rule 124) is obtained:

{ | 类“ wikitable”样式“ text-align: center”
 current pattern current pattern 电流模式 new state for center cell new state for center cell 中央牢房的新状态 111 111 111 110 110 110 101 101 101 100 100 100 011 011 011 010 010 010 001 001 001 000 000 000 P=(L,C,R) P=(L,C,R) p (l，c，r) 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 N112d+12d=124d=(L+C+L*C+L*C*R)%2 N112d+12d=124d=(L+C+L*C+L*C*R)%2 n sub 112 sub d / sub + 12 sub d / sub 124 sub d / sub / sub (l + c + l * c + l * c * r)% 2

|}

Rules which are the same as their mirrored rule are called amphichiral. Of the 256 elementary cellular automata, 64 are amphichiral.

Rules which are the same as their mirrored rule are called amphichiral. Of the 256 elementary cellular automata, 64 are amphichiral.

The second such transformation is to exchange the roles of 0 and 1 in the definition. The result of applying this transformation to a given rule is called the complementary rule.

The second such transformation is to exchange the roles of 0 and 1 in the definition. The result of applying this transformation to a given rule is called the complementary rule.

For example, if this transformation is applied to rule 110, we get the following rule

For example, if this transformation is applied to rule 110, we get the following rule

{ | 类“ wikitable”样式“ text-align: center”
 current pattern current pattern 电流模式 new state for center cell new state for center cell 中央牢房的新状态 000 000 000 001 001 001 010 010 010 011 011 011 100 100 100 101 101 101 110 110 110 111 111 111 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1

|}

and, after reordering, we discover that this is rule 137:

and, after reordering, we discover that this is rule 137:

{ | 类“ wikitable”样式“ text-align: center”
 current pattern current pattern 电流模式 new state for center cell new state for center cell 中央牢房的新状态 111 111 111 110 110 110 101 101 101 100 100 100 011 011 011 010 010 010 001 001 001 000 000 000 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1

|}

There are 16 rules which are the same as their complementary rules.

There are 16 rules which are the same as their complementary rules.

Finally, the previous two transformations can be applied successively to a rule to obtain the mirrored complementary rule. For example, the mirrored complementary rule of rule 110 is rule 193. There are 16 rules which are the same as their mirrored complementary rules.

Finally, the previous two transformations can be applied successively to a rule to obtain the mirrored complementary rule. For example, the mirrored complementary rule of rule 110 is rule 193. There are 16 rules which are the same as their mirrored complementary rules.

Of the 256 elementary cellular automata, there are 88 which are inequivalent under these transformations.

Of the 256 elementary cellular automata, there are 88 which are inequivalent under these transformations.

## Single 1 histories

One method used to study these automata is to follow its history with an initial state of all 0s except for a single cell with a 1. When the rule number is even (so that an input of 000 does not compute to a 1) it makes sense to interpret state at each time, t, as an integer expressed in binary, producing a sequence a(t) of integers. In many cases these sequences have simple, closed form expressions or have a generating function with a simple form. The following rules are notable:

One method used to study these automata is to follow its history with an initial state of all 0s except for a single cell with a 1. When the rule number is even (so that an input of 000 does not compute to a 1) it makes sense to interpret state at each time, t, as an integer expressed in binary, producing a sequence a(t) of integers. In many cases these sequences have simple, closed form expressions or have a generating function with a simple form. The following rules are notable:

### Rule 28

The sequence generated is 1, 3, 5, 11, 21, 43, 85, 171, ... 模板:OEIS. This is the sequence of Jacobsthal numbers and has generating function

The sequence generated is 1, 3, 5, 11, 21, 43, 85, 171, ... . This is the sequence of Jacobsthal numbers and has generating function

$\displaystyle{ \frac{1+2x}{(1+x)(1-2x)} }$.

$\displaystyle{ \frac{1+2x}{(1+x)(1-2x)} }$.

1 + 2 x {(1 + x)(1-2x)} / math.

It has the closed form expression

It has the closed form expression

$\displaystyle{ a(t) = \frac{4\cdot 2^t-(-1)^t}{3} }$

$\displaystyle{ a(t) = \frac{4\cdot 2^t-(-1)^t}{3} }$

Math a (t) frac {4 cdot 2 ^ t-(- 1) ^ t }{3} / math

Note that rule 156 generates the same sequence.

Note that rule 156 generates the same sequence.

### Rule 50

The sequence generated is 1, 5, 21, 85, 341, 1365, 5461, 21845, ... 模板:OEIS. This has generating function

The sequence generated is 1, 5, 21, 85, 341, 1365, 5461, 21845, ... . This has generating function

$\displaystyle{ \frac{1}{(1-x)(1-4x)} }$.

$\displaystyle{ \frac{1}{(1-x)(1-4x)} }$.

Math frac {1}{(1-x)(1-4x)} / math.

It has the closed form expression

It has the closed form expression

$\displaystyle{ a(t) = \frac{4\cdot 4^t-1}{3} }$.

$\displaystyle{ a(t) = \frac{4\cdot 4^t-1}{3} }$.

Note that rules 58, 114, 122, 178, 186, 242 and 250 generate the same sequence.

Note that rules 58, 114, 122, 178, 186, 242 and 250 generate the same sequence.

### Rule 54

The sequence generated is 1, 7, 17, 119, 273, 1911, 4369, 30583, ... 模板:OEIS. This has generating function

The sequence generated is 1, 7, 17, 119, 273, 1911, 4369, 30583, ... . This has generating function

$\displaystyle{ \frac{1+7x}{(1-x^2)(1-16x^2)} }$.

$\displaystyle{ \frac{1+7x}{(1-x^2)(1-16x^2)} }$.

1 + 7 x }{(1-x ^ 2)(1-16x ^ 2)} / math.

It has the closed form expression

It has the closed form expression

$\displaystyle{ a(t) = \frac{22\cdot 4^t-6(-4)^t-4+3(-1)^t}{15} }$.

$\displaystyle{ a(t) = \frac{22\cdot 4^t-6(-4)^t-4+3(-1)^t}{15} }$.

Math a (t) frac {22 cdot 4 ^ t-6(- 4) ^ t-4 + 3(- 1) ^ t }{15} / math.

### Rule 60

The sequence generated is 1, 3, 5, 15, 17, 51, 85, 255, ...模板:OEIS. 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 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.

### Rule 90

The sequence generated is 1, 5, 17, 85, 257, 1285, 4369, 21845, ... 模板:OEIS. This can be obtained by taking successive rows of Pascal's triangle modulo 2 and interpreting them as integers in base 4. Note that rules 18, 26, 82, 146, 154, 210 and 218 generate the same sequence.

The sequence generated is 1, 5, 17, 85, 257, 1285, 4369, 21845, ... . This can be obtained by taking successive rows of Pascal's triangle modulo 2 and interpreting them as integers in base 4. Note that rules 18, 26, 82, 146, 154, 210 and 218 generate the same sequence.

### Rule 94

The sequence generated is 1, 7, 27, 119, 427, 1879, 6827, 30039, ... 模板:OEIS. This can be expressed as

The sequence generated is 1, 7, 27, 119, 427, 1879, 6827, 30039, ... . This can be expressed as

$\displaystyle{ a(t) = \lt math\gt a(t) = 数学 a (t) \begin{cases} \begin{cases} Begin { cases } 1, & \mbox{if }t = 0 \\[5px] 1, & \mbox{if }t = 0 \\[5px] 1，& mbox { if } t 0[5px ] 7, & \mbox{if }t = 1 \\[7px] 7, & \mbox{if }t = 1 \\[7px] 7，& mbox { if } t 1[7px ] \dfrac{1+5\cdot 4^n}{3} , & \mbox{if }t\mbox{ is even otherwise} \\[7px] \dfrac{1+5\cdot 4^n}{3} , & \mbox{if }t\mbox{ is even otherwise} \\[7px] 1 + 5 cdot 4 ^ n }{3} ，& mbox { if } t mbox { is even otherwise }[7px ] \dfrac{10+11\cdot 4^n}{6} , & \mbox{if }t\mbox{ is odd otherwise} \dfrac{10+11\cdot 4^n}{6} , & \mbox{if }t\mbox{ is odd otherwise} 10 + 11 cdot 4 ^ n }{6} ，& mbox { if } t mbox { is odd otherwise } \end{cases} \end{cases} End { cases } }$.

[/itex].

This has generating function

This has generating function

$\displaystyle{ \frac{(1+2x)(1+5x-16x^4)}{(1-x^2)(1-16x^2)} }$.

$\displaystyle{ \frac{(1+2x)(1+5x-16x^4)}{(1-x^2)(1-16x^2)} }$.

Math frac {(1 + 2 x)(1 + 5 x-16x ^ 4)}{(1-x ^ 2)(1-16x ^ 2)} / math.

### Rule 102

The sequence generated is 1, 6, 20, 120, 272, 1632, 5440, 32640, ... 模板:OEIS. This is simply the sequence generated by rule 60 (which is its mirror rule) multiplied by successive powers of 2.

The sequence generated is 1, 6, 20, 120, 272, 1632, 5440, 32640, ... . This is simply the sequence generated by rule 60 (which is its mirror rule) multiplied by successive powers of 2.

### Rule 150

The sequence generated is 1, 7, 21, 107, 273, 1911, 5189, 28123, ... 模板:OEIS. This can be obtained by taking the coefficients of the successive powers of (1+x+x2) modulo 2 and interpreting them as integers in binary.

The sequence generated is 1, 7, 21, 107, 273, 1911, 5189, 28123, ... . This can be obtained by taking the coefficients of the successive powers of (1+x+x2) modulo 2 and interpreting them as integers in binary.

### Rule 158

The sequence generated is 1, 7, 29, 115, 477, 1843, 7645, 29491, ... 模板:OEIS. This has generating function

The sequence generated is 1, 7, 29, 115, 477, 1843, 7645, 29491, ... . This has generating function

$\displaystyle{ \frac{1+7x+12x^2-4x^3}{(1-x^2)(1-16x^2)} }$.

$\displaystyle{ \frac{1+7x+12x^2-4x^3}{(1-x^2)(1-16x^2)} }$.

1 + 7 x + 12 x ^ 2-4 x ^ 3}{(1-x ^ 2)(1-16x ^ 2)} / math.

### Rule 188

The sequence generated is 1, 3, 5, 15, 29, 55, 93, 247, ... 模板:OEIS. This has generating function

The sequence generated is 1, 3, 5, 15, 29, 55, 93, 247, ... . This has generating function

$\displaystyle{ \frac{1+3x+4x^2+12x^3+8x^4-8x^5}{(1-x^2)(1-16x^4)} }$.

$\displaystyle{ \frac{1+3x+4x^2+12x^3+8x^4-8x^5}{(1-x^2)(1-16x^4)} }$.

1 + 3 x + 4 x ^ 2 + 12 x ^ 3 + 8 x ^ 4-8 x ^ 5}{(1-x ^ 2)(1-16 x ^ 4)} / math.

### Rule 190

The sequence generated is 1, 7, 29, 119, 477, 1911, 7645, 30583, ... 模板:OEIS. This has generating function

The sequence generated is 1, 7, 29, 119, 477, 1911, 7645, 30583, ... . This has generating function

$\displaystyle{ \frac{1+3x}{(1-x^2)(1-4x)} }$.

$\displaystyle{ \frac{1+3x}{(1-x^2)(1-4x)} }$.

1 + 3 x }{(1-x ^ 2)(1-4x)} / math.

### Rule 220

The sequence generated is 1, 3, 7, 15, 31, 63, 127, 255, ... 模板:OEIS. This is the sequence of Mersenne numbers and has generating function

The sequence generated is 1, 3, 7, 15, 31, 63, 127, 255, ... . This is the sequence of Mersenne numbers and has generating function

$\displaystyle{ \frac{1}{(1-x)(1-2x)} }$.

$\displaystyle{ \frac{1}{(1-x)(1-2x)} }$.

Math frac {1}{(1-x)(1-2x)} / math.

It has the closed form expression

It has the closed form expression

$\displaystyle{ a(t) = 2\cdot 2^t-1 }$.

$\displaystyle{ a(t) = 2\cdot 2^t-1 }$.

Note that rule 252 generates the same sequence.

Note that rule 252 generates the same sequence.

### Rule 222

The sequence generated is 1, 7, 31, 127, 511, 2047, 8191, 32767, ... 模板:OEIS. This is every other entry in the sequence of Mersenne numbers and has generating function

The sequence generated is 1, 7, 31, 127, 511, 2047, 8191, 32767, ... . This is every other entry in the sequence of Mersenne numbers and has generating function

$\displaystyle{ \frac{1+2x}{(1-x)(1-4x)} }$.

$\displaystyle{ \frac{1+2x}{(1-x)(1-4x)} }$.

1 + 2 x {(1-x)(1-4x)} / math.

It has the closed form expression

It has the closed form expression

$\displaystyle{ a(t) = 2\cdot 4^t-1 }$.

$\displaystyle{ a(t) = 2\cdot 4^t-1 }$.

Note that rule 254 generates the same sequence.

Note that rule 254 generates the same sequence.

-->

-->

-->

-->

! -- NB.Mathworld 有规则220和222交换的公式 --

## Random initial state

! -- 规则34链接到本节 --

A second way to investigate the behavior of these automata is to examine its history starting with a random state. This behavior can be better understood in terms of Wolfram classes. Wolfram gives the following examples as typical rules of each class.[1]

A second way to investigate the behavior of these automata is to examine its history starting with a random state. This behavior can be better understood in terms of Wolfram classes. Wolfram gives the following examples as typical rules of each class.

• Class 1: Cellular automata which rapidly converge to a uniform state. Examples are rules 0, 32, 160 and 232.
• Class 2: Cellular automata which rapidly converge to a repetitive or stable state. Examples are rules 4, 108, 218 and 250.
• Class 3: Cellular automata which appear to remain in a random state. Examples are rules 22, 30, 126, 150, 182.
• Class 4: Cellular automata which form areas of repetitive or stable states, but also form structures that interact with each other in complicated ways. An example is rule 110. Rule 110 has been shown to be capable of universal computation.[2]

Each computed result is placed under that results' source creating a two-dimensional representation of the system's evolution. The 88 inequivalent rules are as follows, evolved from random initial conditions:

Each computed result is placed under that results' source creating a two-dimensional representation of the system's evolution. The 88 inequivalent rules are as follows, evolved from random initial conditions:

</gallery>

/ 画廊

### Unusual cases

In some cases the behavior of a cellular automaton is not immediately obvious. For example, for Rule 62, interacting structures develop as in a Class 4. But in these interactions at least one of the structures is annihilated so the automaton eventually enters a repetitive state and the cellular automaton is Class 2.[3]

In some cases the behavior of a cellular automaton is not immediately obvious. For example, for Rule 62, interacting structures develop as in a Class 4. But in these interactions at least one of the structures is annihilated so the automaton eventually enters a repetitive state and the cellular automaton is Class 2.

Rule 73 is Class 2[4] because any time there are two consecutive 1s surrounded by 0s, this feature is preserved in succeeding generations. This effectively creates walls which block the flow of information between different parts of the array. There are a finite number of possible configurations in the section between two walls so the automaton must eventually start repeating inside each section, though the period may be very long if the section is wide enough. These walls will form with probability 1 for completely random initial conditions. However, if the condition is added that the lengths of runs of consecutive 0s or 1s must always be odd, then the automaton displays Class 3 behavior since the walls can never form.

Rule 73 is Class 2 because any time there are two consecutive 1s surrounded by 0s, this feature is preserved in succeeding generations. This effectively creates walls which block the flow of information between different parts of the array. There are a finite number of possible configurations in the section between two walls so the automaton must eventually start repeating inside each section, though the period may be very long if the section is wide enough. These walls will form with probability 1 for completely random initial conditions. However, if the condition is added that the lengths of runs of consecutive 0s or 1s must always be odd, then the automaton displays Class 3 behavior since the walls can never form.

Rule 54 is Class 4[5] and also appears to be capable of universal computation, but has not been studied as thoroughly as Rule 110. Many interacting structures have been cataloged which collectively are expected to be sufficient for universality.[6]

Rule 54 is Class 4 and also appears to be capable of universal computation, but has not been studied as thoroughly as Rule 110. Many interacting structures have been cataloged which collectively are expected to be sufficient for universality.

## References

• Weisstein, Eric W. "Elementary Cellular Automaton". MathWorld.

1. Stephen Wolfram, A New Kind of Science p223 ff.
2. Rule 110 - Wolfram|Alpha
3. Rule 62 - Wolfram|Alpha
4. Rule 73 - Wolfram|Alpha
5. Rule 54 - Wolfram|Alpha
6. Martínez, Genaro Juárez; Adamatzky, Andrew; McIntosh, Harold V. (2006-04-01). "Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates" (PDF). Chaos, Solitons & Fractals. 28 (1): 100–111. doi:10.1016/j.chaos.2005.05.013. ISSN 0960-0779.