150
个编辑
更改
→与实际机器的比较
1.Anything a real computer can compute, a Turing machine can also compute. For example: "A Turing machine can simulate any type of subroutine found in programming languages, including recursive procedures and any of the known parameter-passing mechanisms" (Hopcroft and Ullman p. 157). A large enough FSA can also model any real computer, disregarding IO. Thus, a statement about the limitations of Turing machines will also apply to real computers.
1.Anything a real computer can compute, a Turing machine can also compute. For example: "A Turing machine can simulate any type of subroutine found in programming languages, including recursive procedures and any of the known parameter-passing mechanisms" (Hopcroft and Ullman p. 157). A large enough FSA can also model any real computer, disregarding IO. Thus, a statement about the limitations of Turing machines will also apply to real computers.
2.The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data.
3.Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media.
4.Descriptions of real machine programs using simpler abstract models are often much more complex than descriptions using Turing machines. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent deterministic finite automaton (DFA) on a given real machine has quadrillions. This makes the DFA representation infeasible to analyze.
5.Turing machines describe algorithms independent of how much memory they use. There is a limit to the memory possessed by any current machine, but this limit can rise arbitrarily in time. Turing machines allow us to make statements about algorithms which will (theoretically) hold forever, regardless of advances in ''conventional'' computing machine architecture.
6.Turing machines simplify the statement of algorithms. Algorithms running on Turing-equivalent abstract machines are usually more general than their counterparts running on real machines, because they have arbitrary-precision data types available and never have to deal with unexpected conditions (including, but not limited to, running [[out of memory]]).
# 区别只在于图灵机有能力处理无限制的数据量。然而，在有限的时间内，图灵机（像实际的机器）只能操纵处理的数据量。
# 区别只在于图灵机有能力处理无限制的数据量。然而，在有限的时间内，图灵机（像实际的机器）只能操纵处理的数据量。
# 像图灵机一样，实际的机器可以根据需要，通过获得更多的磁盘或其他存储介质，扩大其存储空间。
# 像图灵机一样，实际的机器可以根据需要，通过获得更多的磁盘或其他存储介质，扩大其存储空间。
# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如，描述算法的图灵机可能有几百个状态，而给定实际机器上的等效确定性有限自动机（deterministic finite automaton，DFA）却有四千亿个状态。这使得DFA的表示方式无法分析。
# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如，描述算法的图灵机可能有几百个状态，而给定实际机器上的等效确定性有限自动机（deterministic finite automaton，DFA）却有四千亿个状态。这使得DFA的表示方式无法分析。
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限，但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明，这些声明（理论上）将永远成立，而不考虑传统计算机架构的进步。
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限，但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明，这些声明（理论上）将永远成立，而不考虑传统计算机架构的进步。