条件分支是图灵完备性的要求吗?

可以找到原始的罗哈斯纸 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。

罗哈斯也写过 Conditional Branching is not Necessary for Universal Computation in von Neumann Computers

如果只有算术表达式,则可以使用算术运算的某些属性。E、 g.,是 A 是0还是1取决于某些条件(之前计算过),然后 A*B+(1-A)*C 计算表达式 if A then B else C

你需要一些基于输入(结果)的分支。

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

如果你能计算出 goto 或 jmp

如果“true”的数值为1,而“false”为0,则结构如下:

if A then goto B else goto C

相同于:

goto C+(B-C)*A

所以,是的,有了“计算的goto”或自我修改的能力,goto或jmp就可以充当一个条件。

您不需要条件分支来构建图灵完备机,但是任何图灵完备机都会提供条件分支作为核心特性。

事实证明,像 Rule 110 Cellular Automaton a bunch of rocks .

关键是图灵机器将提供条件分支,所以通过证明图灵完备性所做的工作在某种程度上实现了条件分支。无论是在半导体中的岩石或PN结,你都必须在某个点上不带条件分支。

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

原因是有条件分支会自动使任何计算机图灵完成。然而,也有一些机器不能跳转分支,即使这样,仍然被认为是图灵完备的。

分支是使这个过程智能化的一种方法,跳转的条件是什么可以对输入进行分类,分支的位置是存储该输入的正确输出的位置。

最后,澄清一下:

如果你有条件分支,你的计算机在计算上必然等同于图灵机器。然而,对于一台计算机来说,有很多其他的方法来实现图灵完备性(lambda,IF's,CL)。