150
个编辑
更改
跳到导航
跳到搜索
第679行：
第679行： − + − 与真实机器的比较+ 第692行：
第692行： − 人们常说，图灵机不同于简单的自动机，它和真正的机器一样强大，能够执行真实程序所能执行的任何操作。在这句话中被忽略的是，由于真实的机器只能有有限数量的配置，这个“真实的机器”其实只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。+
→Comparison with real machines
就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数倍。这个结果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)
就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数倍。这个结果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)
==Comparison with real machines==
==与真实机器的比较==
[[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces|链接=Special:FilePath/Lego_Turing_Machine.jpg]]
[[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces|链接=Special:FilePath/Lego_Turing_Machine.jpg]]
It is often said that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can. What is neglected in this statement is that, because a real machine can only have a finite number of configurations, this "real machine" is really nothing but a finite state machine. On the other hand, Turing machines are equivalent to machines that have an unlimited amount of storage space for their computations.
It is often said that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can. What is neglected in this statement is that, because a real machine can only have a finite number of configurations, this "real machine" is really nothing but a finite state machine. On the other hand, Turing machines are equivalent to machines that have an unlimited amount of storage space for their computations.
人们常说，图灵机不同于简单的自动机，它和真正的机器一样强大，能够执行真实程序所能执行的任何操作。在这句话中被忽略的是，由于真实的机器只能有有限数量的配置，所以这里的“真实的机器”其实只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。
There are a number of ways to explain why Turing machines are useful models of real computers:
There are a number of ways to explain why Turing machines are useful models of real computers: