30,000美元用于解决细胞自动机规则30的问题-来自Stephen Wolfram的竞赛

我博客中的原始翻译


比赛网站

让我们向读者解释“规则30”的含义-这是一个基本的细胞自动机（请参阅Wiki ），其在二进制数系统中的状态（基于旧细胞构建新细胞水平的规则）设置为0-0-0-1-1-1。 -1-0，可以用十进制表示法解释为30。

那一切从哪里开始呢？ -“规则30”

令人难以置信的简单事物怎么会产生令人难以置信的复杂事物 ？ 自从我第一次熟悉规则30以来已经快40年了，但是它仍然让我感到惊讶和高兴。 长期以来，它成为我在科学史上个人最喜欢的发现，多年来，它改变了我的整个世界观，并使我对科学，技术，哲学等有了多种新型理解 。

但是即使经过了这么多年，我们仍然无法获得关于规则30的许多基本概念。 因此，我认为是时候应该采取一切可能的措施，以刺激确定这些基本模式的基本集合的过程。

因此，今天我向申请人提供30,000美元的总奖金，用于回答有关规则30的三个主要问题。

规则30非常简单：

有一系列黑白单元格（单元格）的序列，给定特定的黑白单元格行，确定下面一行中的单元格的颜色，分别查看每个单元格及其相邻的相邻单元格，然后将以下简单替换规则应用于它们，即：

代号

RulePlot[CellularAutomaton[30]]

[观看视频，该视频在几分钟内讲述了细胞自动机和规则30的本质-译者注]

如果从一个黑格开始，会发生什么？ [取一排白色单元格，两边无限，一个黑色单元格，然后将上面显示的规则应用于该行，获得一个新行，等等-译者注 ]假设（我本人起初是这样做的）规则非常简单，并且根据其工作获得的模板也应相应地简单。 但是，如果您进行实验，您将看到算法的前50个步骤之后会发生什么：


自然地，我们可以假设，由于该算法，将获得简单得多的数学对象。 但是，这是前300个步骤之后发生的情况：



这表明在金字塔的左侧有一定的图案 。 但是与此同时，此模板的许多方面看起来都是随机形成的 。

如此简单的规则最终会导致如此复杂的系统行为，这是不可理解的。 基于此，我得出的结论是，在所有可能的计算机程序的计算领域中 ，这种行为非常普遍，甚至在几乎所有地方都如此。

基于这种假设，我根据观察简单算法操作的原理，开发了一种形成全新科学类型的方法 。

逐渐地，越来越多的证据积累了这些原则。

但是，让我们回到规则30，详细考虑它允许我们做什么，以及它的用途是什么？ 关于该算法的行为到底能说什么？ 显而易见的是，即使是最明显问题的答案也很困难。

即使经过几十年没有找到答案，我仍然决定是时候问一些有关规则30的具体问题，同时用大量现金奖励来刺激这一领域。

我已经在2007年尝试做类似的事情，为回答有关特定Turing机器的基本问题而设立了奖项 。 在这种情况下，结果是肯定的，并且不需要很长时间即可等待。 仅仅几个月后，这个奖项就获得了 -永久地确定了最简单的通用图灵机是什么，并且非常有说服力地证明了我先前开发的计算等效性的一般原理 。

规则30竞赛再次为解决关键任务设定了目标，即： 规则30的行为有多复杂 ？ 每个任务都以其自己的方式，特别是在这个领域提出了一个问题。 与规则30本身一样，它们在原始设置上都看似简单。 尽管如此，对它们中的任何一个的解决方案都将是一项巨大的成就，最终将有助于阐明计算宇宙形成特性的基本原理，而这些基本原理远远超出了规则30的规定。

我从事这些问题的工作已超过35年 。 一直以来，我一直试图在一致的数学或计算思维框架内找到正确的想法，目的是最终解决这些问题中的至少一个。 现在，我想向整个世界社区开放这一过程。 但是，我很想知道在解决这些问题上可以实现什么以及在这种情况下可以使用什么方法。

规则30-要解决的任务

对于规则30下的竞争任务，我优先考虑规则30算法的关键特征之一，即： 中心列单元格形成的明显随机性 。 从一个黑色单元格开始，然后查看此列中单元格的颜色值顺序，您将得出结论，它们是随机的：




但是它们在什么意义上是“真正随机的”呢？ 并可以证明这一假设吗？ 在竞赛框架内设置的每个任务都使用其自己的随机性标准，然后根据该标准询问序列是否是随机的。

任务1：中央列是否始终保持非周期性？

考虑规则30中心栏的开头：




不难发现此列中的值没有重复-这不是周期性的。 但是挑战是，中心柱会根本变成周期性的吗？ 通过启动规则30，我们看到该序列即使在前十亿步中也不会变为周期性。 为了确定并证明这一点需要做什么。

这是此序列的前一百万个和前十亿个值所在的链接（ Wolfram数据仓库 ）。

任务2：中心列中单元格的每种颜色（黑色或白色）是否平均相等？

这是我们在Rule 30算法的中心列中按更多步骤依次计算黑白单元的数量时所得到的：




对于黑白电池，结果肯定接近相等。 这里有问题的（问题的问题）是以下问题： 该关系是否随着循环中步数的增加而收敛到1 。

任务3：计算中心列的第n个单元格是否至少需要O（ n ）个运算？

要在中心列中找到第n个单元格，您始终可以简单地将规则30运行n步，计算下图中所选菱形内所有单元格的值：




但是，如果直接这样做，它将 n ^2个单独的单元更新，因此，所需的计算能力随着O（ n ² ）的增加而增加。 这个问题的问题是， 是否有一种（而不是最快的）方法来计算第n个像元的值，而无需进行所有中间计算，或者尤其是少于O（ n ）个运算 。

组成Pi的数字

规则30是计算领域的产物：这是一个基于对可能的简单程序的研究的系统，该程序具有新的智能结构，由计算范式提供。 但是，我在竞赛30中定义的任务具有数学上的类似物，这已经存在了多个世纪了 。

考虑数字Pi中的数字值 。 这些数字的行为类似于规则30算法中心栏中的数据生成，也就是说，有一个给定的算法可以计算它们，一旦公式化，它们对于任何任务似乎几乎都是随机的。




只是为了使模拟更接近一点，这是Pi以2为底的数字系统中的前几位：




以下是规则30中心栏中的前几位：




为了好玩，您可以将它们转换为十进制：




当然，众所周知，用于计算Pi的数字的算法比在规则30中心列中生成单元格的相对简单的规则要复杂得多。那么，我们对Pi的数字了解多少？

首先，我们知道它们不会重复。 这可以追溯到18世纪60年代，当时证明Pi是一个非理性数 ，因为唯一重复的数字是有理数。 （在1882年，还证明Pi是先验的 ，也就是说，它不能通过多项式的根表示）。

那么问题2的表达可以得出什么样的类比？ 我们是否知道在Pi的一个数字序列中，以相同的频率出现不同的数字？ 迄今为止，已经计算出超过100万亿个二进制数字 -并且所测量的数字频率非常接近（在Pi的前40万亿个二进制数字中 ，“单位与零” 之比约为0.99999998064）。 但是在计算极限时，频率会完全相同吗？ 几个世纪以来，科学家一直在问这个问题，但是到目前为止，数学还没有给出答案。

对于有理数，由它们组成的数字序列是周期性的，并且很容易确定这些数字在数字中出现的相对频率。 但是，对于所有其他“自然创建的（自然构造的）”数字的数字序列，在大多数情况下，实际上几乎不知道该数字所包含的数字频率趋向于什么。 逻辑上假设Pi的数字（以及规则30的中心列）实际上是“ 正常的 ”，这意味着不仅每个单独的数字，而且给定长度的任何数字块都以相等的最大频率相遇。 而且，正如在1930年代有关此主题的作品中所指出的那样，很有可能“构建正常数字的数字结构（模型）”。 通过合并连续整数的数字获得的樟脑常数是上述推理的一个示例（可以通过合并连续整数的函数值在任何正常数的基础上获得相同的值）：




应当指出，这里的要点是，对于由标准数学函数的组合形成的“自然构造”的数字，找不到一个发现的示例，在该示例中将找到任何规则的数字序列。 自然，最后，此规定取决于“规律性”的含义，并且在某些阶段，任务变成了一种对数位模拟的外星情报搜索 。 但是，没有证据表明不可能找到例如具有一系列具有明显规律性的数字序列的平方根的复杂组合。

那么，最后考虑Pi的问题3的类似物吗？ 与规则30（一次计算一个序列中的元素的明显方法一次只一步）不同，传统的计算Pi位数的方法包括获得与Pi最佳近似的精确数字。 随着Ramanujan在1910年发明并由1989年Chudnovsky兄弟改进的标准（“ bizarre”）系列，该系列的前几个成员给出了以下近似值：




那么，要找到第n个数字，需要进行多少次运算？ 该行中所需的项数为O（ n ）。 但是每个条件都必须以n位精度计算，这至少需要O（ n ）个单独的计算操作，这意味着一般而言，计算工作量将大于O（ n ）。

直到1990年代，人们一直认为没有计算所有先前的数字就无法计算Pi的第n位数字。 但是在1995年， 西蒙·普拉夫 （ Simon Pluff）发现，尽管有一定的可能性，实际上可以计算出第n个数字而无需计算前一个数字。 尽管人们会认为这将使您能够以少于O（ n ）个运算获得第n位数字，但是您需要以n位数字的精度执行计算这一事实意味着至少O（ n ）操作。

结果，类比和直觉

任务1：中央列是否始终保持非周期性？

在Rule 30竞赛的三项大奖中，这是解决该问题的大部分进展。 由于尚不知道规则30的中心列是否会变为周期性，因此埃里卡·詹 （ Erica Jen）在1986年指出，没有两个列可以是周期性的。 而且实际上是这样，并且人们还可以支持这样一个事实，即一列与另一列中的单个单元格组合不能是周期性的 。

一对列的证明使用规则30的功能。考虑规则的结构：




可以简单地说，对于每个三元单元格，该规则由它确定中心单元格的颜色，但是对于规则30，您也可以有效地在侧面执行该规则：考虑到右侧和上方的单元格，您还可以唯一地确定左侧单元格的颜色。 这意味着，如果采用两个相邻的列，则可以恢复左侧的整个模板 ：




但是，如果列具有周期性结构，则将立即恢复，还原的模板也应该是周期性的。 因此，例如，通过构造，至少初始条件绝对不是周期性的，因此两个列都不是周期性的。 如果各列不相邻，并且两列中的所有单元都不知道，则相同的语句为true。 但是，尚无将这种规定分配给单个列（例如中央列）的方法，因此，它不能解决规则30规定的比赛的首要任务。

那么，可以用什么来解决呢？ 如果事实证明中心列最终是周期性的，则可以进行计算。 我们知道，最初的十亿步不是周期性的，但是我们至少可以假设可能有数万亿步的过渡过程，之后过渡为周期性。

您认为这是可信的吗？ 出现瞬态现象 -从理论上讲（如在关闭图灵机的经典问题中 ），它们甚至可以具有任意长度。 在这里，我们看一些示例-在搜索过程中找到- 具有4种可能颜色的规则 （通用代码150898）。 假设我们运行了200步，并且如您所见，中心列将完全是随机的：




经过500个步骤，整个模板看起来完全是随机的：




在这里，您可以看到，在接近中心列时，发生了一些令人惊讶的事情：经过251个步骤之后，中心列似乎重生为一个固定值（或者至少固定为下一百万个步骤）：




规则30会发生同样的转变吗？ 考虑规则30中的模式，并选择左侧对角线具有周期性的模式：




显然，这里有一个边界将疾病左侧的顺序分隔到右侧。 而且，至少在最初的100,000步左右，边界似乎平均向每一步向左移动了约0.252步- 带有一些随机偏差 ：




但是，我们最终如何找出这些波动在什么时候不再显着，以至于它们迫使左侧的命令越过中心列，甚至可能使整个模板具有周期性？ 从可用数据来看，这种假设似乎不太可能，尽管我无法确切说明如何确定。

当然，这恰恰是说明存在具有非常长的“瞬态”的系统的情况。 现在考虑素数的分布并计算LogIntegral [ n ] -PrimePi [ n ]




是的，存在波动，但是在此图中，这种差异似乎始终在正区域。 例如，这就是Ramanujan讨论的内容，但最终结果并非如此 。 最初，他失败之处的边界在当时是天文数字很大的（ Skives编号 10 ^{10 10 964} ）。 而且，虽然还没有人发现显着的值n的差为负，但已知必须存在高达n = 10 ³¹⁷ （最终差将为负）。

我认为规则30的中心栏没有发生任何事情，但是到目前为止，我们还没有证据表明这是不可能的，不能争论。

应该注意的是，有可能做出这样的假设：尽管从根本上可以通过显示规则30中心栏中的规律性来证明周期性，但对于非周期性而言，则无法做任何事情。 已知有些模式的中心列是非周期性的，尽管它们非常规则。 此类示例的主要类别是嵌套模板。 例如，这是规则161中的一个非常简单的示例，其中当n = 2 ^k时，中心列具有白色单元格：




这是一个稍微复杂一点的示例（来自两个邻居的2色规则69540422） ，其中中心列为 Thue-Morse序列 -ThueMorse [ n ]：




我们可以假定Thue-Morse序列是通过顺序应用替换生成的：




事实证明，此序列中的第n个项设置为Mod [ DigitCount [ n ，2，1]，2]-此对象永远不会是周期性的。

规则30的中心栏是否可以通过替换生成？ 如果是这样，那么这个事实会让我感到惊讶（尽管当出现非常复杂的替代系统时似乎有自然的例子 ），但是只要没有任何证据就可以。

应该注意的是，规则30中的所有竞争性任务都在制定可在无限数量的像元上运行的算法时予以考虑。 , n , , ( )? , 2 ⁿ — , , . n =5:




n =5 n =11:




, , , , . , 2 ⁿ ( , , ).

, n 30 , , 2 ⁿ . , ( ):




, , n 2 ^{0.63 n} . , , . , , ? .

2: ?

10000 30:




:




:




, , 1 () 0 (), , , , , , , .

. 10 000 :




, 1? …

, :




, , . 1 , :




, ? . , . , , , , .

, , 30, .

, , k . , 2 ^k . , - , , , , 30 k ( ).

, . , , k =22, 2 ^k , , :




, , . , – , , .

— — , , , , , , 30, , , , , .

30 , , « », , , , , , . , «»: 30, , , , , , , , 30.

, . 30, , - , , , 30, , , - .

. 30 , , . , , 30 - ( ), , , , 30. 200 :




, :




, , , 0 1.

1900- . , , FractionalPart [ hn ] n h . , FractionalPart [ h ⁿ ] h ( ), — FractionalPart [(3/2) ⁿ ] — . (, , 16- , , 2- FractionalPart [16 x _{n -1} + r [ n ]], r [ n ] n .)

3: n- O( n ) ?

, 150 :




, ( ), , :




n- ? , , : Mod [ IntegerExponent [ n , 2], 2]. , n , , .

, « »? , n , Log [2, n ] . , , O(log n ) .

- 30? , n- , 30 n ² , , . , -, , , — , , , , , .

« » (, , . .), , , , , (, , 3D- . .), .

, 1980- , , , , , , , .

, 3 30 , , . ( O( n ) ; O( n ^α ) α <2, , , O(log ^β ( n )) — , , .)

3 , , n- , O( n ), 150 .

O ( n )? () , « »? , — — , , .

, . , , , n , , , n , (, «», O(log n ) .

, . , , , , Wolfram Language . « ». , , Wolfram Language , .

, 30 , 3 , , , , , , n- , O( n ) , .

, , . , , . , , , , , — , O(log n ) , n .

, P NP . , 30 ( P LOGTIME ), , , , . , , , n n , O( n ² ) , , P (« »), , , , , NP. («») , , , , 2 ⁿ .

, 2 ⁿ , , . , NP- , , , NP . 30 NP-? , , ( - , 30 NP).

30 . : 30 , , 30, «» , , , , .

, 256 110 ( , ), 110 , , , . , , , «» 110 .




30, , — , «» , . , , 30 , , , , .

, , , , , 30. , , (, ) , , . , , — , . , .

, , 3. , , , , n- ?

, 30 . , 2 ^{m 2} m × m , , . , , , O( n ² ) ( ). , O( n ) ? .

, 1 , , - O( n ) — , « ». , ( , 2 ), , , .

- , , , ? , , .

. «» , , , . 30 - . ( — — 30 Wolfram Language, « !» ).

: « - , , ». ? , , , - . . , — , . , , , — - «» 30.

, 30. , 30 - . , , , - 30 , , , , — 30, , , , .

. , 3 2 6 :




, 6 . ( 2 ). , , .

s- n . s- 3 ⁿ , «» ( b — , 2 6) Mod [ Quotient [3 ⁿ , b ^s ], b]. ? , 3 ⁿ n , : , , 3 ⁿ , log( n ). , , , . , 30, , - , .

3 n - 30 , , O( n ), , n , . , r [ n ] , r [ n ] «O-» n , , MaxLimit [ r [ n ]/ n , n →∞ ]<∞.

, ( - ), . , r [ n ] n , , , - , , r [ n ] . , - n ( - ), r [ n ] . , , , r [ n ] O( n ).

30

, ( , ).

Wolfram Language t 30 :




c [ t ].

1: ?

p i t , t > i , [ t + p ] c [ t ].

2: ?

c [ t ]/ t t →∞ 1/2.

3: n- O( n ) ?

machine[ m ] , m (, TuringMachine [...]), machine[ m ][ n ] { v , t }, v — , t — (, ). :




« m, , machine[ m ] n c [ n ] , n , ». ( m , «» ).

, , , , . 3 ( ), , 1 2, . 3 ( ), , 1 . : 1 , , 3 .

1 , , , , , 2. , 2 - 3. , , O( n ) — , , 3, , .

, , ?

1 , , , 30 - , . , 1 , . , , - , .

( , ), 2, 3 , — , , , . , 3 , , (, , ), O( n ) .

, - . , n n- . . , - , . , , n n . , . , « » . , n , . , , O( n ) .

: ? « », / ( ).

, , ( )? , , , , «» , -, ( ) , .

, , . , , , . , () .

, , , , : « ». , , , .

, — - . - n , . . — (« » . .). , , , .

— , , . , ( FindEquationalProof ). , () .

, , , — , . — , .

, . Wolfram|Alpha (, ) , . , .

, , - , , , , .

? , «» , . Wolfram Language , . Wolfram Language, .

« »? , , - . . - , , «» , , - ( ), . , , «» — , .

?

, ? . . , . - , . . - , , .

, , «» — , — , « ». , 2,3 2007 .

— , , 30, , . . - ( , , ). , , ( ) , , .

n — 30 n , n . Wolfram Language . , 0,4 100 000 :




, 30 Xor [ p , Or [ q , r ]], . , CellularAutomaton :




. . , , 30, , 30 , , , : .

. , , «» . 30 — . , , , .

— , , . , , 30, .

, , 30, . 45° , 30, , . ; . ?

? ? - ? , , , , , .

? 30, . , , , , , . , - , , , , , , - .

– , «» . ( , - ). , , , , « » :




, , , . ? , « » ?

, (, ), , - 30?

« 30». , «» ? 30 , ? «» ?

, , 30, , , , 30, . 256 ( ) , , :




, . , . , , . , , , « 30», .

« 30». 30 ( 1), , — , .

2, 30, , .

3 . n- O( n ^γ ) γ <2 ( - )? , n- , O(log( n )) ? O(log( n )) ? ? . ?

, 30. 30, (, , 110) , 30.

, NP-, 30 , , NP-? , . , , , « », 30?

?

2007 2,3 , — , , , . , . 30? 我不知道 40 , - ( , !). , , (, ) .

, - ( ), , , , , , , . ( ), , , .

, « » ( , ), . , . , (« » . .). . , - « », , , …

, . , , . , , . , .

, 30 40 , - .

Wolfram Language?
« Wolfram » ( ).