问题描述
我一直在网上搜索，但发现一些矛盾的答案。一些消息来源断言，只有当语言/机器/具有什么条件分支和无条件分支（我认为这是多余的）时，您的图灵才是完整的，有人说这是无条件的
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:
到底有什么复杂，聪明的黑客？
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.):
简而言之，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.
这篇关于条件分支是否是图灵完备性的要求？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！