更改

就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数倍。这个结果是由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)

==与真实机器的比较==

==与实际机器的比较==

A Turing machine realization using [[Lego pieces]]

A Turing machine realization using [[Lego pieces]]

使用乐高积木实现的图灵机

使用乐高积木实现的图灵机[[Lego pieces]]

 

It is often said{{By whom|date=February 2016}} 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.

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:

有很多方法可以解释为什么图灵机是 真实计算机的有用模型:

有很多方法可以解释为什么图灵机是实际计算机的有用模型:

# 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.

# 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.

凡是真实计算机能计算的东西，图灵机也能计算。例如："图灵机可以模拟真实的计算机，也可以计算真实的计算机。"图灵机可以模拟编程语言中任何类型的子程序，包括递归程序和任何已知的参数传递机制" (Hopcroft and Ullman 第157页)。一个足够大的FSA也可以模拟任何真实的计算机，而不用考虑IO。因此，关于图灵机的局限性的说法也将适用于真实计算机。

# 凡是真正的计算机能计算的东西，图灵机也能计算。例如，"图灵机可以模拟编程语言中的任何类型的子程序，包括递归程序和任何已知的参数传递机制"(Hopcroft and Ullman 第157页)。一个足够大的FSA也可以模拟任何真正的计算机，而不用考虑IO。因此，关于图灵机的局限性的说法也将适用于实际计算机。

# 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.

# 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.

 

# Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media.

# Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media.

 

# 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.

# 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.

# 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.

# 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.

# 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]]).

# 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]]).

 

====Computational complexity theory====

====计算复杂性理论====

 

{{further|Computational complexity theory}}

{{further|Computational complexity theory}}

A limitation of Turing machines is that they do not model the strengths of a particular arrangement well. For instance, modern stored-program computers are actually instances of a more specific form of [[abstract machine]] known as the [[random-access stored-program machine]] or RASP machine model. Like the [[universal Turing machine]], the RASP stores its "program" in "memory" external to its finite-state machine's "instructions". Unlike the universal Turing machine, the RASP has an infinite number of distinguishable, numbered but unbounded "registers"—memory "cells" that can contain any integer (cf. Elgot and Robinson (1964), Hartmanis (1971), and in particular Cook-Rechow (1973); references at [[random access machine]]). The RASP's finite-state machine is equipped with the capability for indirect addressing (e.g., the contents of one register can be used as an address to specify another register); thus the RASP's "program" can address any register in the register-sequence. The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing machine; thus when Turing machines are used as the basis for bounding running times, a 'false lower bound' can be proven on certain algorithms' running times (due to the false simplifying assumption of a Turing machine). An example of this is [[binary search]], an algorithm that can be shown to perform more quickly when using the RASP model of computation rather than the Turing machine model.

A limitation of Turing machines is that they do not model the strengths of a particular arrangement well. For instance, modern stored-program computers are actually instances of a more specific form of [[abstract machine]] known as the [[random-access stored-program machine]] or RASP machine model. Like the [[universal Turing machine]], the RASP stores its "program" in "memory" external to its finite-state machine's "instructions". Unlike the universal Turing machine, the RASP has an infinite number of distinguishable, numbered but unbounded "registers"—memory "cells" that can contain any integer (cf. Elgot and Robinson (1964), Hartmanis (1971), and in particular Cook-Rechow (1973); references at [[random access machine]]). The RASP's finite-state machine is equipped with the capability for indirect addressing (e.g., the contents of one register can be used as an address to specify another register); thus the RASP's "program" can address any register in the register-sequence. The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing machine; thus when Turing machines are used as the basis for bounding running times, a 'false lower bound' can be proven on certain algorithms' running times (due to the false simplifying assumption of a Turing machine). An example of this is [[binary search]], an algorithm that can be shown to perform more quickly when using the RASP model of computation rather than the Turing machine model.

图灵机的一个局限性在于它们不能很好地模拟特定排列的优势。例如，现代存储程序计算机实际上是一种更具体的抽象机器的实例，这种抽象机器被称为随机存取存储程序机器或 RASP 机器模型。与通用图灵机一样，RASP 将其“程序”存储在有限状态机的“指令”之外的“内存”中。与通用图灵机不同的是，RASP 具有无限数量可区分的、有编号但无限制的“寄存器”ー可以包含任何整数的内存 "单元"(参见Elgot和Robinson(1964)，Hartmanis(1971)，特别是Cook-Rechow(1973)；参考随机存取机) RASP 的有限状态机可以间接寻址(例如，一个寄存器的内容可以用作另一个寄存器的地址) ，因此当图灵机被用作约束运行时间的基础时，可以证明某些算法的运行时间有一个 "假下限"（由于图灵机的假简化假设）。这方面的一个例子是二进制搜索，当使用 RASP 计算模型而不是图灵机模型时，可以证明这种算法的运行速度更快。

图灵机的一个局限性在于它们不能很好地模拟特定排列的优势。例如，现代存储程序计算机实际上是一种更具体的抽象机器的实例，这种抽象机器被称为随机存取存储程序机器或 RASP机器模型。与通用图灵机一样，RASP将其“程序”存储在有限状态机的“指令”之外的“内存”中。与通用图灵机不同的是，RASP具有无限数量可区分的、有编号但无限制的“寄存器”ー可以包含任何整数的内存 "单元"(参见Elgot和Robinson(1964)，Hartmanis(1971)，特别是Cook-Rechow(1973)；) RASP的有限状态机可以间接寻址(例如，一个寄存器的内容可以用作另一个寄存器的地址) ，因此当图灵机被用作约束运行时间的基础时，可以证明某些算法的运行时间有一个 "假下限"（由于图灵机的假简化假设）。这方面的一个例子是二进制搜索，当使用RASP计算模型而不是图灵机模型时，可以证明这种算法的运行速度更快。

 

Another limitation of Turing machines is that they do not model concurrency well. For example, there is a bound on the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank tape. (See article on [[unbounded nondeterminism]].) By contrast, there are always-halting concurrent systems with no inputs that can compute an integer of unbounded size. (A process can be created with local storage that is initialized with a count of 0 that concurrently sends itself both a stop and a go message. When it receives a go message, it increments its count by 1 and sends itself a go message. When it receives a stop message, it stops with an unbounded number in its local storage.)

Another limitation of Turing machines is that they do not model concurrency well. For example, there is a bound on the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank tape. (See article on [[unbounded nondeterminism]].) By contrast, there are always-halting concurrent systems with no inputs that can compute an integer of unbounded size. (A process can be created with local storage that is initialized with a count of 0 that concurrently sends itself both a stop and a go message. When it receives a go message, it increments its count by 1 and sends itself a go message. When it receives a stop message, it stops with an unbounded number in its local storage.)

Another limitation of Turing machines is that they do not model concurrency well. For example, there is a bound on the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank tape. (See article on unbounded nondeterminism.) By contrast, there are always-halting concurrent systems with no inputs that can compute an integer of unbounded size. (A process can be created with local storage that is initialized with a count of 0 that concurrently sends itself both a stop and a go message. When it receives a go message, it increments its count by 1 and sends itself a go message. When it receives a stop message, it stops with an unbounded number in its local storage.)

图灵机的另一个局限是，它们不能很好地模拟并发。例如，一个始终保持非确定性的图灵机在空白纸带上开始计算的整数大小是有限制的。相比之下，有一些没有输入的始终保持一致的并发系统，可以计算出无界大小的整数。(可以用本地存储创建一个初始化为0的进程，它同时向自己发送一个“停止”和一个“运行”的消息。当它收到一个“运行”信息时，它的计数增加1，并向自己发送一个去信息。当它收到一个“停止”消息时，它就停止，在它的本地存储区有一个无限制的数字)。

In the early days of computing, computer use was typically limited to [[batch processing]], i.e., non-interactive tasks, each producing output data from given input data. Computability theory, which studies computability of functions from inputs to outputs, and for which Turing machines were invented, reflects this practice.

In the early days of computing, computer use was typically limited to [[batch processing]], i.e., non-interactive tasks, each producing output data from given input data. Computability theory, which studies computability of functions from inputs to outputs, and for which Turing machines were invented, reflects this practice.

Since the 1970s, [[interactivity|interactive]] use of computers became much more common.  In principle, it is possible to model this by having an external agent read from the tape and write to it at the same time as a Turing machine, but this rarely matches how interaction actually happens; therefore, when describing interactivity, alternatives such as [[Input/output automaton|I/O automata]] are usually preferred.

Since the 1970s, [[interactivity|interactive]] use of computers became much more common.  In principle, it is possible to model this by having an external agent read from the tape and write to it at the same time as a Turing machine, but this rarely matches how interaction actually happens; therefore, when describing interactivity, alternatives such as [[Input/output automaton|I/O automata]] are usually preferred.

自20世纪70年代以来，计算机的交互式使用变得更加普遍。原则上，可以通过让外部代理与图灵机同时从磁带中读出并写入磁带的方式进行建模，但这很少与交互的实际发生方式相吻合；因此，在描述交互性时，通常首选I/O自动机等替代程序。

自20世纪70年代以来，计算机的交互式使用变得更加普遍。原则上，可以通过让外部代理与图灵机同时从纸带中读出并写入纸带的方式进行建模，但这很少与交互的实际发生方式相吻合；因此，在描述交互性时，通常首选I/O自动机等替代程序。

==History==

==History==