150
个编辑
更改
→Choice c-machines, oracle o-machines
一个有趣的问题是：用具体编程语言表示的计算模型是否是图灵等价的？虽然真实计算机的计算是基于有限状态的，因此无法模拟图灵机，但编程语言本身并不一定具有这种限制。Kirner等人在2009年的研究表明，在通用编程语言中，有些语言是图灵完备的，而有些则不是。例如，ANSI C并不等同于图灵机，因为ANSI C的所有实例（由于标准出于遗留的原因，故意不定义某些行为，所以可以有不同的实例）都意味着有限空间的内存。这是因为内存引用数据类型的大小，称为指针，可以在语言内部访问。然而，其他编程语言，如Pascal，则没有这个功能，这使得它们在原则上是图灵等价的。只是原则上是图灵等价的，因为编程语言中的内存分配是允许失败的，也就是说，当忽略失败的内存分配时，编程语言可以是图灵等价的，但在真实计算机上可执行的编译程序却不能。
一个有趣的问题是：用具体编程语言表示的计算模型是否是图灵等价的？虽然真实计算机的计算是基于有限状态的，因此无法模拟图灵机，但编程语言本身并不一定具有这种限制。Kirner等人在2009年的研究表明，在通用编程语言中，有些语言是图灵完备的，而有些则不是。例如，ANSI C并不等同于图灵机，因为ANSI C的所有实例（由于标准出于遗留的原因，故意不定义某些行为，所以可以有不同的实例）都意味着有限空间的内存。这是因为内存引用数据类型的大小，称为指针，可以在语言内部访问。然而，其他编程语言，如Pascal，则没有这个功能，这使得它们在原则上是图灵等价的。只是原则上是图灵等价的，因为编程语言中的内存分配是允许失败的，也就是说，当忽略失败的内存分配时，编程语言可以是图灵等价的，但在真实计算机上可执行的编译程序却不能。
==Choice c-machines, oracle o-machines==
==选择C型机器、Oracle的O型机器==
Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":
Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":
早在1936年的论文中，图灵就对 "运动......完全由配置决定 "的 "自动机"和 "选择机 "进行了区分：
{{quote|...whose motion is only partially determined by the configuration ... When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems.|''The Undecidable'', p. 118}}
{{quote|...whose motion is only partially determined by the configuration ... When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems.|''The Undecidable'', p. 118}}
...它的运动只是部分由配置决定…当这样一台机器达到其中一种不明确的配置时，它不能继续运行，直到外部操作者做出任意的选择。如果我们使用机器来处理公理系统，就会出现这种情况
{{quote|...它的运动只是部分由配置决定…当这样一台机器达到其中一种不明确的配置时，它不能继续运行，直到外部操作者做出任意的选择。如果我们使用机器来处理公理系统，就会出现这种情况。
——The Undecidable，第118页
——The Undecidable，第118页
}}
Turing (1936) does not elaborate further except in a footnote in which he describes how to use an a-machine to "find all the provable formulae of the [Hilbert] calculus" rather than use a choice machine. He "suppose[s] that the choices are always between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 or 1, i<sub>2</sub> = 0 or 1, ..., i<sub>n</sub> = 0 or 1), and hence the number 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> completely determines the proof. The automatic machine carries out successively proof 1, proof 2, proof 3, ..." (Footnote ‡, The Undecidable, p. 138)
Turing (1936) does not elaborate further except in a footnote in which he describes how to use an a-machine to "find all the provable formulae of the [Hilbert] calculus" rather than use a choice machine. He "suppose[s] that the choices are always between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 or 1, i<sub>2</sub> = 0 or 1, ..., i<sub>n</sub> = 0 or 1), and hence the number 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> completely determines the proof. The automatic machine carries out successively proof 1, proof 2, proof 3, ..." (Footnote ‡, The Undecidable, p. 138)
Turing(1936)除了在脚注中描述了如何使用自动机来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他"假设选择总是在0和1之间。那么每个证明将由i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 或 1, i<sub>2</sub> = 0 或 1, ..., i<sub>n</sub> = 0 或 1) 的选择序列决定，因此数字 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> 完全决定了证明。自动机依次执行验证1、验证2、验证3，……”(侧重于脚注，The Undecidable，第138页)
Turing(1936)除了在脚注中描述了如何使用自动机来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他"假设选择总是在0和1之间。那么每个证明将由i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 或 1, i<sub>2</sub> = 0 或 1, ..., i<sub>n</sub> = 0 或 1) 的选择序列决定，因此数字 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> 完全决定了证明。自动机依次执行验证1、验证2、验证3，……”
This is indeed the technique by which a deterministic (i.e., a-) Turing machine can be used to mimic the action of a nondeterministic Turing machine; Turing solved the matter in a footnote and appears to dismiss it from further consideration.
This is indeed the technique by which a deterministic (i.e., a-) Turing machine can be used to mimic the action of a nondeterministic Turing machine; Turing solved the matter in a footnote and appears to dismiss it from further consideration.
这确实是一种技术，通过这种技术，一个确定型的(即a -)图灵机可以用来模拟一个非确定型的图灵机的动作; Turing在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。
这确实是一种技术，通过这种技术，一个确定型的(即a -)图灵机可以用来模拟一个非确定型的图灵机的行为; 图灵在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。
An oracle machine or o-machine is a Turing a-machine that pauses its computation at state "o" while, to complete its calculation, it "awaits the decision" of "the oracle"—an unspecified entity "apart from saying that it cannot be a machine" (Turing (1939), The Undecidable, p. 166–168).
An oracle machine or o-machine is a Turing a-machine that pauses its computation at state "o" while, to complete its calculation, it "awaits the decision" of "the oracle"—an unspecified entity "apart from saying that it cannot be a machine" (Turing (1939), The Undecidable, p. 166–168).
Oracle机或 o-machine是一种图灵机器，它将计算暂停在“o”状态，同时，为了完成计算，它“等待”“oracle”- 一个未指定的实体（不是一台机器）“的决定(图灵(1939) ，The undecutable，p.166-168)。
==Universal Turing machines==
==Universal Turing machines==