我将详细说明:我不认为你正在寻找更详细的证据,这篇文章在本文中已经相当复杂,尽管它明显省略了许多细节.
引用文章引用:"在一个基本元胞自动机中,0和1的一维模式根据一组简单的规则发展.模式中的一个点是0还是1取决于新一代它的当前值以及它的两个邻居的值.规则110自动机具有以下规则集......"(参见下面的维基百科表)
起点,您可以将其视为数据,但可以作为代码的表示(代表作为数据的代码,对于图灵完整性的任何证明都是必要的;这可以追溯到图灵的原始结果),是一个序列0和1,通常但不一定,两侧都被仅包含0的单元包围.规则110显示了该序列如何演变.例如,如果一行中存在3 1的模式,则中间1将在下一行中"死"(变成0).它的两个邻居发生了什么取决于模式如何超越它们.您看到的三角图是自动机从原始状态演变的图形表示,编码1为黑色,0为白色,表示从上到下的演化.初始状态的长度通常非常短,以显示非常复杂的模式可以从简单的初始状态演变而来.
图灵完整性证明的两个不寻常的特征是,首先,这样一个非常简单的规则看起来不太可能完成你喜欢的编程语言可以做的所有事情,其次,这使得第一个事实相当不那么神奇,就是证明需要一个无限长的重复背景才能发挥其魔力.虽然我看不出任何从根本上说不诚实的事情; 正如图灵最初所做的那样,不如假设一个潜在的无限或半无限的空白磁带.
要正确理解证明,您需要掌握数据(以及后来的代码)如何在起始模式中进行编码,并且看起来好像熟悉循环标记系统会有很大帮助.我不是解释这些的人.
尽管用一个二维元胞自动机来理解这种情况似乎比较困难,比如康威的"生命游戏",我觉得玩这个游戏很有意义,研究"滑翔机","滑翔机枪"和"河豚火车"和其他有趣的结构.(河豚火车构造滑翔机枪,滑翔机枪发射滑翔机).这些也可用于为此自动机建立图灵完备性.
您也可以找到提供信息的谈话页面(您并不是唯一没有理解这一点,请参阅条目开头"这些图片对我没有任何意义......").
小智 7
我尝试简明扼要,外行的条款解释:
1970 年，John Conway 发明了生命游戏。
从那以后，我想几乎每个程序员都试图编写它的实现——我很久以前确实做过，而且很有趣。
这个游戏实际上是元胞自动机，它在无限二维平面中的几代细胞之间设置简单的规则。例如，如果在当前一代细胞中存活的邻居少于 2 个（位值1），那么它应该在下一代孤独中死亡。如果它有 3 个以上的邻居活着，它应该死于过度拥挤。如果空（位值0，或死）单元格正好有 3 个邻居，它将导致它诞生（成为1）。
从那时起，人们发现 Game of Life 出奇地复杂——它可以生成许多非常复杂的模式，并不断发展。此外，它被证明是图灵完备的，也就是说，您可以使用起始单元组合作为程序来编码任意复杂的算法，最终组合作为结果。然而，花了几年时间才找到如何真正生成复杂的形式，比如滑翔机或枪。
现在回到规则 110。简单地说，规则110是生命游戏的一维变体。
110 只是二进制串01101110的十进制数表示，它是当前一代细胞（位）如何被转换成下一个的规则系统的简写形式，类似于生命游戏的细胞因孤独或过度拥挤而死亡的规则系统出生于正好有三个邻居。
就像生命游戏一样，已经证明规则 110 是图灵完备的。您可以使用起始单元（位）组合作为您的程序，并使用最终位组合作为结果来编码任意复杂的算法。