条件分支是否是图灵完备性的要求？ [英] Is conditional branching a requirement of Turing-completeness?
问题描述
我一直在网上搜索，但发现一些矛盾的答案。一些消息来源断言，只有当语言/机器/具有什么条件分支和无条件分支（我认为这是多余的）时，您的图灵才是完整的，有人说这是无条件的
I've been searching the web and I'm finding somewhat contradictory answers. Some sources assert that a language/machine/what-have-you is Turing complete if and only if it has both conditional and unconditional branching (which I guess is kind of redundant), some say that only unconditional is required, others that only conditional is required.
Reading about the German Z3 and ENIAC, Wikipedia says:
德国Z3（显示于1941年5月在
工作）是由Konrad Zuse设计的。它是第一台通用数字计算机，但它是机电的，而不是电子的，因为它使用了继电器的所有功能。它使用
二进制数学进行逻辑计算。它可以用
的打孔带编程，但是缺少
的条件分支。虽然不是为图灵完备性设计
的，但它却偶然地是
，因为它是在1998年被发现的
（但要利用此
Turing完备性，复杂，聪明的
黑客是必要的。）
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).
到底有什么复杂，聪明的黑客？
What complex, clever hacks, exactly?
R。Rojas于1998年发表的论文摘要也指出（请注意，我还没有读过这篇论文，它只是IEEE的摘录。）：
A 1998 paper Abstract by R. Rojas also states (Note that I haven't read this paper, it's just a snippet from IEEE.):
由
Konrad Zuse在1938年至1941年之间制造的计算机Z3，
只能执行
浮点算术运算
的固定序列（加，减，
的乘法，除法和平方根
）编码在打孔的磁带中。从计算历史的
角度出发，有一个
有趣的问题要问，
是这些运算是否足以用于通用计算。
该文件显示，实际上，包含这些
算术指令的
单个程序循环可以模拟
的任何Turing机器，该机器的磁带在给定有限大小的情况下为
。这是通过
模拟条件分支和
纯粹通过
算术方式进行间接寻址来完成的。 Zuse的Z3因此至少在原理上是
，因为在当今的
具有有限的寻址空间的计算机中，
是通用的。
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 分支构造的语言是否可以（如果没有，则没有 或 jnz 构造）是否被视为图灵完成的？
In short, SOers, what type of branching is exactly required for Turing-completeness? Assuming infinite memory, can a language with only a goto or jmp branching construct (no if or jnz constructs) be considered Turing-complete?
推荐答案
原始的Rojas论文可以找到此处。基本思想是Z3仅支持无条件的单循环（通过将指令带的末端粘合在一起）。通过将所有代码段一个接一个地放入循环中，并使用变量z来确定要执行的部分，可以构建条件执行程序。在第j节的开头，您设置
The original Rojas paper can be found here. The basic idea is that the Z3 only supports a unconditional single loop (by gluing the ends of the instruction tape together). You build conditional execution of it by putting all code sections one after another in the loop, and having a variable z that determines which section to execute. At the beginning of section j, you set
if (z==j) then t=0 else t=1
然后使每个作业 a = b op c 在本节中
and then make each assignment a = b op c in this section read
a = a*t + (b op c)*(1-t)
（即每个作业都是空操作，活动部分除外）。现在，这仍然包括一个条件赋值：如何比较z == j？他建议使用z的二进制表示形式（z1..zm）和j的取反二进制表示形式（c1..cm），然后计算
(i.e. each assignment is a no-op, except in the active section). Now, this still includes a conditional assignment: how to compare z==j? He proposes to use the binary representation of z (z1..zm) along with the negated binary representation of j (c1..cm), and then compute
t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm))
仅当c和z的所有位不同时，此乘积将为1，仅当z == j时才会出现。对z的赋值（本质上是间接跳转）也必须对z1..zm赋值。
This product will be 1 only if c and z differ in all bits, which will happen only if z==j. An assignment to z (which essentially is an indirect jump) must also assign to z1..zm.
Rojas也写了在冯·诺依曼计算机中进行通用计算不需要条件分支。他在那里提出了一种具有自我修改代码和相对地址的机器，以便您可以从内存中读取Turing指令，并修改程序以进行相应的跳转。作为替代方案，他在仅使用LOAD（A），STORE（A），INC和DEC的版本中提出了上述方法（适用于Z3）。
Rojas has also written Conditional Branching is not Necessary for Universal Computation in von Neumann Computers. There he proposes a machine with self-modifying code and relative addressing, so that you can read the Turing instructions from memory, and modify the program to jump accordingly. As an alternative, he proposes the above approach (for Z3), in a version that only uses LOAD(A), STORE(A), INC and DEC.
这篇关于条件分支是否是图灵完备性的要求？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
