24

我无法理解维基百科文章或这里的答案所说的内容。有人可以简单地解释第 110 条规则吗？它如何保证图灵完备？

4

4 回答 4

8

我尝试用简洁的外行术语解释：

  • 规则 110 是一个基本的元胞自动机：将 1 和 0 的有限模式转换为 1 和 0 的另一种模式的规则。
  • 当规则 110 迭代地应用于某些输入位序列时，模式会根据输入位中的子序列出现。给定足够的迭代次数，可能会发生以下情况：
    • 原始子序列出现在与原始输入相同的位置。
    • 原始子序列被保留，但“移动”到位域中的不同位置。
    • 朝向彼此移动的两个子序列相互作用并“穿过”彼此。
    • 两个子序列结合起来创建一个新的子序列。
  • 不同的子序列可以被赋予符号含义，如“1”、“0”、“时钟脉冲”或“生产规则”，它们对应于循环标签系统的元素。
  • 通过在精心构造的输入位域上对规则 110 进行多次迭代，子序列的交互模拟了循环标签系统的行为。
  • 循环标签系统可用于模拟通用图灵机。因此，循环标签系统是图灵完备的。
  • 由于规则 110 可以模拟循环标签系统，因此它也是图灵完备的。
于 2013-02-18T23:27:02.370 回答
7

我将尝试详细说明：我不认为您正在寻找文章中已经相当复杂的证明的更多细节，尽管它显然省略了许多细节。

引用您引用的文章：“在基本元胞自动机中，0 和 1 的一维模式根据一组简单的规则演变。模式中的点是 0 还是 1 取决于新一代它的当前值，以及它的两个邻居的值。规则 110 自动机具有以下规则集……”（参见下面的维基百科表格）

起点，您可以将其视为数据，但可以将其视为代码的表示（将代码表示为数据对于任何图灵完备性的证明都是必要的；这可以追溯到图灵的原始结果），是一系列0 和 1 通常但不一定在两侧被仅包含 0 的单元包围。规则 110 显示了该序列如何演变。例如，如果一行中有 3 个 1 的模式，则中间的 1 将在下一行中“死亡”（变成 0）。它的两个邻居会发生什么取决于模式如何超越它们。你看到的三角图是自动机从原始状态演化的图形表示，编码 1 为黑色，编码 0 为白色，代表从上到下的演化。

图灵完备性证明的两个不同寻常的特点是，首先，这样一个非常简单的规则看起来不太可能完成你最喜欢的编程语言可以做的所有事情，其次，这使得第一个事实变得不那么令人惊讶的是，证明需要一个无限长的重复背景来发挥它的魔力。不过，我看不出有什么根本不诚实的地方；只不过是假设一个潜在的无限或半无限的空白磁带，就像图灵最初所做的那样。

要正确理解证明，您需要掌握数据（以及后来的代码）是如何在起始模式中编码的，而且看起来熟悉循环标签系统也会有很大帮助。我不是解释这些的人。

尽管使用 2-D 元胞自动机（例如康威的“生命游戏” ）似乎更难理解这种情况，但我发现玩那个游戏很有启发性，研究“滑翔机”、“滑翔机枪”和“河豚火车”和其他有趣的建筑。（河豚列车制造滑翔机枪，滑翔机枪发射滑翔机）。这些也可以用来建立这个自动机的图灵完备性。

您可能还会发现讨论页内容丰富（您不是唯一一个没有抓住重点，请参阅开头的条目“这些图片对我没有任何意义......”）。

于 2013-02-18T18:32:05.240 回答
6

1970 年，约翰康威发明了生命游戏。

从那以后，我认为几乎每个程序员都尝试编写它的实现——我当然很久以前就这样做了，而且很有趣。

这个游戏实际上是元胞自动机，它在无限二维平面上的几代细胞之间设定简单的规则。例如，如果在当前一代中，存活的邻居少于 2 个（位值1），那么它应该在下一代孤独中死亡。如果它有 3 个以上的邻居活着，它应该死于过度拥挤。如果空（位值0，或死）单元格恰好有 3 个邻居，它将导致它诞生（成为1）。

从那以后，人们发现生命游戏异常复杂——它可以产生许多非常复杂的模式，并且不断进化。此外，它被证明是图灵完备的，也就是说，您可以使用起始单元组合作为程序来编码任意复杂的算法，并作为结果进行最终组合。然而，花了几年的时间才找到如何真正生成复杂的形式，比如滑翔机或枪。

现在回到规则 110 是什么。简单地说，规则 110 是生命游戏的一维变体。

110 只是二进制字符串01101110的十进制数字表示，它是当前一代细胞（位）如何转换为下一个细胞的规则系统的简写形式，类似于生命游戏的细胞死于孤独或过度拥挤的规则系统出生时正好有三个邻居。

就像生命游戏一样，已经证明规则 110 是图灵完备的。您可以使用起始单元（位）组合作为程序编码任意复杂的算法，并使用最终位组合作为结果。

于 2013-02-19T07:24:01.767 回答
3

python中的一个实现：

（请注意：实际的 python 程序员会为此杀死你）

import time

seed = raw_input("Feed me a string! (At least 3 characters long please)\n>")

lastline = '>'
iterator = 0

while (iterator<len(seed)):
    temp = (ord(seed[iterator]))%2
    if (temp == 1):
        lastline += '#'
    else:
        lastline += ' '
    iterator += 1

stop = 0
while (stop != 1): #Keep printing as long as CTRL-C isn't pressed
    #dummy = raw_input(lastline)
    print lastline
    iterator = 0
    nextline = '>'


    while (iterator<len(seed)):    #Convert entire string

        if (len(seed) < 3): # if wrong
            print "You had ONE JOB!"
            stop = 1

        elif (iterator == 0): # if at start
            if (lastline[1] == ' '):
                nextline += ' '
            else:
                nextline += '#'

        elif (iterator+1 == len(seed)): # if at end
            if (lastline[iterator+1] == ' '):
                nextline += ' '
            else:
                nextline += '#'

        else: #if in middle
            if (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #111
                nextline += ' '
            elif (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #110
                nextline += '#'
            elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #101
                nextline += '#'
            elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == ' '): #100
                nextline += ' '
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #011
                nextline += '#'
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #010
                nextline += '#'
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #001
                nextline += '#'
            else: # (lastline[iterator-1] == ' ' and lastline[iterator] == ' ' and lastline[iterator+1] == ' '): #000
                nextline += ' '

        iterator += 1

    lastline = nextline
    time.sleep(0.02)
于 2013-06-28T20:44:29.947 回答