条件分支是图灵完备性的要求吗？
我一直在网上搜索，发现了一些相互矛盾的答案。一些消息来源断言，语言/机器/你有什么是图灵完整的，当且仅当它具有两者条件和无条件分支（我认为这有点多余），有人说只有无条件分支是必需的，其他的则仅是有条件的。
德国 Z3（显示 5 月份工作） 1941）由 Konrad Zuse 设计。它 是第一个通用数字 电脑，但它是 机电式，而不是 电子的，因为它使用继电器来完成所有操作 功能。它使用逻辑计算 二进制数学。它可以通过以下方式编程： 打孔胶带，但缺少 条件分支。虽然没有设计 对于图灵完整性，它 意外的是，正如发现的那样 1998年（但为了利用这个 图灵完备、复杂、聪明 黑客是必要的）。
究竟有哪些复杂、巧妙的技巧？
R. Rojas 1998 年的一篇论文摘要也指出（请注意，我还没有读过这篇论文，它只是 IEEE 的一个片段。）：
计算机Z3，由 康拉德·祖斯 (Konrad Zuse) 1938 年至 1941 年间， 只能执行固定的序列 浮点算术运算 （加法、减法、 乘法、除法和平方 root）在打孔带中编码。一个 有趣的问题来自 计算历史的观点， 是这些操作是否 足以进行通用计算。 该论文表明，事实上， 包含这些的单个程序循环 算术指令可以模拟 任何图灵机，其磁带是 给定有限大小。这是由 模拟条件分支和 纯粹间接寻址 算术手段。 Zuse的Z3是 因此，至少在原则上， 像今天的计算机一样普遍 有一个有限的寻址空间。
简而言之，SOers，图灵完备性到底需要什么类型的分支？假设内存无限，语言可以仅具有 goto 或 jmp 分支结构（没有 if 或 jnz 结构）被认为是图灵完备的？
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:
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?
A 1998 paper Abstract by R. Rojas also states (Note that I haven't read this paper, it's just a snippet from 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.
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
原始 Rojas 论文可以在 找到在这里。基本思想是 Z3 仅支持无条件单循环（通过将指令带的末端粘合在一起）。您可以通过将所有代码部分一个接一个地放入循环中并使用变量 z 来确定要执行的部分来构建它的条件执行。在第 j 部分的开头，您设置
并读取本部分中的每个赋值 a = b op c
（即每个赋值都是无操作，活动部分除外）。现在，这仍然包括一个条件赋值：如何比较 z==j？他建议使用 z (z1..zm) 的二进制表示以及 j (c1..cm) 的否定二进制表示，然后计算
只有当 c 和 z 所有位都不同时，该乘积才会为 1，这将仅当 z==j 时才会发生。对 z 的赋值（本质上是间接跳转）也必须赋值给 z1..zm。
Rojas 还写了条件分支是对于冯·诺依曼计算机中的通用计算来说不是必需的。在那里，他提出了一种具有自修改代码和相对寻址的机器，这样你就可以从内存中读取图灵指令，并修改程序以进行相应的跳转。作为替代方案，他提出了上述方法（针对 Z3），其版本仅使用 LOAD(A)、STORE(A)、INC 和 DEC。
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
and then make each assignment
a = b op cin this section read(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
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 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.
如果只有算术表达式，则可以使用算术运算的某些属性。例如，根据某些条件（之前计算的），
A是 0 或 1，然后A*B+(1-A)*C计算表达式如果A则B否则C。If you have only arithmetical expressions you can use some properties of arithmetical operations. E.g., is
Ais either 0 or 1 depending on some condition (which is previously computed), thenA*B+(1-A)*Ccomputes the expressionif A then B else C.如果您可以计算
goto或jmp的地址，则可以模拟任意条件。我偶尔用它来模拟 ZX Basic 中的“ON x GOTO a,b,c”。如果“true”的数值为 1，而“false”的数值为 0，则类似于： 等同
于：
因此，是的，通过“计算的 goto”或自我修改的能力，goto 或 jmp 可以充当有条件的。
If you can compute the address for your
gotoorjmp, you can simulate arbritary conditionals. I occasionally used this to simulate "ON x GOTO a,b,c" in ZX Basic.If "true" has the numerical value 1 and "false" 0, then a construction like:
is identical to:
So, yes, with a "computed goto" or the ability to self-modify, a goto or jmp can act as a conditional.
您需要一些可以根据输入（结果）进行分支的东西。
模拟条件分支的一种方法是使用自修改代码——您进行计算，将其结果存入正在执行的指令流中。您可以将无条件跳转的操作码放入指令流中，并对输入进行数学运算，根据输入的某些条件集为该跳转创建正确的目标。例如，从 y 中减去 x，如果为正则右移至 0 填充，如果为负则右移至 1 填充，然后添加基地址，并将结果存储在紧跟 jmp 操作码之后。当您到达该 jmp 时，如果 x==y，您将转到一个地址，如果 x!=y，您将转到另一个地址。
You need something that can branch based on (results from) input.
One way to simulate conditional branches is with self-modifying code -- you do a computation that deposits its result into the stream of instructions being executed. You could put the op-code for an unconditional jump into the instruction stream, and do math on an input to create the correct target for that jump, depending on some set of conditions for the input. For example, subtract x from y, shift right to 0-fill if it was positive, or 1-fill if it was negative, then add a base address, and store that result immediately following the jmp op-code. When you get to that jmp, you'll go to one address if x==y, and another if x!=y.
您不需要条件分支来构建图灵完备的机器，但当然任何图灵完备的机器都会提供条件分支作为核心功能。
事实证明，像规则110元胞自动机这样简单的系统可以用来实现图灵机。您肯定不需要条件分支来从位桶中提取这样的系统。实际上，人们可以只使用一堆石头。
关键是图灵机将提供条件分支，因此无论如何，通过证明图灵完整性，您所做的就是在某种程度上实现条件分支。你必须在某个时刻没有条件分支地做到这一点，无论是岩石还是半导体中的 PN 结。
You don't need conditional branching to build a Turing-complete machine, but of course any Turing-complete machine will provide conditional branching as a core feature.
It was proved that systems as simple as the Rule 110 Cellular Automaton can be used to implement a Turing machine. You sure don't need conditional branching to pull such a system from the bit bucket. Actually one could just use a bunch of rocks.
The point is that a Turing machine will provide the conditional branching, so what you are doing anyway by proving Turing completeness is somewhat implementing conditional branching. You have to do it without conditional branching at some point, be it rocks or PN-junctions in semi-conductors.
从抽象的角度来看，Z3只是图灵完备的。您可以拥有任意长的程序磁带，并让它计算每个条件分支的两侧。换句话说，对于每个分支，它都会计算两个答案并告诉您忽略哪一个。显然，这会为您拥有的每个条件分支创建指数级更大的程序，因此您永远无法以图灵完备的方式使用这台机器。
The Z3 was only Turing complete from an abstract point of view. You can have an arbitrarily long program tape and just have it compute both sides of every conditional branch. In other words, for each branch, it would compute both answers and tell you which one to ignore. Obviously this creates exponentially larger programs for every conditional branch you would have, so you could never use this machine in a Turing-complete manner.
如果一台机器可以分支，那么它就被认为是图灵完备的。
原因是条件分支自动使任何计算机图灵完备。然而，也有一些机器不能跳转分支甚至IF，但仍然被认为是图灵完备的。
处理只是识别输入以选择输出的过程。
分支是理解此过程的一种方法，跳转的条件是可以对输入进行分类的条件，分支存储该输入的正确输出的位置。
最后，澄清一下：
如果你有条件分支，你的计算机在计算上必然等同于图灵机。然而，计算机还有很多其他方法可以实现图灵完备性（lambda、IF、CL）。
If a machine can branch, then yes it's considered Turing complete.
The reason is having conditional-branching automatically makes any computer Turing complete. However, there are also machines that can't jump branch or even IF but are still considered Turing complete.
Processing is just the process of identifying inputs in-order to select outputs.
Branching is one way to mentalize this process, the condition of the jump is what can classify inputs, the place you branch to stores the correct output for that input.
So finally, to clarify things:
If you have conditional branching your computer is necessarily computationally equivalent to a Turing machine. However, there are plenty of other ways for a computer to achieve Turing completeness (lambda, IF's, CL).