为什么mov指令是图灵完备的

以下全文转载自：mov is Turing-complete

摘要

众所周知，x86指令集是“巴洛克式”的——过度复杂且冗余。我们通过证明，即使将其简化为仅剩一条指令，它仍然是图灵完备的，从而揭示了其臃肿程度。

我们选择的指令是mov，它可以执行加载和存储操作。我们没有使用任何不寻常的寻址模式、自修改代码或运行时代码生成。仅使用这条指令（以及程序末尾的一个无条件分支以实现非终止的可能性），我们演示了如何模拟任意的图灵机。

引言

x86上的mov指令有相当多的寻址模式。该指令可用于执行内存加载或存储，以及将立即数加载到寄存器中。尽管功能强大，但它本身不执行任何形式的条件分支或比较，因此它是否是图灵完备的并不明显。

当然，在实际的x86处理器上，mov指令可用于在指令指针之后将任意代码写入内存，然后处理器将执行该代码，这在某种意义上使其“微不足道地”图灵完备。我们认为这是作弊：我们对图灵机的模拟不使用自修改代码或运行时代码生成，也不使用晦涩的寻址模式。事实上，所使用的寻址模式在大多数 RISC 架构上都可以作为指令使用，尽管 RISC 机器通常不将它们都称为mov。

执行有限序列的mov指令将在有限时间内完成。为了具有图灵完备性，我们必须允许非终止。因此，我们的图灵机模拟器由一系列mov指令组成，最后是一个返回到开头的无条件分支。

机器模型

我们使用一个简单的抽象机器模型。我们的机器有一个由字组成的随机存取存储器。每个字可以容纳一个内存地址或一个偏移量，其中偏移量为 0 或 1（它们不是有效的内存地址）。我们有 n 个寄存器 R1, …, Rn，每个寄存器也容纳一个字。我们暂时假设有足够的寄存器，但稍后我们将展示如何在不损失表达能力的情况下减少其数量。

我们有以下指令（如果你喜欢 RISC）或寻址模式（如果你喜欢 CISC）。我们使用 Intel x86 语法，其中 mov 指令的目标在前，源在后，方括号表示内存操作数。

指令	x86 语法
加载立即数	mov Rdest, c
加载变址	mov Rdest, [Rsrc + Roffset]
存储变址	mov [Rdest + Roffset], Rsrc

在 x86 上，这些都是同一mov指令的所有寻址模式。然而，即使在 RISC 机器上，这些仍然是单个指令。例如，在 PowerPC 上，这三个操作是 li、ldx 和 stx。

看起来我们似乎在通过允许地址中的算术运算来作弊。然而，我们的“算术”是一种非常受限的形式：变址指令只能在 Rsrc（或用于存储的 Rdest）是偶数内存地址时使用。由于偏移量始终为 0 或 1，因此我们的“算术”可以实现为按位或，甚至是位串连接。

通过这三个指令，我们有一些简单的派生指令。我们可以通过使用临时寄存器，以常数偏移量使用加载变址和存储变址指令。例如，加载指令 mov Rdest, [Rsrc] 可以实现如下，使用寄存器 X 作为临时寄存器：

mov X, 0
mov Rdest, [Rsrc]

碰巧的是，这些常数偏移指令在 x86 上可以作为mov的其他寻址模式使用。

内存逻辑上分为单元，它们是成对的相邻字，从偶数内存地址开始。我们的加载变址和存储变址操作可以看作是对单元的加载和存储，其中单元的地址由一个寄存器给出，而要访问的两个字中的哪一个由另一个寄存器指定。

仅使用这些指令，我们就可以模拟任意的图灵机。

表示图灵机

图灵机 M 是一个元组：

M = (Q, q₀, Σ, σ₀, δ)

其组成部分是：

• 一个有限的状态集 Q，带有一个可区分的起始状态 q₀ ∈ Q。
• 一个有限的符号集 Σ，带有一个可区分的空白符号 σ₀ ∈ Σ。
• 一个转换表 δ，它是一个部分函数 Q × Σ → Σ × {L, R} × Q。

图灵机有一个带子，它由一个无限的、每个位置包含一个符号的序列组成。机器有一个当前状态（最初是 q₀）和一个当前位置（最初是带子最左边的位置，带子向右无限延伸）。所有带子位置最初都包含 σ₀。

机器重复查询转换表 δ。如果对于当前状态和当前位置的符号，δ 未定义，则机器停止。如果定义为 (σ’, d’, q’)，则当前状态设置为 q’，当前位置的符号设置为 σ’，当前位置向左移动一位（如果 d’ = L）或向右移动一位（如果 d’ = R），然后机器继续。

我们可以用内存单元表示图灵机。符号由地址为 S₁, …, S|Σ| 的单元表示，其中 Σ 中的每个符号对应于某个 Si，空白符号 σ₀ 对应于 S₁。单元 Si 的内容未指定。

我们用列表表示状态和转换表。我们的单元就像 Lisp 的 cons 单元，所以我们可以像 Lisp 那样表示列表：一个非空列表由一个单元表示，其第一个字包含列表的第一个元素，其第二个字指向列表的其余部分，以相同的方式表示。空列表由地址为 N 的单元表示，其内容未指定。

对于任何状态 q，我们说它的出向转换集是元组 (σ, σ’, d’, q’) 的集合，使得 δ(q, σ) = (σ’, d’, q’)。每个状态都表示为其出向转换的列表，每个出向转换都表示为四个元素的列表：触发符号 σ 和新符号 σ’ 表示为相应单元 Si 和 Sj 的地址，方向 d’ 表示为 0（如果 d’ = L）或 1（如果 d’ = R），新状态 q’ 表示为其出向转换列表的地址。

在图1的图灵机中，有三个状态 q₀、q₁ 和 q₂。状态 q₀ 和 q₁ 各有两个出向转换，q₂ 没有。单元 Q₀ 包含一个表示 q₀ 的出向转换的列表。这两个转换都指向状态 Q₁，因此表示每个转换的列表的第四个单元包含 Q₁ 的地址（为了避免混乱，图中没有用箭头显示）。状态 q₃ 没有出向转换，因此用 N（空列表）表示。

内存的所有其他单元构成了图灵机的带子。为了模拟图灵机，我们假设带子是无限的（尽管在真实机器上它会受到地址空间的限制），因此单元地址由序列 T₁, T₂, … 给出。这些单元被初始化，使得地址为 Tn 的字的内容是地址 S₁，地址为 Tn + 1 的字的内容是地址 Tn+1。

通过这种方式，我们可以将 T₁ 视为一个无限列表的开始，其中无限列表的每个元素最初都包含 S₁。

在讨论图灵完备性时，我们通常只关心计算，而忽略输入和输出。我们假设输入是在我们的程序开始之前放置在单元 T₁ 到 Tn 的第一个字中的一系列符号，并且程序的输出是通过事后检查带子来确定的。

我们的图灵机版本没有特定的接受或拒绝状态，但这并不损失功能，因为它们可以通过在停机前向带子上写入“接受”或“拒绝”符号来模拟。

比较和条件

计算的一个基本方面是分支：根据运行时值选择下一步要执行的操作。因此，我们的机器完全缺乏条件分支、计算跳转或任何闻起来像比较指令的东西，这似乎是一个障碍。然而，事实证明，我们仅使用加载和存储指令就可以进行比较。如果将一个值存储到地址 A，并将一个不同的值存储到地址 B，那么事后检查地址 A 的内容将告诉您 A 和 B 是否相等。假设寄存器 Ri 和 Rj 都指向符号（也就是说，它们的值取自 S₁, …, S|Σ|）。我们可以如下比较它们：

mov [Ri], 0
mov [Rj], 1
mov Rk, [Ri]

这会破坏地址 Ri 和 Rj 处的值，但这没关系，因为符号单元的内容未指定。效果是，如果 Ri = Rj，则 Rk 获得值 1，否则为 0。

我们还可以使用以下代码将任意地址与 N 进行比较。在此示例中，Ri 是要比较的地址，我们将其值保存在暂存寄存器 X 中以避免破坏它。我们假设寄存器 N 包含地址 N。

mov X, [Ri]
mov [N], 0
mov [Ri], 1
mov Rj, [N]
mov [Ri], X

在此序列之后，如果 Ri 等于 N，则 Rj 为 1，否则为 0。

这允许我们进行比较，结果为零或一。然后我们可以使用该结果在两个不同的值之间进行选择。假设我们有两个寄存器 Ri 和 Rj，以及一个包含 0 或 1 的寄存器 Rk。我们可以使用 Rk 通过使用 Rk 索引一个双元素查找表来在 Ri 和 Rj 之间进行选择。地址 N 在寄存器 N 中很方便，并且内容未指定，所以我们使用该单元来保存我们的查找表：

mov [N], Ri
mov [N+1], Rj
mov Rk, [N + Rk]

这个序列导致 Rk 获得 Ri 或 Rj 的值，具体取决于 Rk。

有了这些操作，我们就能够模拟任意的图灵机，如下一节所述。

模拟图灵机

我们使用一个寄存器 T 来保存要测试的当前转换，一个寄存器 S 来保存包含当前符号的单元。寄存器 L 保存表示当前位置左侧带子部分的列表，寄存器 R 保存表示右侧部分的列表。

在程序启动时，T 保存地址 Q₀，S 保存地址 T₁。寄存器 L 保存地址 N，R 保存地址 T₂。寄存器 L 以相反的顺序保存当前位置左侧的带子部分（最初是空列表 N）。顺序是相反的，以便最近的位置始终是列表的第一个元素，因此无需处理整个列表即可向左移动。

寄存器 R 保存当前位置右侧的带子部分，最初是 T₂，即带子上除第一个位置之外的所有位置的列表。L 和 R 中保存的两个列表用作堆栈，向右移动意味着将当前单元推入 L 并从 R 中弹出一个新单元。

由于我们经常使用 N，我们假设寄存器 N 始终包含地址 N。

首先，我们通过比较 S 和当前转换 T 上的符号来检查当前转换是否应该触发。

mov X, [T]       ;; 获取转换
mov X, [X]       ;; 获取触发符号
mov Y, [S]       ;; 获取当前符号
mov [Y], 0       ;; 比较符号
mov [X], 1
mov M, [Y]

在此序列之后，如果转换匹配，则寄存器 M 为 1，否则为 0。接下来，我们更新 S：如果转换匹配，我们使用转换的新符号，否则我们保持不变。

mov X, [T]       ;; 获取转换
mov X, [X+1]     ;; 跳过触发符号
mov X, [X]       ;; 加载新符号
mov Y, [S]       ;; 加载旧符号
mov [N], Y       ;; 在 X 和 Y 之间选择
mov [N+1], X
mov Z, [N + M]
mov [S], Z       ;; 写入新符号

这会在转换匹配时更新 S。接下来，如果转换匹配，我们需要在适当的方向上推进带子。我们分两个阶段进行。首先，我们将单元 S 推入其中一个带子堆栈，然后我们从另一个带子堆栈中弹出一个新的 S。如果转换不匹配，我们从同一个带子堆栈中推入和弹出 S，这没有效果。为了确定转换是向左还是向右移动，我们使用以下序列：

mov D, [T]       ;; 获取转换
mov D, [D+1]     ;; 跳过触发符号
mov D, [D+1]     ;; 跳过新符号
mov D, [D]       ;; 加载方向

在此之后，寄存器 D 保存磁带移动的方向：0 表示左，1 表示右。如果我们要向左移动，则单元 S 必须添加到磁带堆栈 R，反之亦然。将单元添加到磁带堆栈是通过首先将磁带堆栈的当前顶部写入 [S+1]，然后修改磁带堆栈寄存器以指向 S 来完成的。

mov [N], R       ;; 为 [S+1] 选择新值
mov [N+1], L
mov X, [N + D]
mov [S+1], X
mov [N], L       ;; 为 L 选择新值
mov [N+1], S
mov L, [N + D]
mov [N], S       ;; 为 R 选择新值
mov [N+1], R
mov R, [N + D]

我们必须确保如果转换不匹配（即，如果 M = 0），则不会发生磁带移动。为此，如果转换不匹配，我们翻转 D 的值，以便我们弹出刚刚推入的单元。

mov [N], 1       ;; 设置 X = not D
mov [N+1], 0
mov X, [N + D]
mov [N], X       ;; 在 D 和 X 之间选择
mov [N+1], D
mov D, [N + M]

接下来，我们从 D 指示的方向弹出一个单元：如果 D = 0，我们从 L 中弹出一个单元，如果 D = 1，我们从 R 中弹出一个单元。

mov [N], L       ;; 为 S 选择新值
mov [N+1], R
mov S, [N + D]
mov X, [S + 1]   ;; 获取 L 或 R 的新起点
mov [N], X       ;; 为 L 选择新值
mov [N+1], R
mov L, [N + D]
mov [N], R       ;; 为 R 选择新值
mov [N+1], X
mov R, [N + D]

因此，如果当前转换匹配，此代码会向磁带写入一个符号并向适当的方向前进。如果转换不匹配，此代码无效。

剩下的就是找到要考虑的下一个转换。如果当前转换匹配，那么我们应该查看下一个状态的转换列表。否则，我们继续到当前状态的下一个转换。

mov X, [T + 1]   ;; 获取此状态的下一个转换
mov Y, [T]       ;; 获取当前转换
mov Y, [Y + 1]   ;; 跳过触发符号
mov Y, [Y + 1]   ;; 跳过新符号
mov Y, [Y + 1]   ;; 跳过方向
mov Y, [Y]       ;; 加载下一个状态的转换列表
mov [N], X       ;; 选择下一个转换
mov [N + 1], Y
mov T, [N + M]

这会找到我们的图灵机应该考虑的下一个转换。如果 T 的值为 N，则表示没有更多要考虑的转换：要么我们到达了一个状态的转换列表的末尾而没有匹配，要么我们刚刚转换到一个没有出向转换的状态。无论哪种方式，机器都应该在这种情况下停止。首先，我们通过将寄存器 H 设置为 1（如果 T 为 N）来检查是否是这种情况：

mov X, [T]
mov [N], 0
mov [T], 1
mov H, [N]
mov [T], X如果 H 为 1，我们必须停止机器。我们通过从无效内存地址 0 读取来做到这一点：mov [N], 0       ;; 在 0 和 N 之间选择
mov [N+1], N
mov X, [N + H]
mov X, [X]       ;; 从 0 或 N 加载

如果此内存访问没有停止程序，那么我们已经成功找到了另一个候选转换并将其指针放在 T 中，并且我们在 S 中有当前符号单元。因此，我们处于一个合适的状态来再次运行程序，所以我们使用我们的单个无条件跳转来循环回到开始：

jmp start

这模拟了一个任意的图灵机，只使用mov（和一个jmp来循环程序）。

寄存器使用

在构建我们的图灵机模拟器时，我们自由地使用了许多临时寄存器。x86架构从未被指责寄存器过多，我们似乎已经超出了8个通用寄存器的预算。

可以更仔细地分配寄存器以使其在限制范围内，但我们采用不同的方法：我们证明任何可以使用我们受限指令集实现的程序都可以转换为最多使用四个寄存器的等效程序。

假设原始程序使用 n 个寄存器 R₁, …, Rn。我们在翻译后的程序中用 n 个预分配的暂存空间单元来表示它们。每个暂存空间单元的第二个字指向下一个单元，最后一个单元的第二个字指向第一个单元，将它们布置成一个循环链表（见图2）。

我们的四个寄存器是 S（在启动时指向暂存空间的第一个单元）以及另外三个寄存器 A、B 和 C。我们可以如下将 S 前进到下一个单元：

mov A, 1
mov S, [S + A]

如果 mov S, [S + 1] 指令直接可用，那么可以在不使用 A 的情况下完成。这允许我们将任何 Ri 值加载到 A、B 或 C 中：我们将 1 加载到目标寄存器中，然后将 S 前进到正确的位置，然后执行 mov A, [S]。

在翻译过程中，我们总是知道 S 指向哪个暂存单元，因此移动 S 到右侧暂存寄存器所需的 mov S, [S + A] 指令的数量很容易确定。例如，要将 R₂、R₄ 和 R₁ 分别加载到寄存器 A、B 和 C 中，我们生成以下代码（假设有四个暂存单元）：

mov A, 1
mov S, [S + A]
mov A, [S]

mov B, 1
mov S, [S + B]
mov S, [S + B]
mov B, [S]

mov C, 1
mov S, [S + C]   ;; 回绕到 R1
mov C, [S]

我们的操作最多有三个源操作数（用于变址存储），因此对于任何操作，我们都可以使用类似上面的序列将操作数加载到寄存器 A、B 和 C 中。我们生成代码以使用这些寄存器执行操作，然后生成代码将结果存储回暂存空间（如果有结果）。我们假设结果在寄存器 A 中，但对于任何其他结果寄存器，修改以下内容是微不足道的。

我们使用 B 作为暂存寄存器，并像以前一样循环 S：

mov B, 1
mov S, [S + A]

mov S, [S + B] 指令根据需要重复多次以到达所需的暂存单元，然后使用 mov [S], A 存储结果。

这种转换为任何可以在我们受限指令集中实现的程序都有效，包括上一节的图灵机模拟器。因此，仅使用 mov 指令和四个寄存器就可以模拟任意的图灵机。

因此，虽然众所周知x86的指令太多，但我们现在可以贡献一个新颖的结果，即它的寄存器也太多了。

讨论

在不可能的地方发现图灵完备性长期以来一直是无聊的计算机科学家的消遣。被证明是图灵完备的奇异机器的数量太多，无法在此处描述，但有一些与本文所描述的相似。

Farhad Mavaddat 和 Behrooz Parhami [2] 证明了一台计算机仅用一条指令就可以完成任务。他们的机器使用一条指令，该指令需要两个内存地址和一个跳转目标，其操作是“相减并在小于或等于时分支”，将算术、内存加载、内存存储和条件分支组合成一条指令。

Douglas W. Jones [1] 描述了一台仅使用 MOVE 的单指令机器，其中通过具有内存映射的算术和逻辑单元来获得图灵完备性（因此可以通过将数据移动到预定义的内存位置并随后收集结果来执行其他操作）。基于此原理的一些机器已经建成，通常被称为“移动机”或“传输触发架构”。

Raúl Rojas [3] 表明，使用自修改代码，具有加载、存储、增量、置零和无条件分支的指令集是图灵完备的。在同一篇论文中，他还表明，没有自修改代码或代码生成的机器，通过增量和双重间接加载和存储是图灵完备的。双重间接内存操作使用一个寄存器作为保存要访问地址的内存单元的地址（在伪x86表示法中，加载看起来像 mov A, [[A]]）。

从x86架构的未来迭代中删除除 mov 指令之外的所有指令将具有许多优势：指令格式将大大简化，昂贵的解码单元将变得便宜得多，并且当前用于复杂功能单元的硅可以重新用作更多的缓存。只要有人实现编译器。

参考文献

[1] D. W. Jones. The Ultimate RISC. ACM SIGARCH Computer Architecture News, 16(3):48-55, 1988.

[2] F. Mavaddat and B. Parhami. URISC: The Ultimate Reduced Instruction Set Computer. International Journal of Electrical Engineering Education, 25(4):327-334, 1988.

[3] R. Rojas. Conditional Branching is not Necessary for Universal Computation in von Neumann Computers. Journal of Universal Computer Science, 2(11):756-768, 1996.

以上全文转载自：mov is Turing-complete