是否有条件地支持图灵完备性的要求？

我一直在寻找网络，我发现有些矛盾的答案。有些消息来源声称，只有当它有和有条件和无条件分支（我猜这是多余的）时，语言/机器/你拥有的是什么 - 有些人说只有无条件是必需的，只有条件是必需的。是否有条件地支持图灵完备性的要求？

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

德国Z3（显示在1941年5 工作）是由康拉德楚泽的设计。它是第一个通用数字电脑，但它是机电，而不是电子，因为它使用继电器的所有功能。它使用逻辑计算二进制数学。它可由穿孔带编程，但缺少条件分支。虽然图灵完备性没有设计为，但是它意外地发现了，因为它在1998年被发现为（但是要利用这个图灵完备性，复杂的，巧妙的黑客是必要的）。

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

1998年的论文摘要由R.罗哈斯还说（请注意，我没有读过本文，它只是从IEEE片段）：

计算机Z3，通过康拉德楚泽建在1938年至1941年之间，只能执行在打孔带中编码的固定序列浮点算术运算（加法，减法，乘法，除法和方形根）。从计算的历史观点看，有趣的问题是是否足以进行通用计算的这些操作是。该文件显示，实际上，包含这些算术指令的单个程序循环可以模拟其磁带为给定有限尺寸的任何图灵机。这是通过模拟条件分支的和纯粹的算术手段间接寻址完成的。因此Zuse的Z3是因此，至少在原则上如通用，因为如今的计算机具有有限的寻址空间。

总之，SOers，图灵完备性究竟需要什么类型的分支？假设无限存储器，只有goto或jmp分支构造（没有if或jnz构造）的语言才可以被认为是图灵完备的？

来源

2010-10-27 David Titarenco

原始的罗哈斯纸可以找到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？他提议为J（c1..cm）的否定二进制表示一起使用Z（z1..zm）的二进制表示，然后计算

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm))

将本品1只如果C和Z所有位不同，只有当z == j时才会发生。对z的分配（实质上是间接跳转）也必须分配给z1..zm。

罗哈斯还写了Conditional Branching is not Necessary for Universal Computation in von Neumann Computers。在那里，他提出了一个具有自修改代码和相对寻址的机器，以便您可以从内存中读取图灵指令，并修改程序以相应跳转。作为另一种选择，他提出了上述方法（对于Z3），仅使用LOAD（A），STORE（A），INC和DEC的版本。

来源

2010-10-31 11:32:19

我喜欢你的答案，但是当机器不能算术时会发生什么？或者，如果机器有点让人想起ZISC？谢谢！ – 2010-11-05 06:02:09

定义“算术”。通常的定义至少包括增加。（第二）Rojas机器没有添加，只有INC（他还讨论了不需要DEC）。无论如何，我无法提供一个证明，证明没有条件指令的ZISC将会或不会图灵完成;我个人认为它不会。 – 2010-11-05 06:11:40

谢谢你的洞察！ – 2010-11-06 04:07:26

从抽象的角度来看，Z3只是图灵完备的。你可以有一个任意长的程序磁带，只需要它计算每个条件分支的两边。换句话说，对于每个分支，它将计算两个答案，并告诉你哪一个要忽略。很显然，这将为每个有条件的分支创建指数规模较大的程序，因此您无法以图灵完备的方式使用本机。

来源

2010-10-27 04:11:19 Gabe

你需要一些可以基于（结果）输入的分支。

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

来源

2010-10-27 04:12:21

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

来源

2010-10-27 16:40:34

您提出了一个有趣的解决方案。如果机器是ZISC或Turing tarpit（没有算术运算）会怎么样？ – 2010-10-28 02:35:52

如果您可以计算goto或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或jmp可以充当条件。

来源

2010-10-31 09:27:32 Vatine

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

事实证明，可以使用像Rule 110 Cellular Automaton这样简单的系统来实现图灵机。你当然不需要条件分支来从比特桶中抽取这样一个系统。其实可以使用a bunch of rocks。

问题是一个图灵机将提供条件分支，所以你通过证明图灵完备性而做的事情有些实现条件分支。你必须在没有条件分支的情况下做到这一点，无论是半导体中的岩石还是PN结。

来源

2010-11-05 05:28:29 thodg

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

Hoever也有机器不能跳分支甚至IF，但仍然是图灵完成。

有条件分支的原因会自动使计算机Turing完成。

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

分支是对这一过程进行心理调整的一种方式，跳转的条件是可以对输入进行分类，分支的位置也为该输入存储正确的输出。

于是最后澄清; 如果您有条件分支，您的计算机必须在计算上等效。尽管如此，还有很多其他方法可以让计算机实现完整性。（lambda，IF's，CL）

来源

2012-03-27 05:51:12

是否有条件地支持图灵完备性的要求？

回答

相关问题