初等元胞自动机

来自集智百科
跳到导航 跳到搜索

此词条暂由彩云小译翻译,未经人工整理和审校,带来阅读不便,请见谅。

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.

在数学和可计算性理论中,初等细胞自动机是一个一维的细胞自动机,其中有两个可能的状态(标记为0和1) ,决定下一代细胞状态的规则只取决于细胞及其邻近细胞的当前状态。因此,它是最简单的计算模型之一。尽管如此,还是有一个能够进行通用计算的基本细胞自动机。


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:

一个电池及其两个邻近的电池有8种可能的结构。定义细胞自动机的规则必须指定每种可能性的结果状态,因此有256个2 sup 2 sup 3 / sup / sup 可能的初级细胞自动机。提出了一个被称为 Wolfram 代码的方案,给每个规则分配一个从0到255的数字,这个数字已经成为标准。每个可能的当前配置都是按照111,110,... ,001,000的顺序编写的,每个配置的结果状态都是按照相同的顺序编写的,并解释为整数的二进制表示形式。这个数字被认为是自动机的规则号。例如,110 sub d / sub 01101110 sub 2 / sub。所以规则110是由转换规则定义的:


{ | 类“ wikitable”样式“ text-align: center”
111 111 111 110 110 110 101 101 101 100 100 100 011 011 011 010 010 010 001 001 001 000 000 000 current pattern current pattern 电流模式 P=(L,C,R) P=(L,C,R) P (l,c,r)
0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 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

|}


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.

尽管有256个可能的规则,但其中许多规则相互之间的等价性很小,只需对底层几何进行简单的变换即可。第一个这样的转换是通过垂直轴反射,将这个转换应用到给定规则的结果称为镜像规则。这些规则将表现出相同的行为,直至反射通过垂直轴,因此在计算意义上是等价的。


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:

例如,如果规则110的定义通过垂直线反映,则获得以下规则(规则124) :

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

与它们的镜像规则相同的规则称为两极规则。在256个初级细胞自动机中,64个是双基元自动机。


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.

第二个转换是交换定义中0和1的角色。将这种转换应用于给定规则的结果称为互补规则。

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

例如,如果将此转换应用于规则110,我们将得到以下规则

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

重新排序后,我们发现这是第137条规则:

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

有16条规则与它们的补充规则相同。


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.

最后,将前两个变换依次应用于规则,得到镜像互补规则。例如,规则110的镜像互补规则是规则193。有16个规则是相同的镜像互补规则。


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.

在256个初等元胞自动机中,有88个元胞自动机在这些变换下不等价。


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:

研究这些自动机的一种方法是沿着自动机的历史,除了一个单元格的初始状态为1之外,其余的都是0。当规则数为偶数(因此输入000不能计算为1)时,每次都有必要将状态 t 解释为二进制表示的整数,从而生成一个整数序列 a (t)。在许多情况下,这些序列具有简单的封闭形式表达式或具有简单形式的母函数。以下是值得注意的规则:


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

生成的序列是1,3,5,11,21,43,85,171,... 。这是 Jacobsthal 的数字序列,有母函数


[math]\displaystyle{ \frac{1+2x}{(1+x)(1-2x)} }[/math].

[math]\displaystyle{ \frac{1+2x}{(1+x)(1-2x)} }[/math].

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


It has the closed form expression

It has the closed form expression

它具有封闭形式表达式

[math]\displaystyle{ a(t) = \frac{4\cdot 2^t-(-1)^t}{3} }[/math]

[math]\displaystyle{ a(t) = \frac{4\cdot 2^t-(-1)^t}{3} }[/math]

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.

请注意,规则156生成相同的序列。


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

生成的序列是1,5,21,85,341,1365,5461,21845,... 。这就是母函数

[math]\displaystyle{ \frac{1}{(1-x)(1-4x)} }[/math].

[math]\displaystyle{ \frac{1}{(1-x)(1-4x)} }[/math].

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


It has the closed form expression

It has the closed form expression

它具有封闭形式表达式

[math]\displaystyle{ a(t) = \frac{4\cdot 4^t-1}{3} }[/math].

[math]\displaystyle{ a(t) = \frac{4\cdot 4^t-1}{3} }[/math].

数学 a (t) frac {4 cdot 4 ^ t-1}{3} / math。


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.

注意,规则58、114、122、178、186、242和250生成相同的序列。


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

生成的序列是1,7,17,119,273,1911,4369,30583,... 。这就是母函数

[math]\displaystyle{ \frac{1+7x}{(1-x^2)(1-16x^2)} }[/math].

[math]\displaystyle{ \frac{1+7x}{(1-x^2)(1-16x^2)} }[/math].

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


It has the closed form expression

It has the closed form expression

它具有封闭形式表达式

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

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

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.

生成的序列是1,3,5,15,17,51,85,255,..。这可以通过将 Pascal 的三角模2的连续行解释为二进制的整数来得到,这些整数可以用谢尔宾斯基三角形表示。


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.

生成的序列是1,5,17,85,257,1285,4369,21845,... 。这可以通过取帕斯卡三角模2的连续行并将它们解释为以4为底的整数来得到。注意,规则18、26、82、146、154、210和218生成相同的序列。


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

生成的序列是1,7,27,119,427,1879,6827,30039,... 。这可以表示为


[math]\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 } }[/math].

</math>.

数学。


This has generating function

This has generating function

这就是母函数


[math]\displaystyle{ \frac{(1+2x)(1+5x-16x^4)}{(1-x^2)(1-16x^2)} }[/math].

[math]\displaystyle{ \frac{(1+2x)(1+5x-16x^4)}{(1-x^2)(1-16x^2)} }[/math].

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.

生成的序列是1,6,20,120,272,1632,5440,32640,... 。这只是规则60(这是它的镜像规则)生成的序列乘以连续的2的幂。


Rule 110


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.

生成的序列是1,7,21,107,273,1911,5189,28123,... 。这可以通过将(1 + x + x sup 2 / sup)模2的连续幂的系数解释为二进制中的整数得到。


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

生成的序列是1,7,29,115,477,1843,7645,29491,... 。这就是母函数


[math]\displaystyle{ \frac{1+7x+12x^2-4x^3}{(1-x^2)(1-16x^2)} }[/math].

[math]\displaystyle{ \frac{1+7x+12x^2-4x^3}{(1-x^2)(1-16x^2)} }[/math].

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

生成的序列是1,3,5,15,29,55,93,247,... 。这就是母函数


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

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

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

生成的序列是1,7,29,119,477,1911,7645,30583,... 。这就是母函数


[math]\displaystyle{ \frac{1+3x}{(1-x^2)(1-4x)} }[/math].

[math]\displaystyle{ \frac{1+3x}{(1-x^2)(1-4x)} }[/math].

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

生成的序列是1,3,7,15,31,63,127,255,... 。这是梅森数的序列,有母函数


[math]\displaystyle{ \frac{1}{(1-x)(1-2x)} }[/math].

[math]\displaystyle{ \frac{1}{(1-x)(1-2x)} }[/math].

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


It has the closed form expression

It has the closed form expression

它具有封闭形式表达式

[math]\displaystyle{ a(t) = 2\cdot 2^t-1 }[/math].

[math]\displaystyle{ a(t) = 2\cdot 2^t-1 }[/math].

数学 a (t)2 cdot 2 ^ t-1 / math。

Note that rule 252 generates the same sequence.

Note that rule 252 generates the same sequence.

请注意,规则252生成相同的序列。


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

生成的序列是1,7,31,127,511,2047,8191,32767,... 。这是梅森数序列中的每一个其他条目,并且有母函数


[math]\displaystyle{ \frac{1+2x}{(1-x)(1-4x)} }[/math].

[math]\displaystyle{ \frac{1+2x}{(1-x)(1-4x)} }[/math].

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


It has the closed form expression

It has the closed form expression

它具有封闭形式表达式

[math]\displaystyle{ a(t) = 2\cdot 4^t-1 }[/math].

[math]\displaystyle{ a(t) = 2\cdot 4^t-1 }[/math].

数学 a (t)2 cdot 4 ^ t-1 / math。


Note that rule 254 generates the same sequence.

Note that rule 254 generates the same sequence.

请注意,规则254生成相同的序列。



-->

-->


-->

-->


! -- 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.

研究这些自动机行为的第二种方法是从随机状态开始检查它的历史。这种行为可以在 Wolfram 类中得到更好的理解。Wolfram 给出了下面的例子作为每个类的典型规则。

  • 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:

每个计算结果都放在结果源下,创建了系统演化的二维表示。88个不等价的规则如下,由随机的初始条件演化而来:

</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.

在某些情况下,细胞自动机的行为并不会立即显现出来。例如,对于规则62来说,交互结构的发展就像在类4中一样。但是在这些相互作用中,至少有一个结构被湮灭,因此自动机最终进入一个重复的状态,而细胞自动机是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.

规则73是类2,因为任何时候都有两个连续的1被0包围,这个特性在后代中保留。这有效地创建了屏蔽数组不同部分之间的信息流的墙。在两个墙之间的部分有有限数量的可能配置,所以自动机最终必须开始在每个部分内重复,虽然周期可能非常长,如果部分足够宽。在完全随机的初始条件下,这些壁的形成概率为1。但是,如果添加了连续运行0或1的长度必须总是奇数的条件,那么自动机将显示3类行为,因为墙永远不会形成。


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.

规则54是类4,似乎也能够进行通用计算,但是还没有像规则110那样被深入研究。许多相互作用的结构已经编入目录,这些结构加在一起预计足以实现普遍性。


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.


External links

模板:Commons category

Category:Cellular automata

类别: 细胞自动机


This page was moved from wikipedia:en:Elementary cellular automaton. Its edit history can be viewed at 初等元胞自动机/edithistory