条件分支是图灵完备性的要求吗？

Question

我一直在搜索网络，但是发现有些答案相互矛盾。一些来源声称，只有具备条件和无条件分支（这可能有点冗余）的语言/机器/等才是图灵完备的，有些人则说仅需要无条件分支，还有些人则说仅需要条件分支。

关于德国的Z3和ENIAC，维基百科上写道：

“德国的Z3（1941年5月展示工作）由康拉德·祖斯设计。它是第一台通用数字计算机，但是它是电气机械式的，而不是电子式的，因为它使用继电器进行所有功能。它使用二进制数学进行逻辑计算。它可以通过打孔纸带进行编程，但缺少条件分支。虽然它不是为了图灵完备性而设计的，但在1998年发现它意外地具有图灵完备性（但要利用这种图灵完备性，需要复杂的巧妙的技巧）。”

那么到底是哪些复杂的巧妙的技巧呢？

1998年R. Rojas的一篇论文摘要也指出（请注意，我没有阅读这篇论文，这只是IEEE上的一小部分内容）。

在计算机历史的角度来看，Konrad Zuse在1938年至1941年间建造的计算机Z3只能执行编码在打孔纸带上的固定浮点运算序列（加减乘除和平方根）。一个有趣的问题是，这些操作是否足以进行通用计算。本文表明，事实上，仅包含这些算术指令的单个程序循环可以模拟任何具有给定有限尺寸磁带的图灵机。这是通过纯粹的算术手段模拟条件分支和间接寻址完成的。因此，Zuse的Z3至少在原则上与今天具有有限寻址空间的计算机一样通用。 简而言之，SOers，图灵完备性确切需要哪种类型的分支？假设内存无限大，仅使用goto或jmp分支结构（无if或jnz结构）的语言是否可以被认为是图灵完备的？

- David Titarenco

Answer 1

原始的Rojas论文可以在这里找到。基本思想是Z3仅支持无条件单循环（通过将指令带的两端粘合在一起）。您可以通过将所有代码部分依次放置在循环中，并使用变量z确定要执行的部分来构建其条件执行。在第j节开始时，您设置

 if (z==j) then t=0 else t=1

然后在这一部分中，将每个赋值操作a = b op c改为如下形式

 a = a*t + (b op c)*(1-t)

（即每个作业都是无操作，除非在活动部分）。现在，这仍然包括条件赋值：如何比较z==j？他建议使用z的二进制表示（z1..zm）以及j的否定二进制表示（c1..cm），然后计算

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm))

这个产品只有在c和z的每一位都不同的情况下才会为1，这只会发生在z==j的情况下。对于z的分配（本质上是一个间接跳转），也必须分配给z1..zm。

Rojas还写过von Neumann计算机中条件分支不是必需的。他提出了一种具有自修改代码和相对寻址的机器，以便您可以从内存中读取Turing指令，并修改程序以相应地跳转。作为替代方案，他提出了上述方法（针对Z3），其中只使用LOAD（A），STORE（A），INC和DEC。

- Martin v. Löwis

---

我喜欢你的回答，但是如果机器无法进行算术运算会发生什么？或者如果机器有点像ZISC呢？谢谢！ - David Titarenco

定义“算术”。通常的定义至少包括加法。Rojas机器（第二台）没有加法，只有INC（他还讨论了DEC不需要）。无论如何，我无法证明没有条件指令的ZISC是否是图灵完备的；我个人认为它不是。 - Martin v. Löwis

Answer 2

如果您只有算术表达式，可以使用一些算术运算的属性。例如，如果A是根据某些条件（先前计算）为0或1，则A*B+(1-A)*C计算表达式if A then B else C。

- dmitry_vk

---

你提出了一个有趣的解决方案。如果机器是ZISC或图灵沥青坑（没有算术运算），会怎样呢？ - David Titarenco

Answer 3

如果你能计算出你的goto或jmp的地址，那么你就可以模拟任意条件语句。我有时会使用这种方法来模拟ZX Basic中的“ON x GOTO a,b,c”。

如果“true”为数值1，“false”为0，则像下面这样构造：

if A then goto B else goto C

与以下内容完全相同：

goto C+(B-C)*A

所以，是的，使用“computed goto”或自我修改功能，goto或jmp可以作为条件语句。

- Vatine

Answer 4

你需要根据输入结果进行分支，模拟条件分支的一种方法是使用自修改代码——你进行计算并将结果存储到正在执行的指令流中。你可以将无条件跳转的操作码放入指令流中，并对输入进行数学运算，以便根据输入的某些条件创建正确的跳转目标。例如，从y中减去x，如果为正则向右移位0填充，如果为负则向右移位1填充，然后加上基地址，并将该结果存储在jmp操作码之后。当你到达该jmp时，如果x==y，则跳转到一个地址，否则跳转到另一个地址。

- Jerry Coffin

Answer 5

“构建图灵完备的机器并不需要条件分支，但是当然任何图灵完备的机器都将提供条件分支作为其核心功能。已经证明，简单到 规则110元胞自动机 这样的系统也可以用来实现图灵机。你肯定不需要使用条件分支来从位桶中提取这样的系统。实际上，你只需使用一堆石头即可。重点是图灵机将提供条件分支，因此无论如何通过证明图灵完备性来实现条件分支。你必须在某个时候无条件地实现它，无论是使用岩石还是半导体中的 PN 结。”

- thodg

Answer 6

Z3 从抽象的角度来看只是图灵完备的。你可以拥有一个任意长的程序磁带，并让它计算每个条件分支的两侧。换句话说，对于每个分支，它都会计算出两个答案并告诉你应该忽略哪一个。显然，这会为每个条件分支创建指数级别更大的程序，因此你永远无法以图灵完备的方式使用这台机器。

- Gabe

Answer 7

如果一台机器可以分支，那么它就被认为是图灵完备的。

原因是有条件分支自动使任何计算机成为图灵完备。然而，还有一些机器不能跳转分支甚至IF，但仍被认为是图灵完备的。

处理只是识别输入以选择输出的过程。

分支是将这个过程形象化的一种方式，跳转的条件可以分类输入，你跳转到的位置存储了该输入的正确输出。

最后，为了澄清事情：

如果您有条件分支，您的计算机必须与图灵机在计算上等效。然而，还有很多其他方法可以使计算机实现图灵完备性（lambda、IF、CL）。

- Luke schoen