我一直在搜索网络,但是发现有些答案相互矛盾。一些来源声称,只有具备条件和无条件分支(这可能有点冗余)的语言/机器/等才是图灵完备的,有些人则说仅需要无条件分支,还有些人则说仅需要条件分支。
关于德国的Z3和ENIAC,维基百科上写道:
“德国的Z3(1941年5月展示工作)由康拉德·祖斯设计。它是第一台通用数字计算机,但是它是电气机械式的,而不是电子式的,因为它使用继电器进行所有功能。它使用二进制数学进行逻辑计算。它可以通过打孔纸带进行编程,但缺少条件分支。虽然它不是为了图灵完备性而设计的,但在1998年发现它意外地具有图灵完备性(但要利用这种图灵完备性,需要复杂的巧妙的技巧)。”
那么到底是哪些复杂的巧妙的技巧呢?
1998年R. Rojas的一篇论文摘要也指出(请注意,我没有阅读这篇论文,这只是IEEE上的一小部分内容)。
在计算机历史的角度来看,Konrad Zuse在1938年至1941年间建造的计算机Z3只能执行编码在打孔纸带上的固定浮点运算序列(加减乘除和平方根)。一个有趣的问题是,这些操作是否足以进行通用计算。本文表明,事实上,仅包含这些算术指令的单个程序循环可以模拟任何具有给定有限尺寸磁带的图灵机。这是通过纯粹的算术手段模拟条件分支和间接寻址完成的。因此,Zuse的Z3至少在原则上与今天具有有限寻址空间的计算机一样通用。 简而言之,SOers,图灵完备性确切需要哪种类型的分支?假设内存无限大,仅使用goto或jmp分支结构(无if或jnz结构)的语言是否可以被认为是图灵完备的?
关于德国的Z3和ENIAC,维基百科上写道:
“德国的Z3(1941年5月展示工作)由康拉德·祖斯设计。它是第一台通用数字计算机,但是它是电气机械式的,而不是电子式的,因为它使用继电器进行所有功能。它使用二进制数学进行逻辑计算。它可以通过打孔纸带进行编程,但缺少条件分支。虽然它不是为了图灵完备性而设计的,但在1998年发现它意外地具有图灵完备性(但要利用这种图灵完备性,需要复杂的巧妙的技巧)。”
那么到底是哪些复杂的巧妙的技巧呢?
1998年R. Rojas的一篇论文摘要也指出(请注意,我没有阅读这篇论文,这只是IEEE上的一小部分内容)。
在计算机历史的角度来看,Konrad Zuse在1938年至1941年间建造的计算机Z3只能执行编码在打孔纸带上的固定浮点运算序列(加减乘除和平方根)。一个有趣的问题是,这些操作是否足以进行通用计算。本文表明,事实上,仅包含这些算术指令的单个程序循环可以模拟任何具有给定有限尺寸磁带的图灵机。这是通过纯粹的算术手段模拟条件分支和间接寻址完成的。因此,Zuse的Z3至少在原则上与今天具有有限寻址空间的计算机一样通用。 简而言之,SOers,图灵完备性确切需要哪种类型的分支?假设内存无限大,仅使用goto或jmp分支结构(无if或jnz结构)的语言是否可以被认为是图灵完备的?