51
个编辑
更改
→Choice c-machines, oracle o-machines
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)除了在脚注中描述了如何使用a-machine来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他"假设选择总是在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，……”(侧重于脚注，The Undecidable，第138页)
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.
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).
预言机或 o-machine 是一种图灵机器，它将计算暂停在“ o”状态，同时，为了完成计算，它“等待”“oracle”（一个未指定的实体” ，除了说它不可能是一台机器”的决定(Turing(1939) ，The undecutable，p. 166-168)。
预言机或 o-machine 是一种图灵机器，它将计算暂停在“ o”状态，同时，为了完成计算，它“等待”“oracle”- 一个未指定的实体“除了说它不可能是一台机器”的决定(Turing(1939) ，The undecutable，p. 166-168)。
==Universal Turing machines==
==Universal Turing machines==