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

Question

我一直在网上搜索，发现有些矛盾的答案。一些消息来源断言，一种语言/机器/你拥有的东西是图灵完备的当且仅当它具有 两者 条件和无条件分支(我猜这有点多余)，有人说只需要无条件分支，其他人说只需要条件分支。

关于德语的阅读Z3和 ENIAC ，维基百科说:

The German Z3 (shown working in May 1941) was designed by Konrad Zuse. It was the first general-purpose digital computer, but it was electromechanical, rather than electronic, as it used relays for all functions. It computed logically using binary math. It was programmable by punched tape, but lacked the conditional branch. While not designed for Turing-completeness, it accidentally was, as it was found out in 1998 (but to exploit this Turing-completeness, complex, clever hacks were necessary).

究竟是什么复杂、聪明的黑客？

1998 年 R. Rojas 的一篇论文摘要也指出(请注意，我还没有阅读这篇论文，它只是 IEEE 的一个片段。):

The computing machine Z3, built by Konrad Zuse between 1938 and 1941, could execute only fixed sequences of floating point arithmetical operations (addition, subtraction, multiplication, division, and square root) coded in a punched tape. An interesting question to ask, from the viewpoint of the history of computing, is whether or not these operations are sufficient for universal computation. The paper shows that, in fact, a single program loop containing these arithmetical instructions can simulate any Turing machine whose tape is of a given finite size. This is done by simulating conditional branching and indirect addressing by purely arithmetical means. Zuse's Z3 is therefore, at least in principle, as universal as today's computers that have a bounded addressing space.

简而言之，SOers，图灵完备性究竟需要什么类型的分支？假设无限内存，可以使用只有 goto 的语言吗？或 jmp分支结构(没有 if 或 jnz 结构)被认为是图灵完备的吗？

Answer 1

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