一些通用计算模型

2021-01-30 约 1273 字预计阅读 3 分钟次阅读

在可计算性理论中，如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)可以用来模拟任何图灵机，则称该系统是「图灵完备」的或能做「通用计算」的。 – wikipedia

通用计算(图灵完备)是计算能力的体现，意味着解决所有可计算问题的能力。在理论上却不难实现，可能的一个原因是计算能力是传递关系：如果 A 能模拟图灵机，而 B 能模拟 A，则 B 能模拟图灵机。

标签系统

图灵机由纸带，读写头，控制规则，状态表四个部分组成。标签系统(tag system)是一个类似图灵机的计算模型，它是一套字符串的转换规则：反复在一个字符串的末尾添加部分字符并在开头处删除部分字符(控制规则)。于是，标签系统会朝着字符串的末尾“移动”(读写头)。

标签系统可表示为三元组 (m, A, P)，其中：

m 是删除数
A 是有限的符号字母表(状态表)，其中有特殊的停机符号
P 是添加字符的规则集合

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Tag system
    m: 2
    A: {1,2,3,H}
    P:
        1  -->  3321H
        2  -->  331
        3  -->  33

Computation
    Initial word: 211
                    1331
                      313321H
                        3321H33
                          21H3333
                            H3333331(halt).

当初始全为 3 的字符串时，程序永不停机，这意味着标签系统是图灵完备的。

循环标签系统

循环标签系统(cyclic tag system)是一类有额外限制的标签系统：

循环标签系统的字符只有 0 和 1
规则只在当前字符串以 1 开始时才生效
删除数是 1

这些约束对于支持通用计算来说过于苛刻了，作为补偿，允许循环尝试生成规则：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


Cyclic tag system
    m: 1
    A: {0, 1}
    P: 1  -->  011, 10, 101

Computation
 Initial word: 1
       P             word
    --------       --------
      011              1
      10                011
      101                11
      011                 1101
      10                   101011
      101                   0101110
      011                    101110
      ...                      ...

字符串为空时，程序才会停机。而这个程序永不停机，因为 word 中一直有 1，这意味着循环标签系统也是图灵完备的。它的规则非常简单，不过它的行为却很复杂：接下来发生什么并不明显，字符串何时扩张，何时收缩？只能运行程序，然后观察它的行为。

Rule 110

一维元胞自动机建立在一行无限长的格子序列上，它的规则是：

每个格子有黑白两种状态
每个格子下一刻的状态由此刻的自身状态和左右邻居的状态共同决定

依照上述规则，有 256 种可能情况，若规定黑色为 1，白色为 0：

上图对应 01101110(二进制)，这就是 Rule 110(十进制)，它也是图灵完备的，因为它被证明可以模拟循环标签系统。下面做简单解释：

在元胞自动机中，有的结构会随时间做周期性地“移动”，它们被称为“滑翔机”或“飞船”：

上图是 Rule 110 中已发现的所有滑翔机，以及一个滑翔机枪：每周期发射一次 A 和 B 滑翔机。这里展示了用通过特定排列的滑翔机来模拟 P: 1 --> 11, 10 的循环标签系统，这不是完成通用计算的高效方式，但对简单的细胞自动机来说这仍是一项令人印象深刻的技术成果。比起二进制的字符串，图像可能更容易让人观察计算行为的普遍规律。

如果我们建立了宇宙的完整模型，是否意味着我们没有自由意志了呢？“Computational irreducibility ” 意味着，就算你知道了一切规则，你可能也无法提前预测这些规则将会做什么 — 唯一的办法是运行这些规则看看它们到底会做出什么来。

推荐阅读

目录

一些通用计算模型

标签系统

循环标签系统

Rule 110