12

我一直在网上搜索，我发现有些矛盾的答案。一些消息来源断言，当且仅当它同时具有条件分支和无条件分支（我猜这有点多余）时，语言/机器/你有什么是图灵完备的，有人说只需要无条件，其他人只需要条件是必须的。

阅读有关德国Z3和ENIAC的信息，维基百科说：

德国 Z3（显示于 1941 年 5 月工作）由 Konrad Zuse 设计。它是第一台通用数字计算机，但它是机电的，而不是电子的，因为它使用继电器来完成所有功能。它使用二进制数学进行逻辑计算。它可以通过穿孔带进行编程，但缺少条件分支。虽然不是为图灵完备性而设计的，但它意外地是，正如在 1998 年发现的那样（但为了利用这种图灵完备性，需要复杂、聪明的 hack）。

究竟是什么复杂、巧妙的技巧？

R. Rojas 的 1998 年论文摘要也指出（请注意，我没有读过这篇论文，它只是来自 IEEE 的一个片段。）：

计算机 Z3 由 Konrad Zuse 在 1938 年至 1941 年间制造，只能执行在穿孔磁带中编码的固定浮点算术运算序列（加法、减法、乘法、除法和平方根）。从计算历史的角度来看，一个有趣的问题是这些操作是否足以进行通用计算。该论文表明，事实上，包含这些算术指令的单个程序循环可以模拟任何图灵机，其磁带具有给定的有限大小。这是通过纯算术方法模拟条件分支和间接寻址来完成的。因此，至少在原则上，Zuse 的 Z3 与当今具有有限寻址空间的计算机一样通用。

简而言之，SOers，图灵完备性究竟需要哪种类型的分支？假设内存无限，只有一个goto或jmp分支结构（没有if或jnz结构）的语言可以被认为是图灵完备的吗？

4

7 回答 7

10

可以在这里找到原始的 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 Computers 中写过 Conditional Branching is not Necessary for Universal Computation。在那里他提出了一种具有自修改代码和相对寻址的机器，以便您可以从内存中读取图灵指令，并修改程序以进行相应的跳转。作为替代方案，他提出了上述方法（针对 Z3），其版本仅使用 LOAD(A)、STORE(A)、INC 和 DEC。

于 2010-10-31T11:32:19.053 回答
4

如果您只有算术表达式，则可以使用算术运算的某些属性。例如，isA是 0 或 1，具体取决于某些条件（先前已计算），然后A*B+(1-A)*C计算表达式if A then B else C。

于 2010-10-27T16:40:34.357 回答
4

如果您可以计算gotoor的地址jmp，则可以模拟任意条件。我偶尔用它来模拟 ZX Basic 中的“ON x GOTO a,b,c”。

如果“真”的数值为 1，“假”的值为 0，则结​​构如下：

if A then goto B else goto C

等同于：

goto C+(B-C)*A

所以，是的，通过“计算 goto”或自我修改的能力，goto 或 jmp 可以充当条件。

于 2010-10-31T09:27:32.363 回答
3

您需要可以根据输入（结果）进行分支的东西。

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

于 2010-10-27T04:12:21.177 回答
2

您不需要条件分支来构建图灵完备的机器，但当然任何图灵完备的机器都会提供条件分支作为核心功能。

事实证明，像Rule 110 元胞自动机这样简单的系统可以用来实现图灵机。您肯定不需要条件分支来从位桶中提取这样的系统。实际上，一个人可以只用一堆石头。

关键是图灵机将提供条件分支，所以无论如何你通过证明图灵完整性所做的事情在某种程度上实现了条件分支。您必须在某些时候不进行条件分支，无论是岩石还是半导体中的 PN 结。

于 2010-11-05T05:28:29.403 回答
1

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

于 2010-10-27T04:11:19.403 回答
1

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

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

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

分支是思考这个过程的一种方法，跳转的条件是可以对输入进行分类，分支存储该输入的正确输出的地方。

所以最后，澄清一下：

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

于 2012-03-27T05:51:12.587 回答