150
个编辑
更改
跳到导航
跳到搜索
第639行：
第639行： − + − 通用图灵机+ 第653行：
第653行： − 正如图灵在The Undecidable一书中所写，第128页(斜体) :+ − 我们可以发明一个机器，用来计算任何可计算的序列。如果向这台机器U提供一盘磁带，磁带的开头写着某台计算机M的一串用分号隔开的五元组，那么U将计算出与M相同的序列。+ + + − 这一发现现在被认为是理所当然的，但在当时(1936年) ，它被认为是惊人的。Turing称之为“通用机器”(缩写为“U”)的计算模型被一些人(参见Davis(2000))认为是产生存储程序计算机概念的基础理论突破。+ + + + + − ——Minsky（1967），第104页 − 就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数系数。这个结果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)+
→Universal Turing machines
Oracle机或 o-machine是一种图灵机器，它将计算暂停在“o”状态，同时，为了完成计算，它“等待”“oracle”- 一个未指定的实体（不是一台机器）“的决定(图灵(1939) ，The undecutable，p.166-168)。
Oracle机或 o-machine是一种图灵机器，它将计算暂停在“o”状态，同时，为了完成计算，它“等待”“oracle”- 一个未指定的实体（不是一台机器）“的决定(图灵(1939) ，The undecutable，p.166-168)。
==Universal Turing machines==
==通用图灵机==
{{Main|Universal Turing machine}}
{{Main|Universal Turing machine}}
As Turing wrote in The Undecidable, p. 128 (italics added):
As Turing wrote in The Undecidable, p. 128 (italics added):
正如图灵在<The Undecidable>一书中所写，第128页 :
{{quote|It is possible to invent a ''single machine'' which can be used to compute ''any'' computable sequence. If this machine '''U''' is supplied with the tape on the beginning of which is written the string of quintuples separated by semicolons of some computing machine '''M''', then '''U''' will compute the same sequence as '''M'''.}}
{{quote|It is possible to invent a ''single machine'' which can be used to compute ''any'' computable sequence. If this machine '''U''' is supplied with the tape on the beginning of which is written the string of quintuples separated by semicolons of some computing machine '''M''', then '''U''' will compute the same sequence as '''M'''.}}
{{quote|我们可以发明一个机器，用来计算任何可计算序列。如果向机器U提供纸带，纸带的开头写着计算机M用分号隔开的五元数组，那么机器U将计算出与机器M相同的序列
}}
This finding is now taken for granted, but at the time (1936) it was considered astonishing. The model of computation that Turing called his "universal machine"—"U" for short—is considered by some (cf. Davis (2000)) to have been the fundamental theoretical breakthrough that led to the notion of the stored-program computer.
This finding is now taken for granted, but at the time (1936) it was considered astonishing. The model of computation that Turing called his "universal machine"—"U" for short—is considered by some (cf. Davis (2000)) to have been the fundamental theoretical breakthrough that led to the notion of the stored-program computer.
虽然这一发现现在被认为是理所当然的，但在当时(1936年) ，很多人认为这是不可思议的。图灵称之为“通用机器”(缩写为“U”)的计算模型被一些人(参见Davis(2000))认为是产生存储程序计算机概念的基础理论的突破。
{{quote|Turing's paper ... contains, in essence, the invention of the modern computer and some of the programming techniques that accompanied it.|Minsky (1967), p. 104}}
{{quote|Turing's paper ... contains, in essence, the invention of the modern computer and some of the programming techniques that accompanied it.|Minsky (1967), p. 104}}
{{quote|
图灵的论文......实质上包含了现代计算机的发明以及伴随着它的一些编程技术。
图灵的论文......实质上包含了现代计算机的发明以及伴随着它的一些编程技术。
——Minsky（1967），P.104
}}
In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates. This result was obtained in 1966 by F. C. Hennie and R. E. Stearns. (Arora and Barak, 2009, theorem 1.9)
In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates. This result was obtained in 1966 by F. C. Hennie and R. E. Stearns. (Arora and Barak, 2009, theorem 1.9)
就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数倍。这个结果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)
==Comparison with real machines==
==Comparison with real machines==