Dav*_*nco 10 theory computer-science branch turing-complete
我一直在网上搜索,我发现有些矛盾的答案.一些消息来源声称,语言/机器/什么具备的,你是图灵完备当且仅当它有两个有条件和无条件分支(我的猜测是一种多余的),有的说只有无条件的要求,别人只有条件是必须的.
德国Z3(显示于1941年5月工作)由Konrad Zuse设计.它是第一台通用型数字计算机,但它是机电式的,而不是电子的,因为它使用了继电器用于所有功能.它使用二进制数学逻辑计算.它可以通过穿孔带编程,但缺少条件分支.虽然不是为图灵完整性而设计的,但它偶然发生在1998年(但为了利用这种图灵完整性,复杂,聪明的黑客是必要的).
究竟是什么复杂,聪明的黑客？
R. Rojas撰写的1998年论文摘要也指出(请注意,我没有读过这篇论文,它只是IEEE的一个片段.):
由Konrad Zuse在1938年至1941年之间建造的计算机器Z3可以仅执行在穿孔带中编码的浮点算术运算(加法,减法,乘法,除法和平方根)的固定序列.从计算历史的角度来看,一个有趣的问题是这些操作是否足以进行通用计算.该论文表明,实际上,包含这些算术指令的单个程序循环可以模拟其磁带具有给定有限大小的任何图灵机.这是通过纯粹的算术方法模拟条件分支和间接寻址来完成的.因此,Zuse的Z3至少在原则上与今天具有有限寻址空间的计算机一样普遍.
简而言之,SOers,Turing-completeness究竟需要什么类型的分支？假设无限的内存,只有一个goto或jmp分支结构(没有if或jnz构造)的语言可以被认为是图灵完备吗？
Mar*_*wis 10
最初的罗哈斯纸可以在这里找到.基本思想是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.
Rojas还写了条件分支对冯诺依曼计算机中的通用计算不是必需的.在那里,他提出了一个具有自修改代码和相对寻址的机器,以便您可以从内存中读取图灵指令,并修改程序以相应地跳转.作为替代方案,他提出了上述方法(对于Z3),在仅使用LOAD(A),STORE(A),INC和DEC的版本中.
如果只有算术表达式，则可以使用算术运算的某些属性。例如，A根据某些条件（之前已计算）， is 为 0 或 1，然后A*B+(1-A)*C计算表达式if A then B else C。