更改

跳到导航 跳到搜索

图灵机 (查看源代码)

2020年10月27日 (二) 22:31的版本

添加50,953字节 、 2020年10月27日 (二) 22:31
小
Moved page from wikipedia:en:Turing machine (history)
第1行： 第1行： −
此词条暂由彩云小译翻译，翻译字数共4149，未经人工整理和审校，带来阅读不便，请见谅。
+
此词条暂由彩云小译翻译，翻译字数共5995，未经人工整理和审校，带来阅读不便，请见谅。
    
{{other uses}}
 
{{other uses}}
第17行： 第17行：  
A '''Turing machine''' is a [[mathematical model of computation]] that defines an [[abstract machine]],<ref>Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.</ref> which manipulates symbols on a strip of tape according to a table of rules.<ref>Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".</ref> Despite the model's simplicity, given any [[computer algorithm]], a Turing machine capable of simulating that algorithm's logic can be constructed.<ref>Sipser 2006:137 "A Turing machine can do everything that a real computer can do".</ref>
 
A '''Turing machine''' is a [[mathematical model of computation]] that defines an [[abstract machine]],<ref>Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.</ref> which manipulates symbols on a strip of tape according to a table of rules.<ref>Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".</ref> Despite the model's simplicity, given any [[computer algorithm]], a Turing machine capable of simulating that algorithm's logic can be constructed.<ref>Sipser 2006:137 "A Turing machine can do everything that a real computer can do".</ref>
   −
A Turing machine is a mathematical model of computation that defines an abstract machine,(Turing state)
+
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
   −
图灵机是一个定义抽象机器(图灵状态)的数学计算模型
+
图灵机是一个数学计算模型，它定义了一个抽象机器，根据一张规则表在一条带子上操纵符号。尽管模型简单，给定任何计算机算法，一个能够模拟算法逻辑的图灵机可以被构造出来。
      −
  −
! Tape symbol
  −
  −
!磁带符号
      
The machine operates on an infinite<ref>Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".</ref> memory tape divided into [[discrete mathematics|discrete]] "cells".<ref>Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.</ref> The machine positions its "head" over a cell and "reads" or "scans"<ref>This word is used by e.g. Davis 2000:151</ref> the symbol there. Then, as per the symbol and the machine's own present state in a "finite table"<ref>This table represents an [[algorithm]] or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.</ref> of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),<ref>Boolos Burgess and Jeffrey 2002:25</ref> then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),<ref>Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.</ref> then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation.<ref>"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in ''The Undecidable'' 1967:119); this notion was added in the 1950s; see more at [[Halting problem]].</ref>
 
The machine operates on an infinite<ref>Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".</ref> memory tape divided into [[discrete mathematics|discrete]] "cells".<ref>Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.</ref> The machine positions its "head" over a cell and "reads" or "scans"<ref>This word is used by e.g. Davis 2000:151</ref> the symbol there. Then, as per the symbol and the machine's own present state in a "finite table"<ref>This table represents an [[algorithm]] or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.</ref> of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),<ref>Boolos Burgess and Jeffrey 2002:25</ref> then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),<ref>Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.</ref> then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation.<ref>"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in ''The Undecidable'' 1967:119); this notion was added in the 1950s; see more at [[Halting problem]].</ref>
   −
! Print-operation
+
The machine operates on an infinite memory tape divided into discrete "cells". The machine positions its "head" over a cell and "reads" or "scans" the symbol there. Then, as per the symbol and the machine's own present state in a "finite table" of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head), then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation.
−
 
  −
!打印操作
  −
 
      +
这台机器在一个无限大的存储磁带上运行，磁带被分割成若干个独立的“单元”。机器将它的“头”定位在一个单元格上，并“读取”或“扫描”那里的符号。然后，根据符号和机器本身在用户指定指令的“有限表”中的现状，机器(i)在单元格中写入一个符号(例如，数字或有限字母表中的一个字母)(有些模型允许擦除符号或不写入) ，然后(ii)将磁带向左或向右移动一个单元格(有些模型不允许运动，有些模型移动头部) ，然后(iii)(根据观察到的符号和机器在表中的自身状态确定)继续执行后续指令或停止计算。
   −
! Tape-motion
     −
!磁带运动
      
The Turing machine was invented in 1936 by [[Alan Turing]],<ref name=Hodges-2012>{{cite book| first=Andrew | last=Hodges | authorlink =Andrew Hodges | year = 2012 | title =Alan Turing: The Enigma |publisher =[[Princeton University Press]] |isbn=978-0-691-15564-7| edition=The Centenary }}</ref><ref>The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by [[M. H. A. Newman]] in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process"which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its ''Proceedings'' (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).</ref> who called it an "a-machine" (automatic machine).<ref>See footnote in Davis 2000:151.</ref> With this model, Turing was able to answer two questions in the negative: (1) does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol.<ref>Turing 1936 in ''The Undecidable'' 1965:132-134; Turing's definition of "circular" is found on page 119.</ref><ref>{{cite journal | url=http://plms.oxfordjournals.org/content/s2-42/1.toc | first=Alan Mathison |last=Turing | title=On Computable Numbers, with an Application to the Entscheidungsproblem | journal=Proceedings of the London Mathematical Society, Series 2 | volume=42 | number=1 | pages=230–265 | year=1937 | doi=10.1112/plms/s2-42.1.230 }} — Reprint at: {{cite web
 
The Turing machine was invented in 1936 by [[Alan Turing]],<ref name=Hodges-2012>{{cite book| first=Andrew | last=Hodges | authorlink =Andrew Hodges | year = 2012 | title =Alan Turing: The Enigma |publisher =[[Princeton University Press]] |isbn=978-0-691-15564-7| edition=The Centenary }}</ref><ref>The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by [[M. H. A. Newman]] in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process"which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its ''Proceedings'' (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).</ref> who called it an "a-machine" (automatic machine).<ref>See footnote in Davis 2000:151.</ref> With this model, Turing was able to answer two questions in the negative: (1) does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol.<ref>Turing 1936 in ''The Undecidable'' 1965:132-134; Turing's definition of "circular" is found on page 119.</ref><ref>{{cite journal | url=http://plms.oxfordjournals.org/content/s2-42/1.toc | first=Alan Mathison |last=Turing | title=On Computable Numbers, with an Application to the Entscheidungsproblem | journal=Proceedings of the London Mathematical Society, Series 2 | volume=42 | number=1 | pages=230–265 | year=1937 | doi=10.1112/plms/s2-42.1.230 }} — Reprint at: {{cite web
   −
! Final m-configuration<br />(Turing state)
+
The Turing machine was invented in 1936 by Alan Turing, who called it an "a-machine" (automatic machine). With this model, Turing was able to answer two questions in the negative: (1) does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol. Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the Entscheidungsproblem ('decision problem').
   −
!最终 m 配置 < br/> (图灵状态)
+
图灵机是1936年阿兰 · 图灵发明的，他称之为“自动机器”。通过这个模型，图灵能够回答两个否定的问题: (1)是否存在一台机器，可以确定其磁带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ; 同样地，(2)是否存在一台机器，可以确定其磁带上的任意机器是否曾打印给定的符号。因此，通过对一个可以任意计算的非常简单的装置进行数学描述，他能够证明计算的一般性质，特别是可判定性的不可计算性(“决策问题”)。
    
|url=http://www.turingarchive.org/viewer/?id=466&title=01e|accessdate=9 July 2020|first=Alan |last=Turing |title=On computable numbers, with an application to the Entscheidungsproblem|website=The Turing Digital Archive }}</ref> Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the [[computability|uncomputability]] of the ''[[Entscheidungsproblem]]'' ('decision problem').<ref>Turing 1936 in ''The Undecidable'' 1965:145</ref>
 
|url=http://www.turingarchive.org/viewer/?id=466&title=01e|accessdate=9 July 2020|first=Alan |last=Turing |title=On computable numbers, with an application to the Entscheidungsproblem|website=The Turing Digital Archive }}</ref> Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the [[computability|uncomputability]] of the ''[[Entscheidungsproblem]]'' ('decision problem').<ref>Turing 1936 in ''The Undecidable'' 1965:145</ref>
   −
! 5-tuple
     −
!五元组
      +
Turing machines proved the existence of fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory.
    +
图灵机证明了机械计算能力的基本限制的存在。虽然它们可以表达任意的计算，但是它们的最小化设计使得它们在实践中不适合计算: 现实世界的计算机是基于不同的设计，不像图灵机，使用随机存取存储器。
   −
! 5-tuple comments
+
Turing machines proved the existence of fundamental limitations on the power of mechanical computation.<ref>Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."</ref> While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world [[computer]]s are based on different designs that, unlike Turing machines, use [[random-access memory]].
   −
!5-tuple 注释
     −
Turing machines proved the existence of fundamental limitations on the power of mechanical computation.<ref>Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."</ref> While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world [[computer]]s are based on different designs that, unlike Turing machines, use [[random-access memory]].
     −
! 4-tuple
+
Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored.
   −
!四元组
+
图灵完备性是指令系统模拟图灵机的能力。图灵完备的编程语言理论上能够表达计算机完成的所有任务; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。
    +
[[Turing completeness]] is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored.
      −
|-
     −
|-
+
==Overview==
   −
[[Turing completeness]] is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored.
+
A Turing machine is a general example of a central processing unit (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine (automaton) capable of enumerating some arbitrary subset of valid strings of an alphabet; these strings are part of a recursively enumerable set. A Turing machine has a tape of infinite length on which it can perform read and write operations.
   −
| N1
+
图灵机是中央处理器(CPU)的一个通用例子，它控制计算机进行的所有数据操作，规范机器使用顺序存储器存储数据。更具体地说，它是一台机器(自动机) ，能够枚举字母表中有效字符串的任意子集; 这些字符串是字母递归可枚举集合的一部分。图灵机有一个无限长的磁带，它可以在其上执行读写操作。
   −
| n 1
+
A Turing machine is a general example of a [[central processing unit]] (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine ([[automaton]]) capable of [[enumeration|enumerating]] some arbitrary subset of valid strings of an [[Alphabet (formal languages)|alphabet]]; these strings are part of a [[recursively enumerable set]]. A Turing machine has a tape of infinite length on which it can perform read and write operations.
         −
| q<sub>i</sub>
+
Assuming a black box, the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program. This is due to the fact that the halting problem is unsolvable, which has major implications for the theoretical limits of computing.
   −
| q < sub > i </sub >
+
假设是一个黑盒，图灵机不能知道它最终是否会枚举给定程序的子集的任何一个特定字符串。这是因为停机问题是不可解的，这对计算的理论极限有重大的影响。
   −
==Overview==
+
Assuming a [[black box]], the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program. This is due to the fact that the [[halting problem]] is unsolvable, which has major implications for the theoretical limits of computing.
   −
| S<sub>j</sub>
     −
| s < sub > j </sub >
     −
A Turing machine is a general example of a [[central processing unit]] (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine ([[automaton]]) capable of [[enumeration|enumerating]] some arbitrary subset of valid strings of an [[Alphabet (formal languages)|alphabet]]; these strings are part of a [[recursively enumerable set]]. A Turing machine has a tape of infinite length on which it can perform read and write operations.
+
The Turing machine is capable of processing an unrestricted grammar, which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through lambda calculus.
   −
| Print(S<sub>k</sub>)
+
图灵机能够处理无限制文法，这进一步意味着它能够以无限的方式对一阶逻辑进行稳健的评估。这一点通过 lambda 演算得到了著名的证明。
   −
| 列印(s < sub > k </sub >)
+
The Turing machine is capable of processing an [[unrestricted grammar]], which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through [[lambda calculus]].
         −
| Left L
+
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, and provide a precise definition of an algorithm or "mechanical procedure". Studying their  abstract properties yields many insights into computer science and complexity theory.
   −
左 l
+
能够模拟任何其他图灵机的图灵机被称为图灵通用图灵机(UTM，或者简单地称为通用机器)。阿隆佐 · 丘奇提出了一个更加以数学为导向的定义，具有类似的“普遍性”。丘奇在一个被称为丘奇-图灵论文的正式计算理论中，将关于 λ 微积分的工作与图灵的工作相互交织。论文指出，图灵机确实捕获了逻辑和数学中有效方法的非正式概念，并提供了一个算法或“机械过程”的精确定义。研究它们的抽象性质可以使我们对计算机科学和复杂性理论有更深入的了解。
   −
Assuming a [[black box]], the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program. This is due to the fact that the [[halting problem]] is unsolvable, which has major implications for the theoretical limits of computing.
+
A Turing machine that is able to simulate any other Turing machine is called a [[universal Turing machine]] (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by [[Alonzo Church]], whose work on lambda calculus intertwined with Turing's in a formal theory of [[computation]] known as the [[Church–Turing thesis]]. The thesis states that Turing machines indeed capture the informal notion of [[effective method]]s in [[logic]] and [[mathematics]], and provide a precise definition of an [[algorithm]] or "mechanical procedure". Studying their  [[abstract machine|abstract properties]] yields many insights into [[computer science]] and [[computational complexity theory|complexity theory]].
   −
| q<sub>m</sub>
     −
| q < sub > m </sub >
      +
===Physical description===
    +
In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, L, q<sub>m</sub>)
+
在他1948年的论文《智能机器》中，图灵写道他的机器包括:
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，l，q < sub > m </sub >)
+
In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:
   −
The Turing machine is capable of processing an [[unrestricted grammar]], which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through [[lambda calculus]].
     −
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
     −
| “空白” = s < sub > 0 </sub > ，1 = s < sub > 1 </sub > 等。
+
{{quote|...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.<ref>See the definition of "[[wikt:innings|innings]]" on [[Wiktionary]]</ref>|Turing 1948, p. 3<ref>
    +
{{cite web
    +
| title=Intelligent Machinery (manuscript)
   −
|
+
| author=A.M. Turing
   −
|
+
| year=1948
   −
A Turing machine that is able to simulate any other Turing machine is called a [[universal Turing machine]] (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by [[Alonzo Church]], whose work on lambda calculus intertwined with Turing's in a formal theory of [[computation]] known as the [[Church–Turing thesis]]. The thesis states that Turing machines indeed capture the informal notion of [[effective method]]s in [[logic]] and [[mathematics]], and provide a precise definition of an [[algorithm]] or "mechanical procedure". Studying their  [[abstract machine|abstract properties]] yields many insights into [[computer science]] and [[computational complexity theory|complexity theory]].
+
The Turing machine mathematically models a machine that mechanically operates on a tape.  On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article ("On Computable Numbers, with an Application to the Entscheidungsproblem", see also references below), Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly (or as Turing puts it, "in a desultory manner").
   −
|-
+
图灵机对机械操作磁带的机器进行数学建模。这个磁带上有符号，机器可以用磁头读写，一次一个。操作完全由一组有限的基本指令决定，如“在状态42中，如果看到的符号是0，写一个1; 如果看到的符号是1，改为状态17; 在状态17中，如果看到的符号是0，写一个1，改为状态6; ”等等。在最初的文章中(“关于可计算数字，以及对可判定性的应用” ，见下面的参考文献) ，图灵想象的不是一种机制，而是一个他称之为“计算机”的人，他奴隶般地执行这些确定性的机械规则(或者如图灵所说，“以一种杂乱无章的方式”)。
   −
|-
+
| page=3
    +
| url=http://www.alanturing.net/Turing_archive/archive/l/l32/L32-004.html
    +
The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed (q<sub>4</sub>) is shown over the scanned square. (Drawing after Kleene (1952) p. 375.)
   −
| N2
+
磁头始终位于磁带的某个方格上，只显示有限的方格拉伸。将要执行的指令(q < sub > 4 </sub >)显示在扫描的正方形上。(Kleene (1952) p.375.)
   −
2
+
| publisher=The Turing Archive
   −
===Physical description===
+
}}
   −
| q<sub>i</sub>
+
Here, the internal state (q<sub>1</sub>) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its "complete configuration") consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.)
   −
| q < sub > i </sub >  
+
这里，内部状态(q < sub > 1 </sub >)显示在头部内部，图中描述磁带是无限的，并预填充了“0” ，这个符号是空的。系统的完整状态(其“完整配置”)包括内部状态、磁带上的任何非空白符号(在本例“11B”中) ，以及磁头相对于包括空白符号(即:。「011B 」。(以明斯基(1967) p。121.)
   −
In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:
+
</ref>}}
   −
| S<sub>j</sub>
     −
| s < sub > j </sub >
      +
More explicitly, a Turing machine consists of:
    +
更明确地说，图灵机包括:
   −
| Print(S<sub>k</sub>)
+
==Description==
   −
| 列印(s < sub > k </sub >)
+
{{for|visualizations of Turing machines|Turing machine gallery}}
   −
{{quote|...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.<ref>See the definition of "[[wikt:innings|innings]]" on [[Wiktionary]]</ref>|Turing 1948, p. 3<ref>
     −
| Right R
     −
| 右 r
+
The Turing machine mathematically models a machine that mechanically operates on a tape.  On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article ("[[On Computable Numbers, with an Application to the Entscheidungsproblem]]", see also [[#The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900|references below]]), Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly (or as Turing puts it, "in a desultory manner").
   −
{{cite web
     −
| q<sub>m</sub>
     −
| q < sub > m </sub >  
+
Either erase or write a symbol (replacing a<sub>j</sub> with a<sub>j1</sub>).
   −
| title=Intelligent Machinery (manuscript)
+
擦除或者写一个符号(用 < sub > j1 </sub > 替换 < sub > j </sub >)。
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, R, q<sub>m</sub>)
+
[[File:Turing machine 2a.svg|thumb|right|300px|The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed (q<sub>4</sub>) is shown over the scanned square. (Drawing after Kleene (1952) p. 375.)]]
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，r，q < sub > m </sub >)
+
Move the head (which is described by d<sub>k</sub> and can have values: 'L' for one step left or 'R' for one step right or 'N' for staying in the same place).
   −
| author=A.M. Turing
+
移动头部(由 d < sub > k </sub > 描述，可以有以下值: 向左一步为 l，向右一步为 r，停留在同一位置为 n)。
   −
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
     −
| “空白” = s < sub > 0 </sub > ，1 = s < sub > 1 </sub > 等。
     −
| year=1948
+
Assume the same or a new state as prescribed (go to state q<sub>i1</sub>).
   −
|
+
按照规定假设相同或新的状态(转到状态 q < sub > i1 </sub >)。
   −
|
+
[[File:Turing machine 2b.svg|thumb|right|300px|Here, the internal state (q<sub>1</sub>) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its "complete configuration") consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.)]]
   −
| page=3
+
In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol or (ib) move the head left or right, and then (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled.
   −
|-
+
在四元组模型中，擦除或写入符号(a < sub > j1 </sub >)和向左或向右移动头(d < sub > k </sub >)被指定为单独的指令。表告诉机器擦除或写入一个符号，或者(ib)将头向左或向右移动，然后(ii)按照规定假定相同或新的状态，但不是同一指令中的两个操作(ia)和(ib)。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
   −
|-
     −
| url=http://www.alanturing.net/Turing_archive/archive/l/l32/L32-004.html
     −
| N3
+
More explicitly, a Turing machine consists of:
   −
| N3
+
Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space.
   −
| publisher=The Turing Archive
+
机器的每一部分(即。它的状态、符号集合和在任何给定时间使用过的磁带)和它的行为(如打印、擦除和磁带运动)是有限的、离散的和可区分的，正是无限量的磁带和运行时给了它无限量的存储空间。
   −
| q<sub>i</sub>
+
* A ''tape'' divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, so that the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. In some models the tape has a left end marked with a special symbol; the tape extends or is indefinitely extensible to the right.
   −
| q < sub > i </sub >
+
* A ''head'' that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. In some models the head moves and the tape is stationary.
   −
}}
+
* A ''state register'' that stores the state of the Turing machine, one of finitely many. Among these is the special ''start state'' with which the state register is initialized. These states, writes Turing, replace the "state of mind" a person performing computations would ordinarily be in.
   −
| S<sub>j</sub>
+
Following , a (one-tape) Turing machine can be formally defined as a 7-tuple <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> where
   −
| s < sub > j </sub >  
+
接下来，一个(单带)图灵机可以被正式定义为一个七元组 < math > m = langle q，Gamma，b，Sigma，delta，q _ 0，f rangle </math > 其中
   −
</ref>}}
+
* A finite ''table''<ref>Occasionally called an ''action table'' or ''transition function''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref> that, given the ''state''(q<sub>i</sub>) the machine is currently in ''and'' the ''symbol''(a<sub>j</sub>) it is reading on the tape (symbol currently under the head), tells the machine to do the following ''in sequence'' (for the 5-tuple models):
   −
| Print(S<sub>k</sub>)
+
# Either erase or write a symbol (replacing a<sub>j</sub> with a<sub>j1</sub>).
   −
| 列印(s < sub > k </sub >)
+
# Move the head (which is described by d<sub>k</sub> and can have values: 'L' for one step left ''or'' 'R' for one step right ''or'' 'N' for staying in the same place).
    +
# Assume the same or a ''new state'' as prescribed (go to state q<sub>i1</sub>).
    +
In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol ''or'' (ib) move the head left or right, ''and then'' (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled.
   −
| None N
     −
| None n
     −
==Description==
+
Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is ''finite'', ''discrete'' and ''distinguishable''; it is the unlimited amount of tape and runtime that gives it an unbounded amount of [[Computer storage|storage space]].
   −
| q<sub>m</sub>
     −
| q < sub > m </sub >
     −
{{for|visualizations of Turing machines|Turing machine gallery}}
+
==Formal definition==
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, N, q<sub>m</sub>)
+
When executed, the machine will either halt with some string remaining on the tape, or continue executing forever. If it halts, the final values on the tape are regarded as the output. A variant of the Turing machine has an accept state and a reject state which both halt the machine, and the sole output is which of those states the machine ends up on (or it may never halt). This variant can effectively output a longer string by taking in an integer that tells it which bit of the string to output.
   −
(q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，n，q < sub > m </sub >)
+
执行时，机器要么停止，磁带上还有一些字符串，要么永远继续执行。如果停止，磁带上的最终值被视为输出。图灵机的一个变种有一个接受状态和一个拒绝状态，这两个状态都停止了机器，唯一的输出是机器最终处于哪个状态(或者它可能永远不会停止)。这种变体通过接受一个整数来告诉它输出字符串的哪个位，从而可以有效地输出较长的字符串。
    +
Following {{harvtxt|Hopcroft|Ullman|1979|p=148}}, a (one-tape) Turing machine can be formally defined as a 7-[[tuple]] <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> where
    +
* <math>Q</math> is a finite, non-empty set of ''states'';
   −
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
+
A relatively uncommon variant allows "no shift", say N, as a third element of the set of directions <math>\{L,R\}</math>.
   −
| “空白” = s < sub > 0 </sub > ，1 = s < sub > 1 </sub > ，等等。
+
一个相对不常见的变体允许“ no shift” ，比如 n，作为方向集合{ math > { l，r } </math > 的第三个元素。
   −
The Turing machine mathematically models a machine that mechanically operates on a tape.  On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article ("[[On Computable Numbers, with an Application to the Entscheidungsproblem]]", see also [[#The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900|references below]]), Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly (or as Turing puts it, "in a desultory manner").
+
* <math>\Gamma</math> is a finite, non-empty set of ''tape alphabet symbols'';
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, q<sub>m</sub>)
+
* <math>b \in \Gamma</math> is the ''blank symbol'' (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
   −
(q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，q < sub > m </sub >)
+
The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):
    +
三态繁忙海狸的七元组看起来像这样(更多关于这个繁忙海狸的图灵机例子) :
    +
* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> is the set of ''input symbols'', that is, the set of symbols allowed to appear in the initial tape contents;
   −
|-
+
* <math>q_0 \in Q</math> is the ''initial state'';
   −
|-
+
* <math>F \subseteq Q</math> is the set of ''final states'' or ''accepting states''. The initial tape contents is said to be ''accepted'' by <math>M</math> if it eventually halts in a state from <math>F</math>.
   −
[[File:Turing machine 2a.svg|thumb|right|300px|The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed (q<sub>4</sub>) is shown over the scanned square. (Drawing after Kleene (1952) p. 375.)]]
+
* <math>\delta: (Q \setminus F) \times \Gamma \not\to Q \times \Gamma \times \{L,R\}</math> is a [[partial function]] called the ''[[State transition system|transition function]]'', where L is left shift, R is right shift. If <math>\delta</math> is not defined on the current state and the current tape symbol, then the machine halts;<ref>p.149; in particular, Hopcroft and Ullman assume that <math>\delta</math> is undefined on all states from <math>F</math></ref>
   −
| 4
     −
| 4
      +
When executed, the machine will either halt with some string remaining on the tape, or continue executing forever. If it halts, the final values on the tape are regarded as the output. A variant of the Turing machine has an accept state and a reject state which both halt the machine, and the sole output is which of those states the machine ends up on (or it may never halt). This variant can effectively output a longer string by taking in an integer that tells it which bit of the string to output.
      −
| q<sub>i</sub>
     −
| q < sub > i </sub >  
+
A relatively uncommon variant allows "no shift", say N, as a third element of the set of directions <math>\{L,R\}</math>.
   −
[[File:Turing machine 2b.svg|thumb|right|300px|Here, the internal state (q<sub>1</sub>) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its "complete configuration") consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.)]]
     −
| S<sub>j</sub>
     −
| s < sub > j </sub >  
+
Initially all tape cells are marked with <math>0</math>.
    +
最初所有的磁带单元格都用 < math > 0 </math > 标记。
    +
The 7-tuple for the 3-state [[busy beaver]] looks like this (see more about this busy beaver at [[Turing machine examples]]):
   −
| None N
+
* <math>Q = \{ \mbox{A}, \mbox{B}, \mbox{C}, \mbox{HALT} \}</math> (states);
   −
| None n
+
{| class="wikitable" style="text-align:center"
   −
More explicitly, a Turing machine consists of:
+
{ | class = “ wikitable” style = “ text-align: center”
   −
| Left L
+
* <math>\Gamma = \{ 0, 1 \}</math> (tape alphabet symbols);
   −
左 l
+
|+ State table for 3 state, 2 symbol busy beaver
   −
* A ''tape'' divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, so that the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. In some models the tape has a left end marked with a special symbol; the tape extends or is indefinitely extensible to the right.
+
| + 3个状态的状态表，2个符号忙碌的海狸
   −
| q<sub>m</sub>
+
* <math>b = 0</math> (blank symbol);
   −
| q < sub > m </sub >
+
! rowspan="2" | Tape symbol
   −
* A ''head'' that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. In some models the head moves and the tape is stationary.
+
!Rowspan = “2” | 磁带符号
   −
| (q<sub>i</sub>, S<sub>j</sub>, N, L, q<sub>m</sub>)
+
* <math>\Sigma = \{ 1 \}</math> (input symbols);
   −
(q < sub > i </sub > ，s < sub > j </sub > ，n，l，q < sub > m </sub >)
+
! colspan="3" | Current state A
   −
* A ''state register'' that stores the state of the Turing machine, one of finitely many. Among these is the special ''start state'' with which the state register is initialized. These states, writes Turing, replace the "state of mind" a person performing computations would ordinarily be in.
+
!Colspan = “3” | 当前状态 a
   −
|
+
* <math>q_0 = \mbox{A}</math> (initial state);
   −
|
+
! colspan="3" | Current state B
   −
* A finite ''table''<ref>Occasionally called an ''action table'' or ''transition function''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref> that, given the ''state''(q<sub>i</sub>) the machine is currently in ''and'' the ''symbol''(a<sub>j</sub>) it is reading on the tape (symbol currently under the head), tells the machine to do the following ''in sequence'' (for the 5-tuple models):
+
!Colspan = “3” | 当前状态 b
   −
| (q<sub>i</sub>, S<sub>j</sub>, L, q<sub>m</sub>)
+
* <math>F = \{ \mbox{HALT} \}</math> (final states);
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，l，q < sub > m </sub >)
+
! colspan="3" | Current state C
   −
# Either erase or write a symbol (replacing a<sub>j</sub> with a<sub>j1</sub>).
+
!Colspan = “3” | 当前状态 c
   −
|-
+
* <math>\delta = </math> see state-table below (transition function).
   −
|-
+
|- style="font-size:9pt"
   −
# Move the head (which is described by d<sub>k</sub> and can have values: 'L' for one step left ''or'' 'R' for one step right ''or'' 'N' for staying in the same place).
+
|-style = “ font-size: 9 pt”
   −
| 5
     −
| 5
     −
# Assume the same or a ''new state'' as prescribed (go to state q<sub>i1</sub>).
+
| Write symbol
   −
| q<sub>i</sub>
+
| 写符号
   −
| q < sub > i </sub >  
+
Initially all tape cells are marked with <math>0</math>.
   −
In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol ''or'' (ib) move the head left or right, ''and then'' (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled.
+
| Move tape
   −
| S<sub>j</sub>
+
移动磁带
   −
| s < sub > j </sub >
         +
| Next state
   −
| None N
+
下一个州
   −
| None n
+
{| class="wikitable" style="text-align:center"
   −
Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is ''finite'', ''discrete'' and ''distinguishable''; it is the unlimited amount of tape and runtime that gives it an unbounded amount of [[Computer storage|storage space]].
+
| Write symbol
   −
| Right R
+
| 写入符号
   −
| 右 r
+
|+ State table for 3 state, 2 symbol busy beaver
    +
| Move tape
    +
移动磁带
 +
 +
! rowspan="2" | Tape symbol
   −
| q<sub>m</sub>
+
| Next state
   −
| q < sub > m </sub >
+
下一个州
   −
==Formal definition==
+
! colspan="3" | Current state A
   −
| (q<sub>i</sub>, S<sub>j</sub>, N, R, q<sub>m</sub>)
+
| Write symbol
   −
(q < sub > i </sub > ，s < sub > j </sub > ，n，r，q < sub > m </sub >)
+
| 写入符号
   −
Following {{harvtxt|Hopcroft|Ullman|1979|p=148}}, a (one-tape) Turing machine can be formally defined as a 7-[[tuple]] <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> where
+
! colspan="3" | Current state B
   −
|
+
| Move tape
   −
|
+
移动磁带
   −
* <math>Q</math> is a finite, non-empty set of ''states'';
+
! colspan="3" | Current state C
   −
| (q<sub>i</sub>, S<sub>j</sub>, R, q<sub>m</sub>)
+
| Next state
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，r，q < sub > m </sub >)
+
下一个州
   −
* <math>\Gamma</math> is a finite, non-empty set of ''tape alphabet symbols'';
+
|- style="font-size:9pt"
    
|-
 
|-
第369行： 第353行：  
|-
 
|-
   −
* <math>b \in \Gamma</math> is the ''blank symbol'' (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
+
| Write symbol
   −
| 6
+
| 0
   −
| 6
+
| 0
   −
* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> is the set of ''input symbols'', that is, the set of symbols allowed to appear in the initial tape contents;
+
| Move tape
   −
| q<sub>i</sub>
+
| 1
   −
| q < sub > i </sub >
+
| 1
   −
* <math>q_0 \in Q</math> is the ''initial state'';
+
| Next state
   −
| S<sub>j</sub>
+
| R
   −
| s < sub > j </sub >
+
| r
   −
* <math>F \subseteq Q</math> is the set of ''final states'' or ''accepting states''. The initial tape contents is said to be ''accepted'' by <math>M</math> if it eventually halts in a state from <math>F</math>.
+
| Write symbol
   −
| None N
+
| B
   −
| None n
+
| b
   −
* <math>\delta: (Q \setminus F) \times \Gamma \not\to Q \times \Gamma \times \{L,R\}</math> is a [[partial function]] called the ''[[State transition system|transition function]]'', where L is left shift, R is right shift. If <math>\delta</math> is not defined on the current state and the current tape symbol, then the machine halts;<ref>p.149; in particular, Hopcroft and Ullman assume that <math>\delta</math> is undefined on all states from <math>F</math></ref>
+
| Move tape
   −
| None N
+
| 1
   −
| None n
+
| 1
    +
| Next state
    +
| L
   −
| q<sub>m</sub>
+
| l
   −
| q < sub > m </sub >
+
| Write symbol
   −
A relatively uncommon variant allows "no shift", say N, as a third element of the set of directions <math>\{L,R\}</math>.
+
| A
 +
 
 +
我会的
   −
| (q<sub>i</sub>, S<sub>j</sub>, N, N, q<sub>m</sub>)
+
| Move tape
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，n，q < sub > m </sub >)
+
| 1
    +
| 1
    +
| Next state
   −
| Direct "jump"
+
| L
   −
| 直接“跳”
+
| l
   −
The 7-tuple for the 3-state [[busy beaver]] looks like this (see more about this busy beaver at [[Turing machine examples]]):
+
|-
   −
| (q<sub>i</sub>, S<sub>j</sub>, N, q<sub>m</sub>)
+
| B
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，n，q < sub > m </sub >)
+
| b
   −
* <math>Q = \{ \mbox{A}, \mbox{B}, \mbox{C}, \mbox{HALT} \}</math> (states);
+
| 0
    
|-
 
|-
第429行： 第419行：  
|-
 
|-
   −
* <math>\Gamma = \{ 0, 1 \}</math> (tape alphabet symbols);
+
| 1
   −
| 7
+
| 1
   −
| 7
+
| 1
   −
* <math>b = 0</math> (blank symbol);
+
| R
   −
| q<sub>i</sub>
+
| 1
   −
| q < sub > i </sub >
+
| 1
   −
* <math>\Sigma = \{ 1 \}</math> (input symbols);
+
| '''B'''
   −
| S<sub>j</sub>
+
| L
   −
| s < sub > j </sub >
+
| l
   −
* <math>q_0 = \mbox{A}</math> (initial state);
+
| 1
   −
| Erase
+
| C
   −
擦除
+
| c
   −
* <math>F = \{ \mbox{HALT} \}</math> (final states);
+
| L
   −
| Left L
+
| 1
   −
左 l
+
| 1
   −
* <math>\delta = </math> see state-table below (transition function).
+
| '''A'''
   −
| q<sub>m</sub>
+
| R
   −
| q < sub > m </sub >
+
| r
    +
| 1
    +
| B
   −
| (q<sub>i</sub>, S<sub>j</sub>, E, L, q<sub>m</sub>)
+
| b
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，e，l，q < sub > m </sub >)
+
| L
   −
Initially all tape cells are marked with <math>0</math>.
+
| 1
   −
|
+
| 1
   −
|
+
| '''B'''
    +
| R
    +
| r
   −
|
+
|-
   −
|
+
| HALT
   −
{| class="wikitable" style="text-align:center"
+
| HALT
   −
|-
+
| 1
   −
|-
+
|}
   −
|+ State table for 3 state, 2 symbol busy beaver
+
|}
   −
| 8
+
| 1
   −
| 8
+
| L
   −
! rowspan="2" | Tape symbol
+
| '''C'''
   −
| q<sub>i</sub>
+
In the words of van Emde Boas (1990), p.&nbsp;6: "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like."
   −
| q < sub > i </sub >
+
用 van Emde Boas (1990)的话来说，第6页: “集合理论对象(类似于上面的形式七元组描述)只提供了关于机器如何运行以及它的计算将是什么样子的部分信息。”
   −
! colspan="3" | Current state A
+
| 1
   −
| S<sub>j</sub>
+
| R
   −
| s < sub > j </sub >
+
For instance,
   −
! colspan="3" | Current state B
+
比如说,
   −
| Erase
+
| '''B'''
   −
擦除
+
| 1
   −
! colspan="3" | Current state C
+
| R
   −
| Right R
+
| '''HALT'''
   −
| 右 r
+
|}
   −
|- style="font-size:9pt"
     −
| q<sub>m</sub>
     −
| q < sub > m </sub >  
+
Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, the set could be changed from <math>\{L,R\}</math> to <math>\{L,R,N\}</math>, where N ("None" or "No-operation") would allow the machine to stay on the same tape cell instead of moving left or right. This would not increase the machine's computational power.
   −
| Write symbol
+
文献中的定义有时略有不同，以使论证或证明更容易或更清楚，但这总是以这样的方式进行，得到的机器有相同的计算能力。例如，集合可以从 < math > { l，r } </math > 更改为 < math > { l，r，n } </math > ，其中 n (“ None”或“ No-operation”)将允许机器保持在同一磁带单元上，而不是向左或向右移动。这不会增加机器的计算能力。
   −
| (q<sub>i</sub>, S<sub>j</sub>, E, R, q<sub>m</sub>)
+
==Additional details required to visualize or implement Turing machines==
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，e，r，q < sub > m </sub >)
+
In the words of van Emde Boas (1990), p.&nbsp;6: "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like."
   −
| Move tape
+
The most common convention represents each "Turing instruction" in a "Turing table" by one of nine 5-tuples, per the convention of Turing/Davis (Turing (1936) in The Undecidable, p.&nbsp;126-127 and Davis (2000) p.&nbsp;152):
   −
|
+
根据图灵/戴维斯(图灵(1936)在《无法判定》中的约定，第126-127页和戴维斯(2000)第152页，最常见的约定表示“图灵表”中的每个“图灵指令”由9个5元组中的一个组成:
   −
|
     −
| Next state
     −
|
+
For instance,
   −
|
+
(definition 1): (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)
   −
| Write symbol
+
(定义1) : (q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub >/E/N，L/R/N，q < sub > m </sub >)
   −
|-
+
* There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and writing symbols indefinitely.
   −
|-
+
( current state q<sub>i</sub> , symbol scanned S<sub>j</sub> , print symbol S<sub>k</sub>/erase E/none N , move_tape_one_square left L/right R/none N , new state q<sub>m</sub> )
   −
| Move tape
+
(当前状态 q < sub > i </sub > ，符号扫描 s < sub > j </sub > ，打印符号 s < sub > k </sub >/erase E/none n，move _ tape one square left L/right R/none n，新状态 q < sub > m </sub >)
   −
| 9
+
* The shift left and shift right operations may shift the tape head across the tape, but when actually building a Turing machine it is more practical to make the tape slide back and forth under the head instead.
   −
| 9
+
* The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition), but it is more common to think of it as stretching infinitely at one or both ends and being pre-filled with blanks except on the explicitly given finite fragment the tape head is on.  (This is, of course, not implementable in practice.)  The tape ''cannot'' be fixed in length, since that would not correspond to the given definition and would seriously limit the range of computations the machine can perform to those of a [[linear bounded automaton]] if the tape was proportional to the input size, or [[finite state machine]] if it was strictly fixed-length.
   −
| Next state
+
Other authors (Minsky (1967) p.&nbsp;119, Hopcroft and Ullman (1979) p.&nbsp;158, Stone (1972) p.&nbsp;9) adopt a different convention, with new state q<sub>m</sub> listed immediately after the scanned symbol S<sub>j</sub>:
   −
| q<sub>i</sub>
+
其他作者(明斯基(1967)第119页，霍普克罗夫特和乌尔曼(1979)第158页，斯通(1972)第9页)采用了不同的约定，新状态 q </sub > m </sub > 列出后立即扫描符号 s </sub > j </sub > :
   −
| q < sub > i </sub >
     −
| Write symbol
     −
| S<sub>j</sub>
+
(definition 2): (q<sub>i</sub>, S<sub>j</sub>, q<sub>m</sub>, S<sub>k</sub>/E/N, L/R/N)
   −
| s < sub > j </sub >  
+
(定义2) : (q < sub > i </sub > ，s < sub > j </sub > ，q < sub > m </sub > ，s < sub > k </sub >/E/N，L/R/N)
   −
| Move tape
+
===Alternative definitions===
   −
| Erase
+
( current state q<sub>i</sub> , symbol scanned S<sub>j</sub> , new state q<sub>m</sub> , print symbol S<sub>k</sub>/erase E/none N , move_tape_one_square left L/right R/none N )
   −
擦除
+
(当前状态 q < sub > i </sub > ，符号扫描 s < sub > j </sub > ，新状态 q < sub > m </sub > ，打印符号 s < sub > k </sub >/erase E/none n，move _ tape one _ square left L/right R/none n)
   −
| Next state
+
Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, the set could be changed from <math>\{L,R\}</math> to <math>\{L,R,N\}</math>, where ''N'' ("None" or "No-operation") would allow the machine to stay on the same tape cell instead of moving left or right. This would not increase the machine's computational power.
   −
| None N
     −
| None n
     −
|-
+
For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.
   −
| q<sub>m</sub>
+
本文的其余部分将使用“定义1”(图灵/戴维斯约定)。
   −
| q < sub > m </sub >
+
The most common convention represents each "Turing instruction" in a "Turing table" by one of nine 5-tuples, per the convention of Turing/Davis (Turing (1936) in ''The Undecidable'', p.&nbsp;126-127 and Davis (2000) p.&nbsp;152):
   −
| 0
     −
| (q<sub>i</sub>, S<sub>j</sub>, E, N, q<sub>m</sub>)
     −
| (q < sub > i </sub > ，s < sub > j </sub > ，e，n，q < sub > m </sub >)
+
{| class="wikitable" style="text-align: center"
   −
| 1
+
{ | class = “ wikitable” style = “ text-align: center”
   −
|
+
: (definition 1): '''(q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)'''
   −
|
+
|+ Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples
   −
| R
+
| + 示例: 将3状态2符号忙海狸的状态表减少为5元组
   −
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
+
:: '''(''' current state '''q<sub>i</sub>''' ''',''' symbol scanned '''S<sub>j</sub>''' ''',''' print symbol '''S<sub>k</sub>'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''',''' new state '''q<sub>m</sub>''' ''')'''
   −
| (q < sub > i </sub > ，s < sub > j </sub > ，e，q < sub > m </sub >)
+
! Current state
   −
| '''B'''
+
!当前状态
   −
|}
     −
|}
     −
| 1
+
! Scanned symbol
   −
| L
+
!扫描的符号
   −
Any Turing table (list of instructions) can be constructed from the above nine 5-tuples. For technical reasons, the three non-printing or "N" instructions (4, 5, 6) can usually be dispensed with. For examples see Turing machine examples.
+
Other authors (Minsky (1967) p.&nbsp;119, Hopcroft and Ullman (1979) p.&nbsp;158, Stone (1972) p.&nbsp;9) adopt a different convention, with new state '''q<sub>m</sub>''' listed immediately after the scanned symbol S<sub>j</sub>:
   −
任何 Turing 表(指令列表)都可以由上面的9个5元组构成。由于技术原因，三个非打印或“ n”指令(4,5,6)通常可以省略。有关例子，请参阅图灵机示例。
+
!
   −
| '''A'''
+
!
   −
| 1
+
: (definition 2): '''(q<sub>i</sub>, S<sub>j</sub>, q<sub>m</sub>, S<sub>k</sub>/E/N, L/R/N)'''
   −
Less frequently the use of 4-tuples are encountered: these represent a further atomization of the Turing instructions (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); also see more at Post–Turing machine.
+
! Print symbol
   −
遇到4元组使用的频率较低: 这些代表了图灵指令的进一步原子化(参见。Post (1947) ，Boolos & Jeffrey (1974,1999) ，Davis-Sigal-Weyuker (1994) ;.
+
!打印符号
   −
| L
+
:: '''(''' current state '''q<sub>i</sub>''' ''',''' symbol scanned '''S<sub>j</sub>''' ''',''' new state '''q<sub>m</sub>''' ''',''' print symbol '''S<sub>k</sub>'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''')'''
   −
| '''B'''
+
! Move tape
   −
|-
+
!移动磁带
   −
The word "state" used in context of Turing machines can be a source of confusion, as it can mean two things. Most commentators after Turing have used "state" to mean the name/designator of the current instruction to be performed—i.e. the contents of the state register. But Turing (1936) made a strong distinction between a record of what he called the machine's "m-configuration", and the machine's (or person's) "state of progress" through the computation - the current state of the total system. What Turing called "the state formula" includes both the current instruction and all the symbols on the tape:
     −
在图灵机上下文中使用的“状态”这个词可能会引起混淆，因为它可能意味着两件事。图灵之后的大多数评论员都使用“ state”来表示当前要执行的指令的名称/指示器ーー即。国家登记册的内容。但是图灵(1936)在他所谓的机器“ m 配置”的记录和机器(或个人)通过计算的“进展状态”——整个系统的当前状态——之间做出了很大的区别。图灵所说的“状态公式”包括当前指令和磁带上的所有符号:
     −
| 1
+
! Final (i.e. next) state
   −
| 1
+
!最终决定(即。下一步)状态
   −
| L
+
For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.
   −
| '''C'''
+
! 5-tuples
   −
Earlier in his paper Turing carried this even further: he gives an example where he placed a symbol of the current "m-configuration"—the instruction's label—beneath the scanned square, together with all the symbols on the tape (The Undecidable, p.&nbsp;121); this he calls "the complete configuration" (The Undecidable, p.&nbsp;118). To print the "complete configuration" on one line, he places the state-label/m-configuration to the left of the scanned symbol.
+
!5元组
   −
在论文的前面，图灵进一步阐述了这个观点: 他举了一个例子，他把当前“ m 配置”(指令的标签)的一个符号和磁带上的所有符号(无法判定，第121页)放在了扫描的正方形下面，他称之为“完整配置”(无法判定，第118页)。为了在一行上打印“完整配置” ，他将 state-label/m-configuration 放在扫描符号的左侧。
     −
| 1
     −
| R
+
|-
   −
A variant of this is seen in Kleene (1952) where Kleene shows how to write the Gödel number of a machine's "situation": he places the "m-configuration" symbol q<sub>4</sub> over the scanned square in roughly the center of the 6 non-blank squares on the tape (see the Turing-tape figure in this article) and puts it to the right of the scanned square. But Kleene refers to "q<sub>4</sub>" itself as "the machine state" (Kleene, p.&nbsp;374-375). Hopcroft and Ullman call this composite the "instantaneous description" and follow the Turing convention of putting the "current state" (instruction-label, m-configuration) to the left of the scanned symbol (p.&nbsp;149).
+
|-
   −
在 Kleene (1952年) ，Kleene 展示了如何写出机器“状态”的哥德尔数: 他将“ m 配置”符号 q < sub > 4 </sub > 放置在磁带上6个非空白方块的中心，并将其放置在被扫描方块的右侧。但 Kleene 将“ q < sub > 4 </sub > ”本身称为“机器状态”(Kleene，p. 374-375)。霍普克罗夫特和乌尔曼称这种组合为“瞬时描述” ，并遵循图灵约定，将“当前状态”(指令-标签，m-配置)放在扫描符号的左侧(第149页)。
+
{| class="wikitable" style="text-align: center"
   −
| '''B'''
+
| A
   −
| 1
+
我会的
   −
Example: total state of 3-state 2-symbol busy beaver after 3 "moves" (taken from example "run" in the figure below):
+
|+ Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples
   −
例如: 3个状态2个符号的忙碌海狸在3个“ move”之后的总状态(取自下图中的“ run”示例) :
+
| 0
   −
| R
+
| 0
   −
1A1
+
! Current state
   −
1A1
+
|
   −
| '''HALT'''
+
|
   −
This means: after three moves the tape has ... 000110000 ... on it, the head is scanning the right-most 1, and the state is A. Blanks (in this case represented by "0"s) can be part of the total state as shown here: B01; the tape has a single 1 on it, but the head is scanning the 0 ("blank") to its left and the state is B.
+
! Scanned symbol
   −
这意味着: 三步之后，磁带有... 000110000... 在它上面，磁头正在扫描最右边的1，状态是 a。空格(在这里用“0”表示)可以是总状态的一部分，如下所示: B01; 磁带上有一个单独的1，但磁头正在扫描其左边的0(“空白”) ，状态是 b。
+
| 1
   −
|}
+
| 1
    +
!
    +
| R
   −
"State" in the context of Turing machines should be clarified as to which is being described: (i) the current instruction, or (ii) the list of symbols on the tape together with the current instruction, or (iii) the list of symbols on the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned symbol.
+
| r
   −
图灵机上下文中的”状态”应当澄清: (i)当前指令，或者(ii)磁带上的符号列表连同当前指令，或者(iii)磁带上的符号列表连同扫描符号左侧或扫描符号右侧的当前指令。
+
! Print symbol
   −
==Additional details required to visualize or implement Turing machines==
+
| B
   −
In the words of van Emde Boas (1990), p.&nbsp;6: "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like."
+
| b
   −
Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.
+
! Move tape
   −
图灵的传记作者安德鲁 · 霍奇斯(1983:107)注意到并讨论了这种混淆。
+
| (A, 0, 1, R, B)
    +
| (a，0,1，r，b)
    +
! Final (i.e. next) state
   −
For instance,
+
|-
   −
* There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and writing symbols indefinitely.
+
|-
   −
* The shift left and shift right operations may shift the tape head across the tape, but when actually building a Turing machine it is more practical to make the tape slide back and forth under the head instead.
+
! 5-tuples
   −
{|class="wikitable"
+
| A
   −
{ | class = “ wikitable”
+
我会的
   −
* The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition), but it is more common to think of it as stretching infinitely at one or both ends and being pre-filled with blanks except on the explicitly given finite fragment the tape head is on.  (This is, of course, not implementable in practice.)  The tape ''cannot'' be fixed in length, since that would not correspond to the given definition and would seriously limit the range of computations the machine can perform to those of a [[linear bounded automaton]] if the tape was proportional to the input size, or [[finite state machine]] if it was strictly fixed-length.
+
|-
   −
|+ The table for the 3-state busy beaver ("P" = print/write a "1")
+
| 1
   −
| + 3州繁忙海狸的桌子(“ p” = 打印/写一个“1”)
+
| 1
    +
| '''A'''
    +
|
   −
|-
+
|
   −
|-
+
| 0
   −
===Alternative definitions===
+
| 1
   −
! Tape symbol
+
| 1
   −
!磁带符号
+
|
   −
Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, the set could be changed from <math>\{L,R\}</math> to <math>\{L,R,N\}</math>, where ''N'' ("None" or "No-operation") would allow the machine to stay on the same tape cell instead of moving left or right. This would not increase the machine's computational power.
+
| L
   −
! colspan="3" | Current state A
+
| l
   −
!Colspan = “3” | 当前状态 a
+
| 1
    +
| C
    +
| c
   −
! colspan="3" | Current state B
+
| R
   −
!Colspan = “3” | 当前状态 b
+
| (A, 1, 1, L, C)
   −
The most common convention represents each "Turing instruction" in a "Turing table" by one of nine 5-tuples, per the convention of Turing/Davis (Turing (1936) in ''The Undecidable'', p.&nbsp;126-127 and Davis (2000) p.&nbsp;152):
+
| (a，1,1，l，c)
   −
! colspan="3" | Current state C
+
| '''B'''
 +
 
 +
|-
 +
 
 +
|-
   −
!Colspan = “3” | 当前状态 c
+
| ('''A''', 0, 1, R, '''B''')
    +
| B
    +
| b
    
|-
 
|-
   −
|-
+
| 0
 +
 
 +
| 0
   −
: (definition 1): '''(q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)'''
+
| '''A'''
    
|
 
|
第751行： 第745行：  
|
 
|
   −
:: '''(''' current state '''q<sub>i</sub>''' ''',''' symbol scanned '''S<sub>j</sub>''' ''',''' print symbol '''S<sub>k</sub>'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''',''' new state '''q<sub>m</sub>''' ''')'''
+
| 1
   −
| Write symbol
+
| 1
   −
| 写入符号
+
| 1
    +
|
    +
| L
   −
| Move tape
+
| l
   −
移动磁带
+
| 1
   −
Other authors (Minsky (1967) p.&nbsp;119, Hopcroft and Ullman (1979) p.&nbsp;158, Stone (1972) p.&nbsp;9) adopt a different convention, with new state '''q<sub>m</sub>''' listed immediately after the scanned symbol S<sub>j</sub>:
+
| A
   −
| Next state
+
我会的
   −
下一个州
+
| L
   −
: (definition 2): '''(q<sub>i</sub>, S<sub>j</sub>, q<sub>m</sub>, S<sub>k</sub>/E/N, L/R/N)'''
+
| (B, 0, 1, L, A)
   −
| Write symbol
+
| (b，0,1，l，a)
   −
| 写入符号
+
| '''C'''
   −
:: '''(''' current state '''q<sub>i</sub>''' ''',''' symbol scanned '''S<sub>j</sub>''' ''',''' new state '''q<sub>m</sub>''' ''',''' print symbol '''S<sub>k</sub>'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''')'''
+
|-
   −
| Move tape
+
|-
   −
移动磁带
+
| ('''A''', 1, 1, L, '''C''')
    +
| B
    +
| b
   −
| Next state
+
|-
   −
下一个州
+
| 1
   −
For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.
+
| 1
   −
| Write symbol
+
| '''B'''
   −
| 写入符号
+
|
    +
|
    +
| 0
   −
| Move tape
+
| 1
   −
移动磁带
+
| 1
   −
{| class="wikitable" style="text-align: center"
+
|
   −
| Next state
+
| R
   −
下一个州
+
| r
   −
|+ Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples
+
| 1
   −
|-
+
| B
   −
|-
+
| b
   −
! Current state
+
| L
   −
| 0
+
| (B, 1, 1, R, B)
   −
| 0
+
| (b，1,1，r，b)
   −
! Scanned symbol
+
| '''A'''
   −
| P
+
|-
   −
| p
+
|-
   −
!
+
| ('''B''', 0, 1, L, '''A''')
   −
| R
+
| C
   −
| r
+
| c
   −
! Print symbol
+
|-
   −
| B
+
| 0
   −
| b
+
| 0
 +
 
 +
| '''B'''
 +
 
 +
|
 +
 
 +
|
   −
! Move tape
+
| 1
   −
| P
+
| 1
   −
| p
+
| 1
   −
! Final (i.e. next) state
+
|
    
| L
 
| L
第847行： 第853行：  
| l
 
| l
   −
! 5-tuples
+
| 1
   −
| A
+
| B
   −
我会的
+
| b
   −
|-
+
| R
   −
| P
+
| (C, 0, 1, L, B)
   −
| p
+
| (c，0,1，l，b)
   −
| '''A'''
+
| '''B'''
   −
| L
+
|-
   −
| l
+
|-
 +
 
 +
| ('''B''', 1, 1, R, '''B''')
 +
 
 +
| C
 +
 
 +
| c
 +
 
 +
|-
   −
| 0
+
| 1
   −
| B
+
| 1
   −
| b
+
| '''C'''
    
|
 
|
   −
|-
+
|
   −
|-
+
| 0
    
| 1
 
| 1
第881行： 第895行：  
| 1
 
| 1
   −
| 1
+
|
 +
 
 +
| N
   −
| R
+
| n
   −
| P
+
| 1
   −
| p
+
| H
   −
| '''B'''
+
我们会找到他的
    
| L
 
| L
   −
| l
+
| (C, 1, 1, N, H)
   −
| ('''A''', 0, 1, R, '''B''')
+
| (c，1,1，n，h)
   −
| C
+
| '''B'''
   −
| c
+
|}
   −
|-
+
|}
   −
| P
+
| ('''C''', 0, 1, L, '''B''')
   −
| p
+
|-
   −
| '''A'''
+
In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3 (cf. Turing in The Undecidable, p.&nbsp;126). He allowed for erasure of the "scanned square" by naming a 0th symbol S<sub>0</sub> = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S<sub>k</sub>" or "erase" (cf. footnote 12 in Post (1947), The Undecidable, p.&nbsp;300). The abbreviations are Turing's (The Undecidable, p.&nbsp;119). Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of five-tuples:
   −
| R
+
在下表中，图灵的原始模型只允许前三行，他称之为 N1，N2，N3。图灵在不可判定的，126页)。通过命名第0个符号 s < sub > 0 </sub > = “ erase”或“ blank”等，他允许擦除“扫描的正方形”。然而，他不允许非打印，因此每个指令行包括“打印符号 s < sub > k </sub > ”或“ erase”(参见。后注12(1947) ，无法判定的，第300页)。这些缩写是图灵的(无法判定的，p. 119)。在图灵1936-1937年的原始论文之后，机器模型允许所有九种可能的五元组类型:
   −
| r
+
| '''C'''
    
| 1
 
| 1
   −
| B
+
{| class="wikitable" style="text-align: center"
   −
| b
+
{ | class = “ wikitable” style = “ text-align: center”
    
|
 
|
   −
| P
+
|-
   −
| p
+
|-
    
| 1
 
| 1
   −
| R
+
!
   −
| r
+
!
   −
| L
+
| N
   −
| HALT
+
! Current m-configuration<br />(Turing state)
   −
| HALT
+
!当前 m 配置 < br/> (图灵状态)
   −
| '''C'''
+
| '''H'''
   −
|}
+
! Tape symbol
   −
|}
+
!磁带符号
   −
| ('''A''', 1, 1, L, '''C''')
+
| ('''C''', 1, 1, N, '''H''')
   −
|-
+
! Print-operation
   −
finite state representation. Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state transition is shown by an arrow. The label (e.g. 0/P,R) near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g. 0) followed by a slash /, followed by the subsequent "behaviors" of the machine, e.g. "P Print" then move tape "R Right". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).]]
+
!打印操作
   −
有限状态表示。每个圆圈表示一个表的“状态”ーー一个“ m 配置”或“指令”。状态转换的“方向”用箭头表示。标签(例如:。0/P，r)指定导致特定转换的扫描符号(例如:。0)后跟斜线/，后跟机器的后续“行为” ，例如:。“ p 打印”然后移动磁带“ r 右”。没有普遍接受的格式存在。这个展览是在麦克卢斯基(1965) ，布斯(1967) ，希尔和彼得森(1974)之后展出的
+
|}
   −
| '''B'''
+
! Tape-motion
   −
| 0
+
!磁带运动
   −
To the right: the above table as expressed as a "state transition" diagram.
     −
向右: 以上表格用“状态转换”图表示。
     −
|
+
! Final m-configuration<br />(Turing state)
   −
| 1
+
!最终 m 配置 < br/> (图灵状态)
   −
Usually large tables are better left as tables (Booth, p.&nbsp;74). They are more readily simulated by computer in tabular form (Booth, p.&nbsp;74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p.&nbsp;244ff)—can be more readily seen when viewed as a drawing.
+
In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3 (cf. Turing in ''The Undecidable'', p.&nbsp;126). He allowed for erasure of the "scanned square" by naming a 0th symbol S<sub>0</sub> = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S<sub>k</sub>" or "erase" (cf. footnote 12 in Post (1947), ''The Undecidable'', p.&nbsp;300). The abbreviations are Turing's (''The Undecidable'', p.&nbsp;119). Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of five-tuples:
   −
通常大的桌子最好留作桌子(Booth，第74页)。它们更容易被计算机以表格的形式模拟(Booth，74页)。然而，某些概念ーー例如。具有“复位”状态的机器和具有重复模式的机器(参见。希尔和彼得森 p. 244ff)---- 更容易被看作是一幅画。
+
! 5-tuple
   −
| L
+
!五元组
   −
| '''A'''
     −
Whether a drawing represents an improvement on its table must be decided by the reader for the particular context. See Finite state machine for more.
     −
绘图是否代表对其表的改进，必须由读者根据特定的上下文来决定。有关更多信息，请参见有限状态机。
+
! 5-tuple comments
   −
| ('''B''', 0, 1, L, '''A''')
+
!5-tuple 注释
   −
|-
+
{| class="wikitable" style="text-align: center"
   −
The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.
+
! 4-tuple
   −
忙碌海狸计算的进化从顶部开始，一直到底部。
+
!四元组
   −
| '''B'''
+
|-
   −
| 1
+
|-
   −
The reader should again be cautioned that such diagrams represent a snapshot of their table frozen in time, not the course ("trajectory") of a computation through time and space. While every time the busy beaver machine "runs" it will always follow the same state-trajectory, this is not true for the "copy" machine that can be provided with variable input "parameters".
+
|-
   −
读者应该再次注意，这样的图表代表了它们的表在时间上冻结的快照，而不是通过时间和空间计算的过程(“轨迹”)。虽然每次繁忙的海狸机器“运行”它总是遵循相同的状态轨迹，这是不正确的“复制”机器，可以提供可变的输入“参数”。
+
!
   −
|
+
| N1
   −
| 1
+
| n 1
   −
The diagram "Progress of the computation" shows the three-state busy beaver's "state" (instruction) progress through its computation from start to finish. On the far right is the Turing "complete configuration" (Kleene "situation"<!-- Stuation? Not Situation? Is that the right word? Yes, it is, cf. page 375 for example "The Godel number of the stiuation..." and then he shows a tape, etc. This usage runs throughout the chapter. wvbailey~~~~ --><!--So is it "stuation" or "stiuation"?-->, Hopcroft–Ullman "instantaneous description") at each step. If the machine were to be stopped and cleared to blank both the "state register" and entire tape, these "configurations" could be used to rekindle a computation anywhere in its progress (cf. Turing (1936) The Undecidable, pp.&nbsp;139–140).
+
! Current m-configuration<br />(Turing state)
   −
图表“计算进度”显示了三态繁忙海狸的“状态”(指令)进度通过其计算从开始到结束。最右边是图灵“完整配置”(Kleene“情况” < ! -- 研究？不是形势？这个词对吗？是的，没错。例如，第375页“ The Godel number of The stiuation... ” ，然后他展示了一个磁带，等等。这个用法贯穿整个章节。所以它是“研究”还是“退化” ? ——霍普克罗夫特-乌尔曼“瞬间描述”)在每一步。如果机器被停止并清空“状态寄存器”和整个磁带，这些“配置”可用于在其进程的任何地方重新启动计算(参见。图灵(1936) The undecutable，pp. 139-140)。
+
| q<sub>i</sub>
   −
| R
+
| q < sub > i </sub >
   −
| '''B'''
+
! Tape symbol
   −
| ('''B''', 1, 1, R, '''B''')
+
| S<sub>j</sub>
   −
|-
+
| s < sub > j </sub >
   −
| '''C'''
+
! Print-operation
   −
Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p.&nbsp;159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)
+
| Print(S<sub>k</sub>)
   −
许多机器，可能被认为比一个简单的通用图灵机有更多的计算能力，可以证明没有更多的权力(霍普克罗夫特和 Ullman p. 159，参考 f。明斯基(1967))。他们可能计算得更快，或者使用更少的内存，或者他们的指令集可能更小，但是他们不能计算得更有力(即。更多的数学函数)。(回想一下，丘奇-图灵的论点假设这对任何机器都是正确的: 任何可以被“计算”的东西都可以被一些图灵机计算出来。)
+
| 列印(s < sub > k </sub >)
   −
| 0
+
! Tape-motion
   −
|
+
| Left L
   −
A Turing machine is equivalent to a single-stack pushdown automaton (PDA) that has been made more flexible and concise by relaxing the last-in-first-out requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard last-in-first-out semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.
+
左 l
   −
图灵机相当于一个单堆栈下推自动机(PDA) ，通过放松堆栈中“先入先出”的要求，使其更加灵活和简洁。此外，通过使用一个堆栈对磁头左侧的磁带进行建模，而使用右侧的另一个堆栈对磁带进行建模，图灵机也等价于具有标准“后进先出”语义的双堆栈 PDA。
+
! Final m-configuration<br />(Turing state)
   −
| 1
+
| q<sub>m</sub>
   −
| L
+
| q < sub > m </sub >
   −
At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.
+
! 5-tuple
   −
在另一个极端，一些非常简单的模型被证明是图灵等价的，例如。具有与图灵机模型相同的计算能力。
+
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, L, q<sub>m</sub>)
   −
| '''B'''
+
| (q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，l，q < sub > m </sub >)
   −
| ('''C''', 0, 1, L, '''B''')
+
! 5-tuple comments
   −
Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
+
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
   −
常见的等效模型是多磁带图灵机、多轨图灵机、具有输入和输出的机器，以及与确定性图灵机(DTM)相对的非确定型图灵机(NDTM) ，后者的动作表对于每个符号和状态组合最多只有一个条目。
+
| “空白” = s < sub > 0 </sub > ，1 = s < sub > 1 </sub > 等。
   −
|-
+
! 4-tuple
   −
| '''C'''
+
|
   −
Read-only, right-moving Turing machines are equivalent to DFAs (as well as NFAs by conversion using the NDFA to DFA conversion algorithm).
+
|
   −
只读、右移动的图灵机相当于 DFAs (以及通过使用 NDFA 到 DFA 转换算法转换的 nfa)。
+
|-
   −
| 1
+
|-
   −
|
+
|-
   −
For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming language.
+
| N1
   −
对于实际的和教学的意图，等价的寄存器机可以作为一个通常的汇编程序语言使用。
+
| N2
   −
| 1
+
2
   −
| N
+
| q<sub>i</sub>
   −
An interesting question is whether the computation model represented by concrete programming languages is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, ANSI C is not Turing-equivalent, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called pointers, is accessible inside the language. However, other programming languages like Pascal do not have this feature, which allows them to be Turing complete in principle.
+
| q<sub>i</sub>
   −
一个有趣的问题是，用具体的编程语言表示的计算模型是否是图灵等价的。虽然真实计算机的计算是基于有限状态的，因此不能模拟图灵机，但是编程语言本身并不一定有这个限制。Kirner 等人在2009年的研究表明，在通用编程语言中，有些是图灵完备语言，而有些则不是。例如，ANSI c 不是图灵等效的，因为 ANSI c 的所有实例化(不同的实例化是可能的，因为标准由于遗留原因故意不定义某些行为)意味着有限的空间内存。这是因为内存引用数据类型(称为指针)的大小可以在语言中访问。然而，其他编程语言，比如 Pascal 没有这个特性，这使得它们原则上可以是图灵完整的。
+
| q < sub > i </sub >
   −
| '''H'''
+
| S<sub>j</sub>
   −
It is just Turing complete in principle, as memory allocation in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot.
+
| S<sub>j</sub>
   −
这只是图灵完成的原则，因为一种编程语言的内存分配是允许失败的，这意味着当忽略失败的内存分配时，编程语言可以是图灵完成的，但是在真正的计算机上编译的可执行程序不能。
+
| s < sub > j </sub >
   −
| ('''C''', 1, 1, N, '''H''')
+
| Print(S<sub>k</sub>)
   −
|}
+
| Print(S<sub>k</sub>)
    +
| 列印(s < sub > k </sub >)
    +
| Left L
   −
Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":
+
| Right R
   −
早在他的论文(1936)中，图灵区分了“自动机器”ーー它的“运动... ... 完全由配置决定”和“选择机器” :
+
| 右 r
   −
In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3 (cf. Turing in ''The Undecidable'', p.&nbsp;126). He allowed for erasure of the "scanned square" by naming a 0th symbol S<sub>0</sub> = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S<sub>k</sub>" or "erase" (cf. footnote 12 in Post (1947), ''The Undecidable'', p.&nbsp;300). The abbreviations are Turing's (''The Undecidable'', p.&nbsp;119). Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of five-tuples:
+
| q<sub>m</sub>
    +
| q<sub>m</sub>
    +
| q < sub > m </sub >
   −
{| class="wikitable" style="text-align: center"
+
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, L, q<sub>m</sub>)
   −
|-
+
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, R, q<sub>m</sub>)
   −
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.&nbsp;138)
+
| (q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，r，q < sub > m </sub >)
   −
图灵(1936)没有进一步阐述，除了在一个脚注中，他描述了如何使用一台机器“找到[希尔伯特]微积分的所有可证明的公式” ，而不是使用选择机器。他“假设总是在两种可能性0和1之间做出选择。每个证明将由一系列选项决定，i < sub > 1 </sub > ，i < sub > 2 </sub > ，... ，i < sub > n </sub > (i < sub > 1 </sub > 1 </sub > = 0或1，i < sub > 2 </sub > = 0或1，... ，i < sub > n </sub > = 0或1) ，因此数字2 < sup > n </sup > i </sup > 1 </sub > 2 </sub > n </sub > 2 </sub > 2 </sub > 2 </sub > 2 < n-2/> </2/> + i < i < </sub > 完全决定了证明。自动机器依次进行证明1，证明2，证明3，... ”(脚注‡ ，无法判定，第138页)
+
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
   −
!
+
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
   −
! Current m-configuration<br />(Turing state)
+
| “空白” = s < sub > 0 </sub > ，1 = s < sub > 1 </sub > 等。
   −
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.
+
|
   −
这确实是一种技术，通过这种技术，一个确定性的(例如，a -)图灵机可以用来模拟一个不确定的图灵机的动作; 图灵在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。
+
|
   −
! Tape symbol
+
|
   −
! Print-operation
+
|-
   −
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.&nbsp;166–168).
+
|-
   −
甲骨文机器或 o-machine 是一种图灵机器，它将计算暂停在“ o”状态，同时，为了完成计算，它“等待”“甲骨文”的决定——一个未指定的实体” ，除了说它不可能是一台机器”(图灵(1939) ，The undecutable，p. 166-168)。
+
|-
   −
! Tape-motion
+
| N2
   −
! Final m-configuration<br />(Turing state)
+
| N3
   −
! 5-tuple
+
| N3
   −
! 5-tuple comments
+
| q<sub>i</sub>
   −
! 4-tuple
+
| q<sub>i</sub>
   −
An implementation of a Turing machine
+
| q < sub > i </sub >
   −
图灵机的一种实现
+
| S<sub>j</sub>
   −
|-
+
| S<sub>j</sub>
   −
As Turing wrote in The Undecidable, p.&nbsp;128 (italics added):
+
| s < sub > j </sub >
   −
正如图灵在《无法判定》一书中所写，第128页(斜体) :
+
| Print(S<sub>k</sub>)
   −
| N1
+
| Print(S<sub>k</sub>)
   −
| q<sub>i</sub>
+
| 列印(s < sub > k </sub >)
   −
| S<sub>j</sub>
+
| Right R
 +
 
 +
| None N
   −
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.
+
| None n
   −
这一发现现在被认为是理所当然的，但在当时(1936年) ，它被认为是惊人的。将图灵称为“通用机器”的计算模型——“ u”简称为计算模型。戴维斯(2000)的基本理论突破，导致了储存程式计算机的概念。
+
| q<sub>m</sub>
   −
| Print(S<sub>k</sub>)
+
| q<sub>m</sub>
   −
| Left L
+
| q < sub > m </sub >
   −
| q<sub>m</sub>
+
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, R, q<sub>m</sub>)
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, L, q<sub>m</sub>)
+
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, N, q<sub>m</sub>)
   −
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)
+
| (q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，n，q < sub > m </sub >)
   −
在计算复杂度方面，一个多磁带通用图灵机只需要比它模拟的机器的对数因子慢一些。这个结果是在1966年由 F.C.Hennie 和 R.e. Stearns 获得的。(Arora and Barak，2009，定理1.9)
+
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
    
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
 
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
 +
 +
| “空白” = s < sub > 0 </sub > ，1 = s < sub > 1 </sub > 等。
    
|
 
|
   −
|-
+
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, q<sub>m</sub>)
   −
A Turing machine realization using [[Lego pieces]]
+
| (q < sub > i </sub > ，s < sub > j </sub > ，s < sub > k </sub > ，q < sub > m </sub >)
   −
使用[[乐高零件]]实现图灵机
+
|-
   −
| N2
+
|-
   −
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.
+
|-
   −
人们常说，图灵机不同于简单的自动机，它和真正的机器一样强大，能够执行真正的程序所能执行的任何操作。在这个陈述中被忽略的是，因为一个真实的机器只能有有限数量的配置，这个“真实的机器”实际上只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。
+
| N3
 +
 
 +
| 4
 +
 
 +
| 4
 +
 
 +
| q<sub>i</sub>
    
| q<sub>i</sub>
 
| q<sub>i</sub>
 +
 +
| q < sub > i </sub >
    
| S<sub>j</sub>
 
| S<sub>j</sub>
   −
There are a number of ways to explain why Turing machines are useful models of real computers:
+
| S<sub>j</sub>
   −
有很多方法可以解释为什么图灵机是真正计算机的有用模型:
+
| s < sub > j </sub >
    
| Print(S<sub>k</sub>)
 
| Print(S<sub>k</sub>)
   −
| Right R
+
| None N
 +
 
 +
| None n
 +
 
 +
| None N
   −
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.&nbsp;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.
+
| Left L
   −
任何一台真正的计算机可以计算的东西，图灵机也可以计算。例如: “图灵机可以模拟在编程语言中发现的任何类型的子例程，包括递归过程和任何已知的参数传递机制”(Hopcroft 和 Ullman p. 157)。一个足够大的 FSA 还可以模拟任何真正的计算机，而不用考虑 IO。因此，关于图灵机局限性的陈述也将适用于真正的计算机。
+
左 l
    
| q<sub>m</sub>
 
| q<sub>m</sub>
   −
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.
+
| q<sub>m</sub>
   −
区别仅仅在于图灵机操作无限量数据的能力。然而，在有限的时间内，图灵机(就像真正的机器)只能处理有限数量的数据。
+
| q < sub > m </sub >
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, R, q<sub>m</sub>)
+
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, N, q<sub>m</sub>)
   −
Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media.
+
| (q<sub>i</sub>, S<sub>j</sub>, N, L, q<sub>m</sub>)
   −
像图灵机一样，真正的机器可以根据需要扩大存储空间，方法是获取更多的磁盘或其他存储介质。
+
| (q < sub > i </sub > ，s < sub > j </sub > ，n，l，q < sub > m </sub >)
    
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
 
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
   −
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.
+
|
 +
 
 +
|
 +
 
 +
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, q<sub>m</sub>)
   −
使用简单的抽象模型描述真实机器程序通常比使用图灵机描述复杂得多。例如，一台描述算法的图灵机可能有几百种状态，而给定实际机器上的等价确定有限状态自动机(DFA)有千万亿。这使得 DFA 表示法无法进行分析。
+
| (q<sub>i</sub>, S<sub>j</sub>, L, q<sub>m</sub>)
   −
|
+
| (q < sub > i </sub > ，s < sub > j </sub > ，l，q < sub > m </sub >)
   −
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).
+
| 4
 +
 
 +
| 5
   −
图灵机简化了算法的陈述。在与图灵等价的抽象机器上运行的算法通常比在真实机器上运行的算法更通用，因为它们具有任意精度的可用数据类型，而且从不需要处理意外情况(包括但不限于内存耗尽)。
+
| 5
   −
| N3
+
| q<sub>i</sub>
    
| q<sub>i</sub>
 
| q<sub>i</sub>
   −
An experimental prototype of a Turing machine
+
| q < sub > i </sub >
   −
图灵机的实验样机
+
| S<sub>j</sub>
    
| S<sub>j</sub>
 
| S<sub>j</sub>
   −
| Print(S<sub>k</sub>)
+
| s < sub > j </sub >  
    
| None N
 
| None N
   −
| q<sub>m</sub>
+
| None N
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, N, q<sub>m</sub>)
+
| None n
   −
| "blank" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
+
| Left L
   −
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, q<sub>m</sub>)
+
| Right R
   −
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.
+
| 右 r
   −
图灵机的一个局限性在于它们不能很好地模拟特定排列的优势。例如，现代存储程序计算机实际上是一种更具体形式的抽象机器的实例，这种抽象机器被称为随机存取存储程序机器或 RASP 机器模型。与美国通用图灵机一样，RASP 将其“程序”存储在有限状态机的“指令”之外的“内存”中。与通用图灵机不同，RASP 具有无限数量可区分的、编号的但无限制的“寄存器”ー内存“单元” ，可以包含任何整数(参见。Elgot 和 Robinson (1964) ，Hartmanis (1971) ，特别是 Cook-Rechow (1973) ; 随机存取机的引用)。RASP 的有限状态机可以间接寻址(例如，一个寄存器的内容可以用作另一个寄存器的地址) ，因此 RASP 的“程序”可以寻址寄存器序列中的任何寄存器。这种区分的结果是，可以基于内存索引执行计算优化，这在一般的图灵机中是不可能的; 因此，当图灵机被用作边界运行时间的基础时，在某些算法的运行时间上可以证明一个“错误的下界”(由于图灵机的错误简化假设)。这方面的一个例子是二进制搜索，当使用 RASP 计算模型而不是图灵机模型时，这种算法的执行速度更快。
+
| q<sub>m</sub>
   −
|-
+
| q<sub>m</sub>
   −
| 4
+
| q < sub > m </sub >
   −
| q<sub>i</sub>
+
| (q<sub>i</sub>, S<sub>j</sub>, N, L, q<sub>m</sub>)
   −
| S<sub>j</sub>
+
| (q<sub>i</sub>, S<sub>j</sub>, N, R, q<sub>m</sub>)
   −
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.)
+
| (q < sub > i </sub > ，s < sub > j </sub > ，n，r，q < sub > m </sub >)
   −
图灵机的另一个局限是它们不能很好地模拟并发性。例如，可以由始终停止的不确定图灵机从空白磁带上开始计算整数大小的界限。(见关于无界非决定论的文章)相比之下，总是有停止的并发系统没有输入，可以计算一个无界大小的整数。(可以使用初始化为0的本地存储创建进程，并同时发送停止和继续消息。当它接收到一条 go 消息时，它将其计数增加1，并发送一条 go 消息。当它接收到一个停止消息时，它在本地存储器中将停止使用一个无界数字
+
|
   −
| None N
+
|
   −
| Left L
+
|
   −
| q<sub>m</sub>
+
| (q<sub>i</sub>, S<sub>j</sub>, L, q<sub>m</sub>)
   −
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.
+
| (q<sub>i</sub>, S<sub>j</sub>, R, q<sub>m</sub>)
   −
在计算机的早期，计算机的使用通常局限于批处理，即非交互式任务，每个输出数据来自给定的输入数据。可计算性理论研究从输入到输出的函数的可计算性，图灵机就是为此而发明的。
+
| (q < sub > i </sub > ，s < sub > j </sub > ，r，q < sub > m </sub >)
   −
| (q<sub>i</sub>, S<sub>j</sub>, N, L, q<sub>m</sub>)
+
|-
   −
|
+
|-
   −
Since the 1970s, 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 I/O automata are usually preferred.
+
|-
   −
自20世纪70年代以来，交互式使用计算机变得越来越普遍。原则上，通过让外部代理程序读取磁带并同时向其写入数据是可能的，但这很少与交互实际发生的方式相匹配; 因此，在描述交互性时，I/O 自动机等替代程序通常是首选的。
+
| 5
   −
| (q<sub>i</sub>, S<sub>j</sub>, L, q<sub>m</sub>)
+
| 6
   −
|-
+
| 6
   −
| 5
+
| q<sub>i</sub>
    
| q<sub>i</sub>
 
| q<sub>i</sub>
 +
 +
| q < sub > i </sub >
 +
 +
| S<sub>j</sub>
    
| S<sub>j</sub>
 
| S<sub>j</sub>
   −
They were described in 1936 by Alan Turing.
+
| s < sub > j </sub >
   −
阿兰 · 图灵在1936年描述了它们。
+
| None N
    
| None N
 
| None N
 +
 +
| None n
    
| Right R
 
| Right R
 +
 +
| None N
 +
 +
| None n
    
| q<sub>m</sub>
 
| q<sub>m</sub>
   −
Robin Gandy (1919–1995)—a student of Alan Turing (1912–1954), and his lifelong friend—traces the lineage of the notion of "calculating machine" back to Charles Babbage (circa 1834) and actually proposes "Babbage's Thesis":
+
| q<sub>m</sub>
   −
Robin Gandy (1919-1995)是 Alan Turing (1912-1954)的学生，也是他一生的朋友，他将“机械式计算器”的概念追溯到 Charles Babbage (大约1834年) ，并提出了“ Babbage’s Thesis” :
+
| q < sub > m </sub >
    
| (q<sub>i</sub>, S<sub>j</sub>, N, R, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, N, R, q<sub>m</sub>)
   −
|
+
| (q<sub>i</sub>, S<sub>j</sub>, N, N, q<sub>m</sub>)
 +
 
 +
| (q < sub > i </sub > ，s < sub > j </sub > ，n，q < sub > m </sub >)
 +
 
 +
|
 +
 
 +
| Direct "jump"
 +
 
 +
| 直接“跳”
    
| (q<sub>i</sub>, S<sub>j</sub>, R, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, R, q<sub>m</sub>)
 +
 +
| (q<sub>i</sub>, S<sub>j</sub>, N, q<sub>m</sub>)
 +
 +
| (q < sub > i </sub > ，s < sub > j </sub > ，n，q < sub > m </sub >)
    
|-
 
|-
   −
Gandy's analysis of Babbage's Analytical Engine describes the following five operations (cf. p.&nbsp;52–53):
+
|-
   −
甘迪对巴贝奇的分析机的分析描述了以下五个操作(参见。P. 52-53) :
+
|-
    
| 6
 
| 6
   −
The arithmetic functions +, −, ×, where − indicates "proper" subtraction  0}} if .
+
| 7
   −
算术函数 + ,-，× ，其中-表示“正确的”减法0}如果。
+
| 7
    
| q<sub>i</sub>
 
| q<sub>i</sub>
   −
Any sequence of operations is an operation.
+
| q<sub>i</sub>
   −
任何操作序列都是一个操作。
+
| q < sub > i </sub >
    
| S<sub>j</sub>
 
| S<sub>j</sub>
   −
Iteration of an operation (repeating n times an operation P).
+
| S<sub>j</sub>
   −
操作的迭代(重复 n 次操作 p)。
+
| s < sub > j </sub >
    
| None N
 
| None N
   −
Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
+
| Erase
   −
条件迭代(以测试 t 的“成功”为条件重复 n 次操作 p)。
+
擦除
    
| None N
 
| None N
   −
Conditional transfer (i.e., conditional "goto").
+
| Left L
 +
 
 +
左 l
   −
有条件转移(即有条件的“ goto”)。
+
| q<sub>m</sub>
    
| q<sub>m</sub>
 
| q<sub>m</sub>
 +
 +
| q < sub > m </sub >
    
| (q<sub>i</sub>, S<sub>j</sub>, N, N, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, N, N, q<sub>m</sub>)
   −
Gandy states that "the functions which can be calculated by (1), (2), and (4) are precisely those which are Turing computable." (p.&nbsp;53). He cites other proposals for "universal calculating machines" including those of Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937). However:
+
| (q<sub>i</sub>, S<sub>j</sub>, E, L, q<sub>m</sub>)
   −
甘迪指出: “可由(1)、(2)和(4)计算的函数恰恰是图灵可计算的函数。”(p. 53).他引用了其他关于“通用计算机器”的提议，包括珀西 · 卢德盖特(1909年)、莱昂纳多 · 托雷斯 · 奎维多(1914年)、莫里斯 · d’奥卡涅(1922年)、路易斯 · 库夫尼纳尔(1933年)、万尼瓦尔 · 布什(1936年)、霍华德 · 艾肯(1937年)。然而:
+
(q < sub > i </sub > ，s < sub > j </sub > ，e，l，q < sub > m </sub >)
    
| Direct "jump"
 
| Direct "jump"
 +
 +
|
 +
 +
|
    
| (q<sub>i</sub>, S<sub>j</sub>, N, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, N, q<sub>m</sub>)
 +
 +
|
 +
 +
|
 +
 +
|-
 +
 +
|-
    
|-
 
|-
    
| 7
 
| 7
 +
 +
| 8
 +
 +
| 8
    
| q<sub>i</sub>
 
| q<sub>i</sub>
   −
With regard to Hilbert's problems posed by the famous mathematician David Hilbert in 1900, an aspect of problem #10 had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for #10 is as follows:
+
| q<sub>i</sub>
   −
至于著名数学家大卫 · 希尔伯特在1900年提出的希尔伯特问题，第10号问题的一个方面在被精确设计之前已经漂浮了近30年。希尔伯特对 # 10的原始表达如下:
+
| q < sub > i </sub >
    
| S<sub>j</sub>
 
| S<sub>j</sub>
 +
 +
| S<sub>j</sub>
 +
 +
| s < sub > j </sub >
    
| Erase
 
| Erase
   −
{{quote|10. Determination of the solvability of a Diophantine equation. Given a Diophantine equation with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
+
| Erase
   −
{引用 | 10。丢番图方程可解性的测定。给定一个具有任意数量未知量和有理整系数的丢番图方程: 设计一个过程，根据这个过程可以在有限数量的运算中确定该方程是否在有理整数中是可解的。
+
擦除
    
| Left L
 
| Left L
 +
 +
| Right R
 +
 +
| 右 r
    
| q<sub>m</sub>
 
| q<sub>m</sub>
   −
The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.|quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008}}
+
| q<sub>m</sub>
   −
当我们知道一个程序允许任何给定的逻辑表达式通过有限多个操作来决定其有效性或可满足性时，可判定性问题[一阶逻辑的决策问题]就得到了解决..。可判定性必须被认为是数理逻辑的主要问题。2008年，德尔肖维茨和古列维奇引用了这个翻译和德文原文
+
| q < sub > m </sub >
    
| (q<sub>i</sub>, S<sub>j</sub>, E, L, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, E, L, q<sub>m</sub>)
 +
 +
| (q<sub>i</sub>, S<sub>j</sub>, E, R, q<sub>m</sub>)
 +
 +
(q < sub > i </sub > ，s < sub > j </sub > ，e，r，q < sub > m </sub >)
 +
 +
|
 +
 +
|
    
|
 
|
   −
By 1922, this notion of "Entscheidungsproblem" had developed a bit, and H. Behmann stated that
+
|
   −
到了1922年，这个“可判定性”的概念已经发展了一些，h. Behmann 说
+
|
    
|
 
|
第1,381行： 第1,477行：  
|-
 
|-
   −
{{quote|...&nbsp;most general form of the Entscheidungsproblem [is] as follows:
+
|-
   −
{{引用 | ... 可判定性的一般形式如下:
+
|-
    
| 8
 
| 8
   −
<blockquote>A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion ...</blockquote>|Gandy p. 57, quoting Behmann}}
+
| 9
 +
 
 +
| 9
   −
需要一个相当明确的、普遍适用的处方，这个处方将允许人们在有限的步骤中决定一个给定的纯粹逻辑断言的真实性或虚假性... ..
+
| q<sub>i</sub>
    
| q<sub>i</sub>
 
| q<sub>i</sub>
 +
 +
| q < sub > i </sub >
 +
 +
| S<sub>j</sub>
    
| S<sub>j</sub>
 
| S<sub>j</sub>
 +
 +
| s < sub > j </sub >
 +
 +
| Erase
    
| Erase
 
| Erase
 +
 +
擦除
    
| Right R
 
| Right R
   −
By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete ... Second, was mathematics consistent ... And thirdly, was mathematics decidable?" (Hodges p.&nbsp;91, Hawking p.&nbsp;1121). The first two questions were answered in 1930 by Kurt Gödel at the very same meeting where Hilbert delivered his retirement speech (much to the chagrin of Hilbert); the third—the Entscheidungsproblem—had to wait until the mid-1930s.
+
| None N
 +
 
 +
| None n
   −
到了1928年的国际数学家大会，希尔伯特把他的问题提得非常精确。第一，数学是完整的吗? 第二，数学是一致的吗? 第三，数学是可判定的吗? ”(Hodges p. 91，Hawking p. 1121).1930年，在希尔伯特发表退休演讲的同一次会议上，库尔特 · 哥德尔(Kurt Gödel)回答了前两个问题(这让希尔伯特颇为懊恼) ; 而第三个问题——协商问题——不得不等到上世纪30年代中期。
+
| q<sub>m</sub>
    
| q<sub>m</sub>
 
| q<sub>m</sub>
 +
 +
| q < sub > m </sub >
    
| (q<sub>i</sub>, S<sub>j</sub>, E, R, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, E, R, q<sub>m</sub>)
   −
The problem was that an answer first required a precise definition of "definite general applicable prescription", which Princeton professor Alonzo Church would come to call "effective calculability", and in 1928 no such definition existed. But over the next 6–7 years Emil Post developed his definition of a worker moving from room to room writing and erasing marks per a list of instructions (Post 1936), as did Church and his two students Stephen Kleene and J. B. Rosser by use of Church's lambda-calculus and Gödel's recursion theory (1934). Church's paper (published 15 April 1936) showed that the Entscheidungsproblem was indeed "undecidable" and beat Turing to the punch by almost a year (Turing's paper submitted 28 May 1936, published January 1937). In the meantime, Emil Post submitted a brief paper in the fall of 1936, so Turing at least had priority over Post. While Church refereed Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that Church's lambda-calculus and his machines would compute the same functions.
+
| (q<sub>i</sub>, S<sub>j</sub>, E, N, q<sub>m</sub>)
   −
问题在于，首先需要对“明确的一般适用处方”作出精确的定义，普林斯顿大学教授阿隆佐 · 丘奇将其称之为“有效可计算性” ，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特(Emil Post)定义了一个从一个房间走到另一个房间的工人，他在一系列指令中擦去了字迹(1936年以后) ，丘奇和他的两个学生斯蒂芬•克莱恩(Stephen Kleene)和 j。B. Rosser 使用 Church 的 lambda 微积分和哥德尔的可计算性理论。丘奇的论文(发表于1936年4月15日)表明，可判定性确实是“无法判定的” ，几乎用了一年时间击败了图灵(图灵于1936年5月28日提交的论文，发表于1937年1月)。与此同时，埃米尔 · 波斯特在1936年秋天提交了一份简短的论文，因此图灵至少比波斯特有优先权。当丘奇审阅图灵的论文时，图灵有时间研究丘奇的论文，并在附录中草拟了一个证据，证明丘奇的 λ 微积分和他的机器可以计算相同的函数。
+
(q < sub > i </sub > ，s < sub > j </sub > ，e，n，q < sub > m </sub >)
    
|
 
|
第1,415行： 第1,527行：  
|
 
|
   −
|-
+
|
   −
| 9
+
|
   −
And Post had only proposed a definition of calculability and criticized Church's "definition", but had proved nothing.
+
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
 +
 
 +
| (q < sub > i </sub > ，s < sub > j </sub > ，e，q < sub > m </sub >)
 +
 
 +
|-
 +
 
 +
|}
 +
 
 +
|}
   −
波斯特只是提出了一个可计算性的定义，并批评了丘奇的“定义” ，但什么也没有证明。
+
| 9
    
| q<sub>i</sub>
 
| q<sub>i</sub>
 +
 +
Any Turing table (list of instructions) can be constructed from the above nine 5-tuples. For technical reasons, the three non-printing or "N" instructions (4, 5, 6) can usually be dispensed with. For examples see Turing machine examples.
 +
 +
任何 Turing 表(指令列表)都可以由上面的9个5元组构成。由于技术原因，三个非打印或“ n”指令(4,5,6)通常可以省略。有关例子，请参阅图灵机的例子。
    
| S<sub>j</sub>
 
| S<sub>j</sub>
第1,429行： 第1,553行：  
| Erase
 
| Erase
   −
In the spring of 1935, Turing as a young Master's student at King's College Cambridge, UK, took on the challenge; he had been stimulated by the lectures of the logician M. H. A. Newman "and learned from them of Gödel's work and the Entscheidungsproblem ... Newman used the word 'mechanical' ... In his obituary of Turing 1955 Newman writes:
+
Less frequently the use of 4-tuples are encountered: these represent a further atomization of the Turing instructions (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); also see more at Post–Turing machine.
   −
1935年春天，图灵作为英国剑桥国王学院的一名年轻的硕士生接受了这个挑战，他受到逻辑学家 m. h. a. Newman 的演讲的鼓舞，从他们那里学到了哥德尔的作品和可判定性... ..。在图灵1955年的讣告中，纽曼写道:
+
遇到4元组使用的频率较低: 这些代表了图灵指令的进一步原子化(参见。Post (1947) ，Boolos & Jeffrey (1974,1999) ，Davis-Sigal-Weyuker (1994) ;.
    
| None N
 
| None N
第1,439行： 第1,563行：  
| (q<sub>i</sub>, S<sub>j</sub>, E, N, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, E, N, q<sub>m</sub>)
   −
|
+
The word "state" used in context of Turing machines can be a source of confusion, as it can mean two things. Most commentators after Turing have used "state" to mean the name/designator of the current instruction to be performed—i.e. the contents of the state register. But Turing (1936) made a strong distinction between a record of what he called the machine's "m-configuration", and the machine's (or person's) "state of progress" through the computation - the current state of the total system. What Turing called "the state formula" includes both the current instruction and all the symbols on the tape:
   −
Gandy states that:
+
在图灵机上下文中使用的“状态”这个词可能会引起混淆，因为它可能意味着两件事。图灵之后的大多数评论员都使用“ state”来表示当前要执行的指令的名称/指示器ーー即。国家登记册的内容。但是图灵(1936)在他所谓的机器“ m 配置”的记录和机器(或人)通过计算的“进展状态”——整个系统的当前状态——之间做出了很大的区别。图灵所说的“状态公式”包括当前指令和磁带上的所有符号:
   −
甘迪表示:
+
|
    
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
 
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
第1,451行： 第1,575行：       −
Any Turing table (list of instructions) can be constructed from the above nine 5-tuples. For technical reasons, the three non-printing or "N" instructions (4, 5, 6) can usually be dispensed with. For examples see [[Turing machine examples]].
+
Earlier in his paper Turing carried this even further: he gives an example where he placed a symbol of the current "m-configuration"—the instruction's label—beneath the scanned square, together with all the symbols on the tape (The Undecidable, p.&nbsp;121); this he calls "the complete configuration" (The Undecidable, p.&nbsp;118). To print the "complete configuration" on one line, he places the state-label/m-configuration to the left of the scanned symbol.
   −
While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges p.&nbsp;96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD thesis, titled "Systems of Logic Based on Ordinals", contains the following definition of "a computable function":
+
在论文的前面，图灵进一步阐述了这个观点: 他举了一个例子，他把当前“ m 配置”(指令的标签)的一个符号和磁带上的所有符号(无法判定，第121页)放在了扫描的正方形下面，他称之为“完整配置”(无法判定，第118页)。为了在一行上打印“完整配置” ，他将 state-label/m-configuration 放在扫描符号的左侧。
   −
虽然甘迪认为纽曼的上述言论是“误导性的” ，但并非所有人都赞同这一观点。图灵一生都对机器有着浓厚的兴趣: “艾伦从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他完全可以从问自己，称打字机为‘机械’是什么意思开始。”。在普林斯顿攻读博士学位期间，图灵构建了一个布尔逻辑乘数(见下文)。他的博士论文题为“基于序数的逻辑系统” ，包含了以下“可计算函数”的定义:
+
Any Turing table (list of instructions) can be constructed from the above nine 5-tuples. For technical reasons, the three non-printing or "N" instructions (4, 5, 6) can usually be dispensed with. For examples see [[Turing machine examples]].
       +
 +
A variant of this is seen in Kleene (1952) where Kleene shows how to write the Gödel number of a machine's "situation": he places the "m-configuration" symbol q<sub>4</sub> over the scanned square in roughly the center of the 6 non-blank squares on the tape (see the Turing-tape figure in this article) and puts it to the right of the scanned square. But Kleene refers to "q<sub>4</sub>" itself as "the machine state" (Kleene, p.&nbsp;374-375). Hopcroft and Ullman call this composite the "instantaneous description" and follow the Turing convention of putting the "current state" (instruction-label, m-configuration) to the left of the scanned symbol (p.&nbsp;149).
 +
 +
在 Kleene (1952年) ，Kleene 展示了如何写出机器“状态”的哥德尔数: 他将“ m 配置”符号 q < sub > 4 </sub > 放置在磁带上6个非空白方块的中心，并将其放置在被扫描方块的右侧。但 Kleene 将“ q < sub > 4 </sub > ”本身称为“机器状态”(Kleene，p. 374-375)。霍普克罗夫特和乌尔曼称这种组合为“瞬时描述” ，并遵循图灵约定，将“当前状态”(指令-标签，m-配置)放在扫描符号的左侧(第149页)。
    
Less frequently the use of 4-tuples are encountered: these represent a further atomization of the Turing instructions (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); also see more at [[Post–Turing machine]].
 
Less frequently the use of 4-tuples are encountered: these represent a further atomization of the Turing instructions (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); also see more at [[Post–Turing machine]].
       +
 +
Example: total state of 3-state 2-symbol busy beaver after 3 "moves" (taken from example "run" in the figure below):
 +
 +
例如: 3个状态2个符号的忙碌海狸在3个“ move”之后的总状态(取自下图中的“ run”示例) :
    
===The "state"===
 
===The "state"===
   −
When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes created by encryption machines called "The Enigma"; he also became involved in the design of the ACE (Automatic Computing Engine), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the EDVAC [the USA's initiative], but in his own universal machine" (Hodges p.&nbsp;318). Arguments still continue concerning the origin and nature of what has been named by Kleene (1952) Turing's Thesis. But what Turing did prove with his computational-machine model appears in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (1937):
+
1A1
   −
当图灵回到英国后，他最终共同负责破解由加密机制造的德国秘密代码“谜” ; 他还参与了 ACE (自动计算机引擎)的设计，“(图灵的) ACE 提案实际上是自成一体的，它的根基不在于 EDVAC (美国的倡议) ，而在于他自己的通用机器”(第318页)。关于克莱恩(1952)图灵命名的东西的起源和性质的争论仍在继续。但是图灵用他的计算机模型证明的东西出现在他的论文《论可计算的数字，以及对可判定性的应用》(1937)中:
+
1A1
    
The word "state" used in context of Turing machines can be a source of confusion, as it can mean two things. Most commentators after Turing have used "state" to mean the name/designator of the current instruction to be performed—i.e. the contents of the state register. But Turing (1936) made a strong distinction between a record of what he called the machine's "m-configuration", and the machine's (or person's) "state of progress" through the computation - the current state of the total system. What Turing called "the state formula" includes both the current instruction and ''all'' the symbols on the tape:
 
The word "state" used in context of Turing machines can be a source of confusion, as it can mean two things. Most commentators after Turing have used "state" to mean the name/designator of the current instruction to be performed—i.e. the contents of the state register. But Turing (1936) made a strong distinction between a record of what he called the machine's "m-configuration", and the machine's (or person's) "state of progress" through the computation - the current state of the total system. What Turing called "the state formula" includes both the current instruction and ''all'' the symbols on the tape:
 +
 +
This means: after three moves the tape has ... 000110000 ... on it, the head is scanning the right-most 1, and the state is A. Blanks (in this case represented by "0"s) can be part of the total state as shown here: B01; the tape has a single 1 on it, but the head is scanning the 0 ("blank") to its left and the state is B.
 +
 +
这意味着: 三步之后，磁带有... 000110000... 在它上面，磁头正在扫描最右边的1，状态是 a。空格(在这里用“0”表示)可以是总状态的一部分，如下所示: B01; 磁带上有一个单独的1，但磁头正在扫描其左边的0(“空白”) ，状态是 b。
      第1,475行： 第1,611行：  
{{quote|Thus the state of progress of the computation at any stage is completely determined by the note of instructions and the symbols on the tape. That is, the '''state of the system''' may be described by a single expression (sequence of symbols) consisting of the symbols on the tape followed by Δ (which we suppose not to appear elsewhere) and then by the note of instructions. This expression is called the 'state formula'.|''The Undecidable'', pp. 139–140, emphasis added}}
 
{{quote|Thus the state of progress of the computation at any stage is completely determined by the note of instructions and the symbols on the tape. That is, the '''state of the system''' may be described by a single expression (sequence of symbols) consisting of the symbols on the tape followed by Δ (which we suppose not to appear elsewhere) and then by the note of instructions. This expression is called the 'state formula'.|''The Undecidable'', pp. 139–140, emphasis added}}
    +
"State" in the context of Turing machines should be clarified as to which is being described: (i) the current instruction, or (ii) the list of symbols on the tape together with the current instruction, or (iii) the list of symbols on the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned symbol.
    +
图灵机上下文中的”状态”应当澄清: (i)当前指令，或者(ii)磁带上的符号列表连同当前指令，或者(iii)磁带上的符号列表连同扫描符号左侧或扫描符号右侧的当前指令。
   −
Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".
     −
图灵的例子(他的第二个证明) : 如果一个人要求一个通用程序告诉我们: “这台机器曾经打印过0吗? ” ，这个问题是“无法判定的”。
      
Earlier in his paper Turing carried this even further: he gives an example where he placed a symbol of the current "m-configuration"—the instruction's label—beneath the scanned square, together with all the symbols on the tape (''The Undecidable'', p.&nbsp;121); this he calls "the ''complete configuration''" (''The Undecidable'', p.&nbsp;118). To print the "complete configuration" on one line, he places the state-label/m-configuration to the ''left'' of the scanned symbol.
 
Earlier in his paper Turing carried this even further: he gives an example where he placed a symbol of the current "m-configuration"—the instruction's label—beneath the scanned square, together with all the symbols on the tape (''The Undecidable'', p.&nbsp;121); this he calls "the ''complete configuration''" (''The Undecidable'', p.&nbsp;118). To print the "complete configuration" on one line, he places the state-label/m-configuration to the ''left'' of the scanned symbol.
 +
 +
Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.
 +
 +
图灵的传记作者安德鲁 · 霍奇斯(1983:107)注意到并讨论了这种混淆。
      第1,487行： 第1,627行：  
A variant of this is seen in Kleene (1952) where [[Stephen Cole Kleene|Kleene]] shows how to write the [[Gödel number]] of a machine's "situation": he places the "m-configuration" symbol q<sub>4</sub> over the scanned square in roughly the center of the 6 non-blank squares on the tape (see the Turing-tape figure in this article) and puts it to the ''right'' of the scanned square. But Kleene refers to "q<sub>4</sub>" itself as "the machine state" (Kleene, p.&nbsp;374-375). Hopcroft and Ullman call this composite the "instantaneous description" and follow the Turing convention of putting the "current state" (instruction-label, m-configuration) to the ''left'' of the scanned symbol (p.&nbsp;149).
 
A variant of this is seen in Kleene (1952) where [[Stephen Cole Kleene|Kleene]] shows how to write the [[Gödel number]] of a machine's "situation": he places the "m-configuration" symbol q<sub>4</sub> over the scanned square in roughly the center of the 6 non-blank squares on the tape (see the Turing-tape figure in this article) and puts it to the ''right'' of the scanned square. But Kleene refers to "q<sub>4</sub>" itself as "the machine state" (Kleene, p.&nbsp;374-375). Hopcroft and Ullman call this composite the "instantaneous description" and follow the Turing convention of putting the "current state" (instruction-label, m-configuration) to the ''left'' of the scanned symbol (p.&nbsp;149).
   −
In 1937, while at Princeton working on his PhD thesis, Turing built a digital (Boolean-logic) multiplier from scratch, making his own electromechanical relays (Hodges p.&nbsp;138). "Alan's task was to embody the logical design of a Turing machine in a network of relay-operated switches ..." (Hodges p.&nbsp;138). While Turing might have been just initially curious and experimenting, quite-earnest work in the same direction was going in Germany (Konrad Zuse (1938)), and in the United States (Howard Aiken) and George Stibitz (1937); the fruits of their labors were used by both the Axis and Allied militaries in World War II (cf. Hodges p.&nbsp;298–299). In the early to mid-1950s Hao Wang and Marvin Minsky reduced the Turing machine to a simpler form (a precursor to the Post–Turing machine of Martin Davis); simultaneously European researchers were reducing the new-fangled electronic computer to a computer-like theoretical object equivalent to what was now being called a "Turing machine". In the late 1950s and early 1960s, the coincidentally parallel developments of Melzak and Lambek (1961), Minsky (1961), and Shepherdson and Sturgis (1961) carried the European work further and reduced the Turing machine to a more friendly, computer-like abstract model called the counter machine; Elgot and Robinson (1964), Hartmanis (1971), Cook and Reckhow (1973) carried this work even further with the register machine and random-access machine models—but basically all are just multi-tape Turing machines with an arithmetic-like instruction set.
     −
1937年，在普林斯顿大学完成博士论文时，图灵从零开始制造了一个数字(布尔逻辑)乘法器，制造了他自己的机电式继电器(Hodges p. 138)。“艾伦的任务是在中继操作的开关网络中体现图灵机的逻辑设计... ”(Hodges p. 138)。虽然图灵最初可能只是好奇和试验，但是在德国(Konrad Zuse，1938年) ，美国(Howard Aiken)和乔治 · 斯蒂比茨(George Stibitz，1937年) ，他们的劳动成果被轴心国和盟国军队在第二次世界大战中使用。Hodges p. 298-299).在20世纪50年代早期到中期，Hao Wang 和 Marvin Minsky 将图灵机简化为一种更简单的形式(它是 Martin Davis 的后图灵机的前身) ; 与此同时，欧洲的研究人员将这种新型电子计算机简化为一种类似于计算机的理论物体，相当于现在所说的“图灵机”。在20世纪50年代末和60年代初，巧合地并行发展的 Melzak 和 Lambek (1961)、 Minsky (1961)和 Shepherdson and Sturgis (1961)进一步推进了欧洲的工作，并将图灵机简化为一个更友好的、类似计算机的抽象模型，称为计数器; Elgot 和 Robinson (1964)、 Hartmanis (1971)、 Cook 和 Reckhow (1973)将这项工作进一步推进到寄存器和随机存取机器模型ーー但基本上所有这些都只是带有类似指令集的多磁带算术机。
      +
'''Example: total state of 3-state 2-symbol busy beaver after 3 "moves"''' (taken from example "run" in the figure below):
    +
{|class="wikitable"
   −
'''Example: total state of 3-state 2-symbol busy beaver after 3 "moves"''' (taken from example "run" in the figure below):
+
{ | class = “ wikitable”
    
:: 1'''A'''1
 
:: 1'''A'''1
   −
Today, the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating questions in the theory of computation. In particular, computational complexity theory makes use of the Turing machine:
+
|+ The table for the 3-state busy beaver ("P" = print/write a "1")
   −
今天，计数器、寄存器和随机存取机器以及它们的祖先图灵机仍然是研究计算理论问题的理论家们的首选模型。特别值得一提的是，计算复杂性理论使用图灵机:
+
| + 3州繁忙海狸的桌子(“ p” = 打印/写一个“1”)
    
This means: after three moves the tape has ... 000110000 ... on it, the head is scanning the right-most 1, and the state is '''A'''. Blanks (in this case represented by "0"s) can be part of the total state as shown here: '''B'''01; the tape has a single 1 on it, but the head is scanning the 0 ("blank") to its left and the state is '''B'''.
 
This means: after three moves the tape has ... 000110000 ... on it, the head is scanning the right-most 1, and the state is '''A'''. Blanks (in this case represented by "0"s) can be part of the total state as shown here: '''B'''01; the tape has a single 1 on it, but the head is scanning the 0 ("blank") to its left and the state is '''B'''.
    +
|-
    +
|-
   −
{{quote|Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models have obtained a dominant position in machine-based complexity theory:
     −
{{ quote | 取决于人们喜欢在计算中操纵的对象(如非负整数或字母数字字符串) ，两个模型在机器复杂性理论中占据了主导地位:
     −
"State" in the context of Turing machines should be clarified as to which is being described: (''i'') the current instruction, or (''ii'') the list of symbols on the tape together with the current instruction, or (''iii'') the list of symbols on the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned symbol.
+
! Tape symbol
   −
<blockquote>the off-line multitape Turing machine..., which represents the standard model for string-oriented computation, and
+
!磁带符号
   −
离线多带图灵机... ，它代表了面向字符串计算的标准模型
+
"State" in the context of Turing machines should be clarified as to which is being described: (''i'') the current instruction, or (''ii'') the list of symbols on the tape together with the current instruction, or (''iii'') the list of symbols on the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned symbol.
    +
! colspan="3" | Current state A
    +
!Colspan = “3” | 当前状态 a
   −
Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.
     −
the random access machine (RAM) as introduced by Cook and Reckhow ..., which models the idealized Von Neumann style computer.</blockquote>|van Emde Boas 1990:4}}
     −
由 Cook 和 Reckhow... 引入的随机存取机(RAM) ，它模拟了理想化的冯诺依曼式计算机。1990:4}
+
! colspan="3" | Current state B
    +
!Colspan = “3” | 当前状态 b
    +
Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.
   −
===Turing machine "state" diagrams===
+
! colspan="3" | Current state C
    +
!Colspan = “3” | 当前状态 c
      −
{|class="wikitable"
     −
|+ The table for the 3-state busy beaver ("P" = print/write a "1")
+
|-
    
|-
 
|-
   −
! Tape symbol
+
===Turing machine "state" diagrams===
   −
! colspan="3" | Current state A
+
|
   −
! colspan="3" | Current state B
+
|
   −
! colspan="3" | Current state C
     −
|-
     −
|
+
| Write symbol
 +
 
 +
| 写入符号
   −
| Write symbol
+
{|class="wikitable"
    
| Move tape
 
| Move tape
 +
 +
移动磁带
 +
 +
|+ The table for the 3-state busy beaver ("P" = print/write a "1")
    
| Next state
 
| Next state
 +
 +
下一个州
 +
 +
|-
    
| Write symbol
 
| Write symbol
 +
 +
| 写入符号
 +
 +
! Tape symbol
    
| Move tape
 
| Move tape
 +
 +
移动磁带
 +
 +
! colspan="3" | Current state A
    
| Next state
 
| Next state
 +
 +
下一个州
 +
 +
! colspan="3" | Current state B
    
| Write symbol
 
| Write symbol
 +
 +
| 写入符号
 +
 +
! colspan="3" | Current state C
    
| Move tape
 
| Move tape
   −
| Next state
+
移动磁带
    
|-
 
|-
   −
| '''0'''
+
| Next state
   −
| P
+
下一个州
   −
| R
+
|
   −
| '''B'''
+
|-
   −
| P
+
|-
   −
| L
+
| Write symbol
   −
| '''A'''
+
| 0
   −
| P
+
| 0
   −
| L
+
| Move tape
   −
| '''B'''
+
| P
   −
|-
+
| p
   −
| '''1'''
+
| Next state
   −
| P
+
| R
   −
| L
+
| r
   −
| '''C'''
+
| Write symbol
   −
| P
+
| B
   −
| R
+
| b
   −
| '''B'''
+
| Move tape
    
| P
 
| P
   −
| R
+
| p
   −
| '''HALT'''
+
| Next state
   −
|}
+
| L
    +
| l
    +
| Write symbol
   −
[[File:State diagram 3 state busy beaver 2B.svg|thumb|500px|right|The "3-state busy beaver" Turing machine in a [[Finite State Machine|finite state representation]]. Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state ''transition'' is shown by an arrow. The label (e.g. '''0/P,R''') near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g. '''0''') followed by a slash '''/''', followed by the subsequent "behaviors" of the machine, e.g. "'''P''' '''P'''rint" then move tape "'''R''' '''R'''ight". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).]]
+
| A
    +
我会的
    +
| Move tape
   −
To the right: the above table as expressed as a "state transition" diagram.
+
| P
    +
| p
    +
| Next state
   −
Usually large tables are better left as tables (Booth, p.&nbsp;74). They are more readily simulated by computer in tabular form (Booth, p.&nbsp;74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p.&nbsp;244ff)—can be more readily seen when viewed as a drawing.
+
| L
    +
| l
    +
|-
   −
Whether a drawing represents an improvement on its table must be decided by the reader for the particular context. See [[Finite state machine]] for more.
+
| B
    +
| b
    +
| '''0'''
   −
[[File:Moves of a 3-state Busy Beaver.jpg|thumbnail|500px|right|The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.]]
+
|-
    +
|-
    +
| P
   −
The reader should again be cautioned that such diagrams represent a snapshot of their table frozen in time, ''not'' the course ("trajectory") of a computation ''through'' time and space. While every time the busy beaver machine "runs" it will always follow the same state-trajectory, this is not true for the "copy" machine that can be provided with variable input "parameters".
+
| 1
    +
| 1
    +
| R
   −
The diagram "Progress of the computation" shows the three-state busy beaver's "state" (instruction) progress through its computation from start to finish. On the far right is the Turing "complete configuration" (Kleene "situation"<!-- Stuation? Not Situation? Is that the right word? Yes, it is, cf. page 375 for example "The Godel number of the stiuation..." and then he shows a tape, etc. This usage runs throughout the chapter. wvbailey~~~~ --><!--So is it "stuation" or "stiuation"?-->, Hopcroft–Ullman "instantaneous description") at each step. If the machine were to be stopped and cleared to blank both the "state register" and entire tape, these "configurations" could be used to rekindle a computation anywhere in its progress (cf. Turing (1936) ''The Undecidable'', pp.&nbsp;139–140).
+
| P
    +
| p
    +
| '''B'''
   −
==Models equivalent to the Turing machine model==
+
| L
   −
{{See also|Turing machine equivalents|Register machine|Post–Turing machine}}
+
| l
    +
| P
    +
| C
   −
Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p.&nbsp;159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the [[Church–Turing thesis]] ''hypothesizes'' this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)
+
| c
    +
| L
    +
| P
   −
A Turing machine is equivalent to a single-stack [[pushdown automaton]] (PDA) that has been made more flexible and concise by relaxing the [[LIFO (computing)|last-in-first-out]] requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard [[LIFO (computing)|last-in-first-out]] semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.
+
| p
    +
| '''A'''
    +
| R
   −
At the other extreme, some very simple models turn out to be [[Turing completeness|Turing-equivalent]], i.e. to have the same computational power as the Turing machine model.
+
| r
    +
| P
    +
| B
   −
Common equivalent models are the [[multi-tape Turing machine]], [[multi-track Turing machine]], machines with input and output, and the [[Non-deterministic Turing machine|''non-deterministic'' Turing machine]] (NDTM) as opposed to the ''deterministic'' Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
+
| b
    +
| L
    +
| P
   −
[[Read-only right moving Turing machines|Read-only, right-moving Turing machines]] are equivalent to [[Deterministic finite automaton|DFAs]] (as well as [[Nondeterministic finite automaton|NFAs]] by conversion using the [[NDFA to DFA conversion algorithm]]).
+
| p
    +
| '''B'''
    +
| R
   −
For practical and didactical intentions the equivalent [[register machine]] can be used as a usual [[Assembly language|assembly]] [[programming language]].
+
| r
    +
|-
    +
| HALT
   −
An interesting question is whether the computation model represented by concrete [[programming languages]] is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, [[ANSI C]] is not Turing-equivalent, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called ''pointers'', is accessible inside the language. However, other programming languages like [[Pascal (programming language)|Pascal]] do not have this feature, which allows them to be Turing complete in principle.
+
| HALT
   −
It is just Turing complete in principle, as [[memory allocation]] in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot.
+
| '''1'''
    +
|}
    +
|}
   −
==Choice c-machines, oracle o-machines==
+
| P
   −
Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":
+
| L
    +
finite state representation. Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state transition is shown by an arrow. The label (e.g. 0/P,R) near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g. 0) followed by a slash /, followed by the subsequent "behaviors" of the machine, e.g. "P Print" then move tape "R Right". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).]]
    +
有限状态表示。每个圆圈表示一个表的“状态”ーー一个“ m 配置”或“指令”。状态转换的“方向”用箭头表示。标签(例如:。0/P，r)指定导致特定转换的扫描符号(例如:。0)后跟斜线/，后跟机器的后续“行为” ，例如:。“ p 打印”然后移动磁带“ r 右”。没有普遍接受的格式存在。这个展览是在麦克卢斯基(1965) ，布斯(1967) ，希尔和彼得森(1974)之后展出的
   −
{{quote|...whose motion is only partially determined by the configuration ... When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems.|''The Undecidable'', p. 118}}
+
| '''C'''
    +
| P
    +
To the right: the above table as expressed as a "state transition" diagram.
   −
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.&nbsp;138)
+
向右: 以上表格用“状态转换”图表示。
    +
| R
    +
| '''B'''
   −
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.
+
Usually large tables are better left as tables (Booth, p.&nbsp;74). They are more readily simulated by computer in tabular form (Booth, p.&nbsp;74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p.&nbsp;244ff)—can be more readily seen when viewed as a drawing.
    +
通常大的桌子最好留作桌子(Booth，第74页)。它们更容易被计算机以表格的形式模拟(Booth，74页)。然而，某些概念ーー例如。具有“复位”状态的机器和具有重复模式的机器(参见。希尔和彼得森 p. 244ff)---- 更容易被看作是一幅画。
    +
| P
   −
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.&nbsp;166–168).
+
| R
    +
Whether a drawing represents an improvement on its table must be decided by the reader for the particular context. See Finite state machine for more.
    +
绘图是否代表对其表的改进，必须由读者根据特定的上下文来决定。有关更多信息，请参见有限状态机。
   −
==Universal Turing machines==
+
| '''HALT'''
   −
{{Main|Universal Turing machine}}
+
|}
    +
The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.
    +
忙碌海狸计算的进化从顶部开始，一直到底部。
   −
[[File:Model of a Turing machine.jpg|thumb|An implementation of a Turing machine]]
     −
As Turing wrote in ''The Undecidable'', p.&nbsp;128 (italics added):
     −
{{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'''.}}
+
[[File:State diagram 3 state busy beaver 2B.svg|thumb|500px|right|The "3-state busy beaver" Turing machine in a [[Finite State Machine|finite state representation]]. Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state ''transition'' is shown by an arrow. The label (e.g. '''0/P,R''') near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g. '''0''') followed by a slash '''/''', followed by the subsequent "behaviors" of the machine, e.g. "'''P''' '''P'''rint" then move tape "'''R''' '''R'''ight". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).]]
    +
The reader should again be cautioned that such diagrams represent a snapshot of their table frozen in time, not the course ("trajectory") of a computation through time and space. While every time the busy beaver machine "runs" it will always follow the same state-trajectory, this is not true for the "copy" machine that can be provided with variable input "parameters".
    +
读者应该再次注意，这样的图表代表了它们的表在时间上冻结的快照，而不是通过时间和空间计算的过程(“轨迹”)。虽然每次繁忙的海狸机器“运行”它总是遵循相同的状态轨迹，这是不正确的“复制”机器，可以提供可变的输入“参数”。
   −
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]].
         +
To the right: the above table as expressed as a "state transition" diagram.
   −
{{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}}
+
The diagram "Progress of the computation" shows the three-state busy beaver's "state" (instruction) progress through its computation from start to finish. On the far right is the Turing "complete configuration" (Kleene "situation"<!-- Stuation? Not Situation? Is that the right word? Yes, it is, cf. page 375 for example "The Godel number of the stiuation..." and then he shows a tape, etc. This usage runs throughout the chapter. wvbailey~~~~ --><!--So is it "stuation" or "stiuation"?-->, Hopcroft–Ullman "instantaneous description") at each step. If the machine were to be stopped and cleared to blank both the "state register" and entire tape, these "configurations" could be used to rekindle a computation anywhere in its progress (cf. Turing (1936) The Undecidable, pp.&nbsp;139–140).
    +
图表“计算进度”显示了三态繁忙海狸的“状态”(指令)进度通过其计算从开始到结束。最右边是图灵“完整配置”(Kleene“情况” < ! -- 研究？不是形势？这个词对吗？是的，没错。例如，第375页“ The Godel number of The stiuation... ” ，然后他展示了一个磁带，等等。这个用法贯穿整个章节。所以它是“研究”还是“退化” ? ——霍普克罗夫特-乌尔曼“瞬间描述”)在每一步。如果机器被停止并清空“状态寄存器”和整个磁带，这些“配置”可用于在其进程的任何地方重新启动计算(参见。图灵(1936) The undecutable，pp. 139-140)。
      −
In terms of [[Computational complexity theory|computational complexity]], a multi-tape universal Turing machine need only be slower by [[logarithm]]ic 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)
      +
Usually large tables are better left as tables (Booth, p.&nbsp;74). They are more readily simulated by computer in tabular form (Booth, p.&nbsp;74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p.&nbsp;244ff)—can be more readily seen when viewed as a drawing.
      −
==Comparison with real machines==
     −
[[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces]]
+
Whether a drawing represents an improvement on its table must be decided by the reader for the particular context. See [[Finite state machine]] for more.
   −
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.
         +
Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p.&nbsp;159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)
   −
There are a number of ways to explain why Turing machines are useful models of real computers:
+
许多机器，可能被认为比一个简单的通用图灵机有更多的计算能力，可以证明没有更多的权力(霍普克罗夫特和 Ullman p. 159，参考 f。明斯基(1967))。他们可能计算得更快，或者使用更少的内存，或者他们的指令集可能更小，但是他们不能计算得更有力(即。更多的数学函数)。(回想一下，丘奇-图灵的论点假设这对任何机器都是正确的: 任何可以被“计算”的东西都可以被一些图灵机计算出来。)
 +
 
 +
[[File:Moves of a 3-state Busy Beaver.jpg|thumbnail|500px|right|The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.]]
 +
 
 +
 
 +
 
 +
A Turing machine is equivalent to a single-stack pushdown automaton (PDA) that has been made more flexible and concise by relaxing the last-in-first-out requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard last-in-first-out semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.
    +
图灵机相当于一个单堆栈下推自动机(PDA) ，通过放松堆栈中“先入先出”的要求，使其更加灵活和简洁。此外，通过使用一个堆栈对磁头左侧的磁带进行建模，而使用右侧的另一个堆栈对磁带进行建模，图灵机也等价于具有标准“后进先出”语义的双堆栈 PDA。
    +
The reader should again be cautioned that such diagrams represent a snapshot of their table frozen in time, ''not'' the course ("trajectory") of a computation ''through'' time and space. While every time the busy beaver machine "runs" it will always follow the same state-trajectory, this is not true for the "copy" machine that can be provided with variable input "parameters".
   −
# 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.&nbsp;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.
     −
# 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.
+
At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.
   −
# 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.
+
The diagram "Progress of the computation" shows the three-state busy beaver's "state" (instruction) progress through its computation from start to finish. On the far right is the Turing "complete configuration" (Kleene "situation"<!-- Stuation? Not Situation? Is that the right word? Yes, it is, cf. page 375 for example "The Godel number of the stiuation..." and then he shows a tape, etc. This usage runs throughout the chapter. wvbailey~~~~ --><!--So is it "stuation" or "stiuation"?-->, Hopcroft–Ullman "instantaneous description") at each step. If the machine were to be stopped and cleared to blank both the "state register" and entire tape, these "configurations" could be used to rekindle a computation anywhere in its progress (cf. Turing (1936) ''The Undecidable'', pp.&nbsp;139–140).
   −
# 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]]).
         +
Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
   −
[[File:Turingmachine.jpg|thumb|An experimental prototype of a Turing machine]]
+
常见的等效模型是多磁带图灵机、多轨图灵机、具有输入和输出的机器，以及与确定性图灵机(DTM)相对的非确定型图灵机(NDTM) ，后者的动作表对于每个符号和状态组合最多只有一个条目。
   −
Category:1936 in computing
+
==Models equivalent to the Turing machine model==
   −
类别: 1936年
+
{{See also|Turing machine equivalents|Register machine|Post–Turing machine}}
    +
Read-only, right-moving Turing machines are equivalent to DFAs (as well as NFAs by conversion using the NDFA to DFA conversion algorithm).
    +
只读、右移动的图灵机相当于 DFAs (以及通过使用 NDFA 到 DFA 转换算法转换的 nfa)。
   −
Category:1937 in computing
     −
类别: 1937年计算机
     −
===Limitations of Turing machines===
+
Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p.&nbsp;159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the [[Church–Turing thesis]] ''hypothesizes'' this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)
   −
Category:Educational abstract machines
+
For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming language.
−
 
+
 
−
类别: 教育摘要机器
+
对于实际的和教学的意图，等价的寄存器机可以作为一个通常的汇编程序语言使用。
−
 
+
 
−
 
+
 
−
 
+
 
−
Category:Theoretical computer science
+
A Turing machine is equivalent to a single-stack [[pushdown automaton]] (PDA) that has been made more flexible and concise by relaxing the [[LIFO (computing)|last-in-first-out]] requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard [[LIFO (computing)|last-in-first-out]] semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.
−
 
+
 
−
类别: 理论计算机科学
+
An interesting question is whether the computation model represented by concrete programming languages is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, ANSI C is not Turing-equivalent, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called pointers, is accessible inside the language. However, other programming languages like Pascal do not have this feature, which allows them to be Turing complete in principle.
−
 
+
 
−
====Computational complexity theory====
+
一个有趣的问题是，用具体的编程语言表示的计算模型是否是图灵等价的。虽然真实计算机的计算是基于有限状态的，因此不能模拟图灵机，但是编程语言本身并不一定有这个限制。Kirner 等人在2009年的研究表明，在通用编程语言中，有些是图灵完备语言，而有些则不是。例如，ANSI c 不是图灵等效的，因为 ANSI c 的所有实例化(不同的实例化是可能的，因为标准由于遗留原因故意不定义某些行为)意味着有限的空间内存。这是因为内存引用数据类型(称为指针)的大小可以在语言中访问。然而，其他编程语言，比如 Pascal 没有这个特性，这使得它们原则上可以是图灵完整的。
−
 
+
 
−
Category:Alan Turing
+
 
 +
 
 +
It is just Turing complete in principle, as memory allocation in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot.
 +
 
 +
这只是图灵完成的原则，因为一种编程语言的内存分配是允许失败的，这意味着当忽略失败的内存分配时，编程语言可以是图灵完成的，但是在真正的计算机上编译的可执行程序不能。
 +
 
 +
At the other extreme, some very simple models turn out to be [[Turing completeness|Turing-equivalent]], i.e. to have the same computational power as the Turing machine model.
 +
 
 +
 
 +
 
 +
Common equivalent models are the [[multi-tape Turing machine]], [[multi-track Turing machine]], machines with input and output, and the [[Non-deterministic Turing machine|''non-deterministic'' Turing machine]] (NDTM) as opposed to the ''deterministic'' Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
 +
 
 +
Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":
 +
 
 +
早在他的论文(1936)中，图灵区分了“自动机器”ーー它的“运动... ... 完全由配置决定”和“选择机器” :
 +
 
 +
 
 +
 
 +
[[Read-only right moving Turing machines|Read-only, right-moving Turing machines]] are equivalent to [[Deterministic finite automaton|DFAs]] (as well as [[Nondeterministic finite automaton|NFAs]] by conversion using the [[NDFA to DFA conversion algorithm]]).
 +
 
 +
 
 +
 
 +
For practical and didactical intentions the equivalent [[register machine]] can be used as a usual [[Assembly language|assembly]] [[programming language]].
 +
 
 +
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.&nbsp;138)
 +
 
 +
图灵(1936)没有进一步阐述，除了在一个脚注中，他描述了如何使用一台机器“找到[希尔伯特]微积分的所有可证明的公式” ，而不是使用选择机器。他“假设总是在两种可能性0和1之间做出选择。每个证明将由一系列选项决定，i < sub > 1 </sub > ，i < sub > 2 </sub > ，... ，i < sub > n </sub > (i < sub > 1 </sub > 1 </sub > = 0或1，i < sub > 2 </sub > = 0或1，... ，i < sub > n </sub > = 0或1) ，因此数字2 < sup > n </sup > i </sup > 1 </sub > 2 </sub > n </sub > 2 </sub > 2 </sub > 2 </sub > 2 < n-2/> </2/> + i < i < </sub > 完全决定了证明。自动机器依次进行证明1，证明2，证明3，... ”(脚注‡ ，无法判定，第138页)
 +
 
 +
 
 +
 
 +
An interesting question is whether the computation model represented by concrete [[programming languages]] is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, [[ANSI C]] is not Turing-equivalent, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called ''pointers'', is accessible inside the language. However, other programming languages like [[Pascal (programming language)|Pascal]] do not have this feature, which allows them to be Turing complete in principle.
 +
 
 +
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.
 +
 
 +
这确实是一种技术，通过这种技术，一个确定性的(例如，a -)图灵机可以用来模拟一个不确定的图灵机的动作; 图灵在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。
 +
 
 +
It is just Turing complete in principle, as [[memory allocation]] in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot.
 +
 
 +
 
 +
 
 +
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.&nbsp;166–168).
 +
 
 +
甲骨文机器或 o-machine 是一种图灵机器，它将计算暂停在“ o”状态，同时，为了完成计算，它“等待”“甲骨文”的决定——一个未指定的实体” ，除了说它不可能是一台机器”(图灵(1939) ，The undecutable，p. 166-168)。
 +
 
 +
==Choice c-machines, oracle o-machines==
 +
 
 +
Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":
 +
 
 +
 
 +
 
 +
{{quote|...whose motion is only partially determined by the configuration ... When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems.|''The Undecidable'', p. 118}}
 +
 
 +
 
 +
 
 +
An implementation of a Turing machine
 +
 
 +
图灵机的一种实现
 +
 
 +
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.&nbsp;138)
 +
 
 +
As Turing wrote in The Undecidable, p.&nbsp;128 (italics added):
 +
 
 +
正如图灵在《无法判定》一书中所写，第128页(斜体) :
 +
 
 +
 
 +
 
 +
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 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”简称为计算模型。戴维斯(2000)的基本理论突破，导致了储存程式计算机的概念。
 +
 
 +
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.&nbsp;166–168).
 +
 
 +
 
 +
 
 +
==Universal Turing machines==
 +
 
 +
{{Main|Universal Turing machine}}
 +
 
 +
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)
 +
 
 +
在计算复杂度方面，一个多磁带通用图灵机只需要比它模拟的机器的对数因子慢一些。这个结果是在1966年由 F.C.Hennie 和 R.e. Stearns 获得的。(Arora and Barak，2009，定理1.9)
 +
 
 +
 
 +
 
 +
[[File:Model of a Turing machine.jpg|thumb|An implementation of a Turing machine]]
 +
 
 +
As Turing wrote in ''The Undecidable'', p.&nbsp;128 (italics added):
 +
 
 +
A Turing machine realization using [[Lego pieces]]
 +
 
 +
使用[[乐高零件]]实现图灵机
 +
 
 +
{{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'''.}}
 +
 
 +
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.
 +
 
 +
人们常说，图灵机不同于简单的自动机，它和真正的机器一样强大，能够执行真正的程序所能执行的任何操作。在这个陈述中被忽略的是，因为一个真实的机器只能有有限数量的配置，这个“真实的机器”实际上只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。
 +
 
 +
 
 +
 
 +
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]].
 +
 
 +
There are a number of ways to explain why Turing machines are useful models of real computers:
 +
 
 +
有很多方法可以解释为什么图灵机是真正计算机的有用模型:
 +
 
 +
 
 +
 
 +
{{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}}
 +
 
 +
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.&nbsp;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 和 Ullman p. 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.
 +
 
 +
区别仅仅在于图灵机操作无限量数据的能力。然而，在有限的时间内，图灵机(就像真正的机器)只能处理有限数量的数据。
 +
 
 +
In terms of [[Computational complexity theory|computational complexity]], a multi-tape universal Turing machine need only be slower by [[logarithm]]ic 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)
 +
 
 +
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.
 +
 
 +
使用简单的抽象模型描述真实机器程序通常比使用图灵机描述复杂得多。例如，一台描述算法的图灵机可能有几百种状态，而给定实际机器上的等价确定有限状态自动机(DFA)有千万亿。这使得 DFA 表示法无法进行分析。
 +
 
 +
==Comparison with real machines==
 +
 
 +
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.
 +
 
 +
图灵机描述的算法与它们使用的内存量无关。任何当前的机器所拥有的内存都是有限的，但是这个限制随着时间的推移可以任意上升。图灵机允许我们对算法做出永恒的陈述(理论上) ，而不管传统计算机体系结构的进步如何。
 +
 
 +
[[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces]]
 +
 
 +
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).
 +
 
 +
图灵机简化了算法的陈述。在与图灵等价的抽象机器上运行的算法通常比在真实机器上运行的算法更通用，因为它们具有任意精度的可用数据类型，而且从不需要处理意外情况(包括但不限于内存耗尽)。
 +
 
 +
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.
 +
 
 +
 
 +
 
 +
An experimental prototype of a Turing machine
 +
 
 +
图灵机的实验样机
 +
 
 +
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.&nbsp;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.
 +
 
 +
# 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.
 +
 
 +
# 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.
 +
 
 +
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 计算模型而不是图灵机模型时，这种算法的执行速度更快。
 +
 
 +
# 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]]).
 +
 
 +
 
 +
 
 +
[[File:Turingmachine.jpg|thumb|An experimental prototype of a Turing machine]]
 +
 
 +
 
 +
 
 +
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的本地存储创建进程，并同时发送停止和继续消息。当它接收到一条 go 消息时，它将其计数增加1，并发送一条 go 消息。当它接收到一个停止消息时，它在本地存储器中停止运行，并显示一个无界数字
 +
 
 +
===Limitations of Turing machines===
 +
 
 +
 
 +
 
 +
====Computational complexity theory====
 +
 
 +
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.
 +
 
 +
在计算机的早期，计算机的使用通常局限于批处理，也就是说，非交互式任务，每个输出数据来自给定的输入数据。可计算性理论研究从输入到输出的函数的可计算性，图灵机就是为此而发明的。
 +
 
 +
{{further|Computational complexity theory}}
 +
 
 +
 
 +
 
 +
Since the 1970s, 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 I/O automata are usually preferred.
 +
 
 +
自20世纪70年代以来，交互式使用计算机变得越来越普遍。原则上，通过让外部代理程序读取磁带并同时写入磁带来建模是可能的，但这很少与交互实际发生的方式相匹配; 因此，在描述交互性时，通常首选 I/O 自动机这样的替代程序。
 +
 
 +
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.
 +
 
 +
 
 +
 
 +
====Concurrency====
 +
 
 +
{{Unreferenced section|date=April 2015}}
 +
 
 +
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.)
 +
 
 +
They were described in 1936 by Alan Turing.
 +
 
 +
阿兰 · 图灵在1936年描述了它们。
 +
 
 +
 
 +
 
 +
====Interaction====
 +
 
 +
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.
 +
 
 +
Robin Gandy (1919–1995)—a student of Alan Turing (1912–1954), and his lifelong friend—traces the lineage of the notion of "calculating machine" back to Charles Babbage (circa 1834) and actually proposes "Babbage's Thesis":
 +
 
 +
Robin Gandy (1919-1995)是 Alan Turing (1912-1954)的学生，也是他一生的朋友，他将“机械式计算器”的概念追溯到 Charles Babbage (大约1834年) ，并提出了“ Babbage’s Thesis” :
 +
 
 +
 
 +
 
 +
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.
 +
 
 +
 
 +
 
 +
==History==
 +
 
 +
Gandy's analysis of Babbage's Analytical Engine describes the following five operations (cf. p.&nbsp;52–53):
 +
 
 +
甘迪对巴贝奇的分析机的分析描述了以下五个操作(参见。P. 52-53) :
 +
 
 +
{{See also|Algorithm|Church–Turing thesis}}
 +
 
 +
The arithmetic functions +, −, ×, where − indicates "proper" subtraction  0}} if .
 +
 
 +
算术函数 + ,-，× ，其中-表示“正确的”减法0}如果。
 +
 
 +
 
 +
 
 +
Any sequence of operations is an operation.
 +
 
 +
任何操作序列都是一个操作。
 +
 
 +
They were described in 1936 by [[Alan Turing]].
 +
 
 +
Iteration of an operation (repeating n times an operation P).
 +
 
 +
操作的迭代(重复 n 次操作 p)。
 +
 
 +
 
 +
 
 +
Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
 +
 
 +
条件迭代(以测试 t 的“成功”为条件重复 n 次操作 p)。
 +
 
 +
===Historical background: computational machinery===
 +
 
 +
Conditional transfer (i.e., conditional "goto").
 +
 
 +
有条件转移(即有条件的“ goto”)。
 +
 
 +
[[Robin Gandy]] (1919–1995)—a student of Alan Turing (1912–1954), and his lifelong friend—traces the lineage of the notion of "calculating machine" back to [[Charles Babbage]] (circa 1834) and actually proposes "Babbage's Thesis":
 +
 
 +
 
 +
 
 +
Gandy states that "the functions which can be calculated by (1), (2), and (4) are precisely those which are Turing computable." (p.&nbsp;53). He cites other proposals for "universal calculating machines" including those of Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937). However:
 +
 
 +
甘迪指出: “可由(1)、(2)和(4)计算的函数恰恰是图灵可计算的函数。”(p. 53).他引用了其他关于“通用计算机器”的提议，包括珀西 · 卢德盖特(1909年)、莱昂纳多 · 托雷斯 · 奎维多(1914年)、莫里斯 · d’奥卡涅(1922年)、路易斯 · 库夫尼纳尔(1933年)、万尼瓦尔 · 布什(1936年)、霍华德 · 艾肯(1937年)。然而:
 +
 
 +
{{quote|''That the whole of development and operations of analysis are now capable of being executed by machinery''.|(italics in Babbage as cited by Gandy, p. 54)}}
 +
 
 +
 
 +
 
 +
Gandy's analysis of Babbage's [[Analytical Engine]] describes the following five operations (cf. p.&nbsp;52–53):
 +
 
 +
# The arithmetic functions +, −, ×, where − indicates "proper" subtraction {{nowrap|''x'' − ''y'' {{=}} 0}} if {{nowrap|''y'' ≥ ''x''}}.
 +
 
 +
# Any sequence of operations is an operation.
 +
 
 +
With regard to Hilbert's problems posed by the famous mathematician David Hilbert in 1900, an aspect of problem #10 had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for #10 is as follows:
 +
 
 +
至于著名数学家大卫 · 希尔伯特在1900年提出的希尔伯特问题，第10号问题的一个方面在被精确设计之前已经漂浮了近30年。希尔伯特对 # 10的原始表达如下:
 +
 
 +
# Iteration of an operation (repeating n times an operation P).
 +
 
 +
# Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
 +
 
 +
{{quote|10. Determination of the solvability of a Diophantine equation. Given a Diophantine equation with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
 +
 
 +
{引用 | 10。丢番图方程可解性的测定。给定一个具有任意数量未知量和有理整系数的丢番图方程: 设计一个过程，根据这个过程可以在有限数量的运算中确定该方程是否在有理整数中是可解的。
 +
 
 +
# Conditional transfer (i.e., conditional "[[goto]]").
 +
 
 +
 
 +
 
 +
The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.|quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008}}
 +
 
 +
当我们知道一个程序允许任何给定的逻辑表达式通过有限多个操作来决定其有效性或可满足性时，可判定性问题[一阶逻辑的决策问题]就得到了解决..。可判定性必须被认为是数理逻辑的主要问题。2008年，德尔肖维茨和古列维奇引用了这个翻译和德文原文
 +
 
 +
Gandy states that "the functions which can be calculated by (1), (2), and (4) are precisely those which are [[Turing computable]]." (p.&nbsp;53). He cites other proposals for "universal calculating machines" including those of [[Percy Ludgate]] (1909), [[Leonardo Torres y Quevedo]] (1914), [[Maurice d'Ocagne]] (1922), [[Louis Couffignal]] (1933), [[Vannevar Bush]] (1936), [[Howard Aiken]] (1937). However:
 +
 
 +
 
 +
 
 +
By 1922, this notion of "Entscheidungsproblem" had developed a bit, and H. Behmann stated that
 +
 
 +
到了1922年，这个“可判定性”的概念已经发展了一些，h. Behmann 说
 +
 
 +
{{quote|… the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized…|Gandy p. 55}}
 +
 
 +
 
 +
 
 +
{{quote|...&nbsp;most general form of the Entscheidungsproblem [is] as follows:
 +
 
 +
{{引用 | ... 可判定性的一般形式如下:
 +
 
 +
===The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900===
 +
 
 +
<blockquote>A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion ...</blockquote>|Gandy p. 57, quoting Behmann}}
 +
 
 +
需要一个相当明确的、普遍适用的处方，这个处方将允许人们在有限的步骤中决定一个给定的纯粹逻辑断言的真实性或虚假性... ..
 +
 
 +
With regard to [[Hilbert's problems]] posed by the famous mathematician [[David Hilbert]] in 1900, an aspect of problem #10 had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for #10 is as follows:
 +
 
 +
 
 +
 
 +
{{quote|'''10. Determination of the solvability of a Diophantine equation'''. Given a [[Diophantine equation]] with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
 +
 
 +
 
 +
 
 +
By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete ... Second, was mathematics consistent ... And thirdly, was mathematics decidable?" (Hodges p.&nbsp;91, Hawking p.&nbsp;1121). The first two questions were answered in 1930 by Kurt Gödel at the very same meeting where Hilbert delivered his retirement speech (much to the chagrin of Hilbert); the third—the Entscheidungsproblem—had to wait until the mid-1930s.
 +
 
 +
到了1928年的国际数学家大会，希尔伯特把他的问题提得非常精确。第一，数学是完整的吗? 第二，数学是一致的吗? 第三，数学是可判定的吗? ”(Hodges p. 91，Hawking p. 1121).1930年，在希尔伯特发表退休演讲的同一次会议上，库尔特 · 哥德尔(Kurt Gödel)回答了前两个问题(这让希尔伯特颇为懊恼) ; 而第三个问题——协商问题——不得不等到上世纪30年代中期。
 +
 
 +
The Entscheidungsproblem [decision problem for [[first-order logic]]] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.|quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008}}
 +
 
 +
 
 +
 
 +
The problem was that an answer first required a precise definition of "definite general applicable prescription", which Princeton professor Alonzo Church would come to call "effective calculability", and in 1928 no such definition existed. But over the next 6–7 years Emil Post developed his definition of a worker moving from room to room writing and erasing marks per a list of instructions (Post 1936), as did Church and his two students Stephen Kleene and J. B. Rosser by use of Church's lambda-calculus and Gödel's recursion theory (1934). Church's paper (published 15 April 1936) showed that the Entscheidungsproblem was indeed "undecidable" and beat Turing to the punch by almost a year (Turing's paper submitted 28 May 1936, published January 1937). In the meantime, Emil Post submitted a brief paper in the fall of 1936, so Turing at least had priority over Post. While Church refereed Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that Church's lambda-calculus and his machines would compute the same functions.
 +
 
 +
问题在于，首先需要对“明确的一般适用处方”作出精确的定义，普林斯顿大学教授阿隆佐 · 丘奇将其称之为“有效可计算性” ，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特(Emil Post)定义了一个从一个房间走到另一个房间的工人，他在一系列指令中擦去了字迹(1936年以后) ，丘奇和他的两个学生斯蒂芬•克莱恩(Stephen Kleene)和 j。B. Rosser 使用 Church 的 lambda 微积分和哥德尔的可计算性理论。丘奇的论文(发表于1936年4月15日)表明，可判定性确实是“无法判定的” ，几乎用了一年时间击败了图灵(图灵于1936年5月28日提交的论文，发表于1937年1月)。与此同时，埃米尔 · 波斯特在1936年秋天提交了一份简短的论文，因此图灵至少比波斯特有优先权。当丘奇审阅图灵的论文时，图灵有时间研究丘奇的论文，并在附录中草拟了一个证据，证明丘奇的 λ 微积分和他的机器可以计算相同的函数。
 +
 
 +
By 1922, this notion of "[[Entscheidungsproblem]]" had developed a bit, and [[Heinrich Behmann|H. Behmann]] stated that
 +
 
 +
 
 +
 
 +
{{quote|...&nbsp;most general form of the Entscheidungsproblem [is] as follows:
 +
 
 +
<blockquote>A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion ...</blockquote>|Gandy p. 57, quoting Behmann}}
 +
 
 +
And Post had only proposed a definition of calculability and criticized Church's "definition", but had proved nothing.
 +
 
 +
波斯特只是提出了一个可计算性的定义，并批评了丘奇的“定义” ，但什么也没有证明。
 +
 
 +
{{quote|Behmann remarks that ... the general problem is equivalent to the problem of deciding which mathematical propositions are true.|''ibid.''}}
 +
 
 +
{{quote|If one were able to solve the Entscheidungsproblem then one would have a "procedure for solving many (or even all) mathematical problems".|''ibid.'', p. 92}}
 +
 
 +
 
 +
 
 +
In the spring of 1935, Turing as a young Master's student at King's College Cambridge, UK, took on the challenge; he had been stimulated by the lectures of the logician M. H. A. Newman "and learned from them of Gödel's work and the Entscheidungsproblem ... Newman used the word 'mechanical' ... In his obituary of Turing 1955 Newman writes:
 +
 
 +
1935年春天，图灵作为英国剑桥国王学院的一名年轻的硕士生接受了这个挑战，他受到逻辑学家 m. h. a. Newman 的演讲的鼓舞，从他们那里学到了哥德尔的作品和可判定性... ..。在图灵1955年的讣告中，纽曼写道:
 +
 
 +
By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics ''[[Completeness (logic)|complete]]'' ... Second, was mathematics ''[[Consistency proof|consistent]]'' ... And thirdly, was mathematics ''[[Decidability (logic)|decidable]]''?" (Hodges p.&nbsp;91, Hawking p.&nbsp;1121). The first two questions were answered in 1930 by [[Kurt Gödel]] at the very same meeting where Hilbert delivered his retirement speech (much to the chagrin of Hilbert); the third—the Entscheidungsproblem—had to wait until the mid-1930s.
 +
 
 +
 
 +
 
 +
The problem was that an answer first required a precise definition of "''definite general applicable prescription''", which Princeton professor [[Alonzo Church]] would come to call "[[effective calculability]]", and in 1928 no such definition existed. But over the next 6–7 years [[Emil Post]] developed his definition of a worker moving from room to room writing and erasing marks per a list of instructions (Post 1936), as did Church and his two students [[Stephen Kleene]] and [[J. B. Rosser]] by use of Church's [[lambda-calculus]] and Gödel's [[recursion theory]] (1934). Church's paper (published 15 April 1936) showed that the Entscheidungsproblem was indeed "undecidable" and beat Turing to the punch by almost a year (Turing's paper submitted 28 May 1936, published January 1937). In the meantime, Emil Post submitted a brief paper in the fall of 1936, so Turing at least had priority over Post. While Church refereed Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that Church's lambda-calculus and his machines would compute the same functions.
 +
 
 +
 
 +
 
 +
Gandy states that:
 +
 
 +
甘迪表示:
 +
 
 +
{{quote|But what Church had done was something rather different, and in a certain sense weaker. ... the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church's demonstration.|Hodges p. 112}}
 +
 
 +
 
 +
 
 +
And Post had only proposed a definition of [[Church–Turing thesis|calculability]] and criticized Church's "definition", but had proved nothing.
 +
 
 +
 
 +
 
 +
While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges p.&nbsp;96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD thesis, titled "Systems of Logic Based on Ordinals", contains the following definition of "a computable function":
 +
 
 +
虽然甘迪认为纽曼的上述言论是“误导性的” ，但并非所有人都赞同这一观点。图灵一生都对机器有着浓厚的兴趣: “艾伦从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他完全可以从问自己，称打字机为‘机械’是什么意思开始。”。在普林斯顿攻读博士学位期间，图灵构建了一个布尔逻辑乘数(见下文)。他的博士论文题为“基于序数的逻辑系统” ，包含了以下“可计算函数”的定义:
 +
 
 +
===Alan Turing's a-machine===
 +
 
 +
In the spring of 1935, Turing as a young Master's student at [[King's College Cambridge]], [[UK]], took on the challenge; he had been stimulated by the lectures of the logician [[M. H. A. Newman]] "and learned from them of Gödel's work and the Entscheidungsproblem ... Newman used the word 'mechanical' ... In his obituary of Turing 1955 Newman writes:
 +
 
 +
 
 +
 
 +
{{quote|To the question 'what is a "mechanical" process?' Turing returned the characteristic answer 'Something that can be done by a machine' and he embarked on the highly congenial task of analysing the general notion of a computing machine.|Gandy, p. 74}}
 +
 
 +
When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes created by encryption machines called "The Enigma"; he also became involved in the design of the ACE (Automatic Computing Engine), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the EDVAC [the USA's initiative], but in his own universal machine" (Hodges p.&nbsp;318). Arguments still continue concerning the origin and nature of what has been named by Kleene (1952) Turing's Thesis. But what Turing did prove with his computational-machine model appears in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (1937):
 +
 
 +
当图灵回到英国后，他最终共同负责破解由加密机制造的德国秘密代码“谜” ; 他还参与了 ACE (自动计算机引擎)的设计，“(图灵的) ACE 提案实际上是独立的，它的根基不在于 EDVAC (美国的倡议) ，而在于他自己的通用机器”(第318页)。关于克莱恩(1952)图灵命名的东西的起源和性质的争论仍在继续。但是图灵用他的计算机模型证明的东西出现在他的论文《论可计算的数字，以及对可判定性的应用》(1937)中:
 +
 
 +
 
 +
 
 +
Gandy states that:
 +
 
 +
 
 +
 
 +
{{quote|I suppose, but do not know, that Turing, right from the start of his work, had as his goal a proof of the undecidability of the Entscheidungsproblem. He told me that the 'main idea' of the paper came to him when he was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis of computation or his realization that there was a universal machine, and so a [[Cantor's diagonal argument|diagonal argument]] to prove unsolvability.|''ibid.'', p. 76}}
 +
 
 +
Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".
 +
 
 +
图灵的例子(他的第二个证明) : 如果一个人要求一个通用程序告诉我们: “这台机器曾经打印过0吗? ” ，这个问题是“无法判定的”。
 +
 
 +
 
 +
 
 +
While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges p.&nbsp;96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD thesis, titled "[[Systems of Logic Based on Ordinals]]", contains the following definition of "a computable function":
 +
 
 +
 
 +
 
 +
In 1937, while at Princeton working on his PhD thesis, Turing built a digital (Boolean-logic) multiplier from scratch, making his own electromechanical relays (Hodges p.&nbsp;138). "Alan's task was to embody the logical design of a Turing machine in a network of relay-operated switches ..." (Hodges p.&nbsp;138). While Turing might have been just initially curious and experimenting, quite-earnest work in the same direction was going in Germany (Konrad Zuse (1938)), and in the United States (Howard Aiken) and George Stibitz (1937); the fruits of their labors were used by both the Axis and Allied militaries in World War II (cf. Hodges p.&nbsp;298–299). In the early to mid-1950s Hao Wang and Marvin Minsky reduced the Turing machine to a simpler form (a precursor to the Post–Turing machine of Martin Davis); simultaneously European researchers were reducing the new-fangled electronic computer to a computer-like theoretical object equivalent to what was now being called a "Turing machine". In the late 1950s and early 1960s, the coincidentally parallel developments of Melzak and Lambek (1961), Minsky (1961), and Shepherdson and Sturgis (1961) carried the European work further and reduced the Turing machine to a more friendly, computer-like abstract model called the counter machine; Elgot and Robinson (1964), Hartmanis (1971), Cook and Reckhow (1973) carried this work even further with the register machine and random-access machine models—but basically all are just multi-tape Turing machines with an arithmetic-like instruction set.
 +
 
 +
1937年，在普林斯顿写博士论文的时候，图灵从零开始制造了一个数字(布尔逻辑)乘法器，制造了他自己的机电式继电器(Hodges p. 138)。“艾伦的任务是在中继操作的开关网络中体现图灵机的逻辑设计... ”(Hodges p. 138)。虽然图灵最初可能只是好奇和试验，但是在德国(Konrad Zuse，1938年)和美国(Howard Aiken，1937年)都在朝着同一个方向努力，他们的劳动成果被轴心国和盟国的军队在二战中使用。Hodges p. 298-299).在20世纪50年代早期到中期，Hao Wang 和 Marvin Minsky 将图灵机简化为一种更简单的形式(它是 Martin Davis 的后图灵机的前身) ; 与此同时，欧洲研究人员将这种新型电子计算机简化为一种类似于计算机的理论物体，相当于现在所说的“图灵机”。在20世纪50年代后期和60年代初期，巧合地并行发展的 Melzak 和 Lambek (1961)、 Minsky (1961)和 Shepherdson and Sturgis (1961)进一步推进了欧洲的工作，并将图灵机简化为一个更友好的、类似计算机的抽象模型，称为计数器; Elgot 和 Robinson (1964)、 Hartmanis (1971)、 Cook 和 Reckhow (1973)将这项工作进一步推进到寄存器和随机存取机器模型ーー但基本上所有这些都只是带有类似指令集的多磁带算术机器。
 +
 
 +
{{quote|It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.|Turing (1939) in ''The Undecidable'', p. 160}}
 +
 
 +
 
 +
 
 +
When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes created by encryption machines called "The Enigma"; he also became involved in the design of the ACE ([[Automatic Computing Engine]]), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the [[EDVAC]] [the USA's initiative], but in his own universal machine" (Hodges p.&nbsp;318). Arguments still continue concerning the origin and nature of what has been named by Kleene (1952) [[Turing's Thesis]]. But what Turing ''did prove'' with his computational-machine model appears in his paper "[[On Computable Numbers, with an Application to the Entscheidungsproblem]]" (1937):
 +
 
 +
Today, the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating questions in the theory of computation. In particular, computational complexity theory makes use of the Turing machine:
 +
 
 +
今天，计数器、寄存器和随机存取机器以及它们的祖先图灵机仍然是研究计算理论问题的理论家们的首选模型。特别是，计算复杂性理论使用了图灵机:
 +
 
 +
 
 +
 
 +
{{quote|[that] the Hilbert Entscheidungsproblem can have no solution ... I propose, therefore to show that there can be no general process for determining whether a given formula U of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.|from Turing's paper as reprinted in ''The Undecidable'', p. 145}}
 +
 
 +
{{quote|Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models have obtained a dominant position in machine-based complexity theory:
 +
 
 +
{{ quote | 取决于人们喜欢在计算中操纵的对象(如非负整数或字母数字字符串) ，两个模型在机器复杂性理论中占据了主导地位:
 +
 
 +
 
 +
 
 +
<blockquote>the off-line multitape Turing machine..., which represents the standard model for string-oriented computation, and
 +
 
 +
离线多带图灵机... ，它代表了面向字符串计算的标准模型，以及
 +
 
 +
Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".
 +
 
 +
 
 +
 
 +
the random access machine (RAM) as introduced by Cook and Reckhow ..., which models the idealized Von Neumann style computer.</blockquote>|van Emde Boas 1990:4}}
 +
 
 +
由 Cook 和 Reckhow... 引入的随机存取机(RAM) ，它模拟了理想化的冯诺依曼式计算机。1990:4}
 +
 
 +
===1937–1970: The "digital computer", the birth of "computer science"===
 +
 
 +
In 1937, while at Princeton working on his PhD thesis, Turing built a digital (Boolean-logic) multiplier from scratch, making his own electromechanical relays (Hodges p.&nbsp;138). "Alan's task was to embody the logical design of a Turing machine in a network of relay-operated switches ..." (Hodges p.&nbsp;138). While Turing might have been just initially curious and experimenting, quite-earnest work in the same direction was going in Germany ([[Konrad Zuse]] (1938)), and in the United States ([[Howard Aiken]]) and [[George Stibitz]] (1937); the fruits of their labors were used by both the Axis and Allied militaries in [[World War II]] (cf. Hodges p.&nbsp;298–299). In the early to mid-1950s [[Hao Wang (academic)|Hao Wang]] and [[Marvin Minsky]] reduced the Turing machine to a simpler form (a precursor to the [[Post–Turing machine]] of [[Martin Davis (mathematician)|Martin Davis]]); simultaneously European researchers were reducing the new-fangled [[electronic computer]] to a computer-like theoretical object equivalent to what was now being called a "Turing machine". In the late 1950s and early 1960s, the coincidentally parallel developments of Melzak and Lambek (1961), Minsky (1961), and Shepherdson and Sturgis (1961) carried the European work further and reduced the Turing machine to a more friendly, computer-like abstract model called the [[counter machine]]; Elgot and Robinson (1964), Hartmanis (1971), Cook and Reckhow (1973) carried this work even further with the [[register machine]] and [[random-access machine]] models—but basically all are just multi-tape Turing machines with an arithmetic-like instruction set.
 +
 
 +
 
 +
 
 +
===1970–present: the Turing machine as a model of computation===
 +
 
 +
Today, the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating questions in the [[theory of computation]]. In particular, [[computational complexity theory]] makes use of the Turing machine:
 +
 
 +
 
 +
 
 +
{{quote|Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models have obtained a dominant position in machine-based complexity theory:
 +
 
 +
<blockquote>''the off-line multitape Turing machine''..., which represents the standard model for string-oriented computation, and
 +
 
 +
 
 +
 
 +
the ''random access machine (RAM)'' as introduced by Cook and Reckhow ..., which models the idealized Von Neumann style computer.</blockquote>|van Emde Boas 1990:4}}
 +
 
 +
{{quote|Only in the related area of analysis of algorithms this role is taken over by the RAM model.|van Emde Boas 1990:16}}
 +
 
 +
 
 +
 
 +
==See also==
 +
 
 +
{{divcol|colwidth=22em}}
 +
 
 +
* [[Arithmetical hierarchy]]
 +
 
 +
* [[Bekenstein bound]], showing the impossibility of infinite-tape Turing machines of finite size and bounded energy
 +
 
 +
* [[BlooP and FlooP]]
 +
 
 +
* [[Busy beaver]]
 +
 
 +
* [[Chaitin constant]] or [[Omega (computer science)]] for information relating to the halting problem
 +
 
 +
* [[Chinese Room]]
 +
 
 +
* [[Conway's Game of Life]], a Turing-complete cellular automaton
 +
 
 +
* [[Digital infinity]]
 +
 
 +
* [[The Emperor's New Mind]]
 +
 
 +
* [[Enumerator (in theoretical computer science)]]
 +
 
 +
* [[Genetix]]
 +
 
 +
* ''[[Gödel, Escher, Bach: An Eternal Golden Braid]]'', a famous book that discusses, among other topics, the Church–Turing thesis
 +
 
 +
* [[Halting problem]], for more references
 +
 
 +
* [[Harvard architecture]]
 +
 
 +
* [[Imperative programming]]
 +
 
 +
* [[Langton's ant]] and [[Turmite]]s, simple two-dimensional analogues of the Turing machine
 +
 
 +
* [[List of things named after Alan Turing]]
 +
 
 +
* [[Modified Harvard architecture]]
 +
 
 +
* [[Probabilistic Turing machine]]
 +
 
 +
* [[Random-access Turing machine]]
 +
 
 +
* [[Quantum Turing machine]]
 +
 
 +
* [[Claude Shannon]], another leading thinker in information theory
 +
 
 +
* [[Turing machine examples]]
 +
 
 +
* [[Turing switch]]
 +
 
 +
* [[Turing tarpit]], any computing system or language that, despite being Turing complete, is generally considered useless for practical computing
 +
 
 +
* [[Unorganized machine]], for Turing's very early ideas on neural networks
 +
 
 +
* [[Von Neumann architecture]]
 +
 
 +
 
 +
 
 +
{{divcol-end}}
 +
 
 +
 
 +
 
 +
==Notes==
 +
 
 +
<references responsive="0" />
 +
 
 +
 
 +
 
 +
==References==
 +
 
 +
{{Reflist}}
 +
 
 +
 
 +
 
 +
===Primary literature, reprints, and compilations===
 +
 
 +
* B. [[Jack Copeland]] ed. (2004), ''The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma,'' Clarendon Press (Oxford University Press), Oxford UK, {{isbn|0-19-825079-7}}. Contains the Turing papers plus a draft letter to [[Emil Post]] re his criticism of "Turing's convention", and Donald W. Davies' ''Corrections to Turing's Universal Computing Machine''
 +
 
 +
* [[Martin Davis (mathematician)|Martin Davis]] (ed.) (1965), ''The Undecidable'', Raven Press, Hewlett, NY.
 +
 
 +
* Emil Post (1936), "Finite Combinatory Processes—Formulation 1", ''Journal of Symbolic Logic'', 1, 103–105, 1936. Reprinted in ''The Undecidable'', pp.&nbsp;289ff.
 +
 
 +
* Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", ''Journal of Symbolic Logic'', vol. 12, pp.&nbsp;1–11. Reprinted in ''The Undecidable'', pp.&nbsp;293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on [[Turing's proof|Turing's first and second proofs]].
 +
 
 +
* {{Cite journal | last= Turing | first= A.M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–265 | doi= 10.1112/plms/s2-42.1.230 }} (and {{Cite journal | last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 | issue = 6 }}). Reprinted in many collections, e.g. in ''The Undecidable'', pp.&nbsp;115–154; available on the web in many places.
 +
 
 +
* Alan Turing, 1948, "Intelligent Machinery."  Reprinted in "Cybernetics: Key Papers." Ed. C.R. Evans and A.D.J. Robertson.  Baltimore: University Park Press, 1968. p.&nbsp;31.  Reprinted in {{Cite journal | doi = 10.1093/philmat/4.3.256| title = Intelligent Machinery, A Heretical Theory| journal = Philosophia Mathematica| volume = 4| issue = 3| pages = 256–260| year = 1996| last1 = Turing | first1 = A. M.}}
 +
 
 +
* F. C. Hennie and [[R. E. Stearns]]. ''Two-tape simulation of multitape Turing machines''. [[JACM]], 13(4):533–546, 1966.
 +
 
 +
 
 +
 
 +
===Computability theory===
 +
 
 +
* {{cite book | last = Boolos | first = George |author2=Richard Jeffrey  | title = Computability and Logic | url = https://archive.org/details/computabilitylog0000bool_r8y9 | url-access = registration | edition = 3rd | publisher = Cambridge University Press | location = Cambridge UK | origyear = 1989| year = 1999| isbn = 0-521-20402-X }}
 +
 
 +
* {{cite book | last = Boolos | first = George |author2=John Burgess |author3=Richard Jeffrey  | title = Computability and Logic | edition = 4th | publisher = Cambridge University Press | location = Cambridge UK | year = 2002 | isbn = 0-521-00758-5  }} Some parts have been significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" (cf. [[Register machine]]) and [[Computable function|recursive functions]], showing their equivalence.
 +
 
 +
* [[Taylor L. Booth]] (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX ''Turing Machines'' includes some recursion theory.
 +
 
 +
* {{cite book|author = Martin Davis | year = 1958| title = Computability and Unsolvability| publisher = McGraw-Hill Book Company, Inc, New York | author-link = Martin Davis (mathematician)}}. On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
 +
 
 +
* {{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker|author3-link=Elaine Weyuker | title = Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994 | isbn = 0-12-206382-1}}
 +
 
 +
* {{cite book|last =Hennie |first = Fredrick | year = 1977| title = Introduction to Computability| publisher = Addison–Wesley, Reading, Mass|id=QA248.5H4 1977 }}. On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual 'code'.
 +
 
 +
* {{cite book|author = [[John Hopcroft]] and [[Jeffrey Ullman]] | year = 1979| title = Introduction to Automata Theory, Languages, and Computation| title-link = Introduction to Automata Theory, Languages, and Computation| publisher = Addison–Wesley, Reading Mass| edition = 1st | isbn = 0-201-02988-X}} Centered around the issues of machine-interpretation of "languages", NP-completeness, etc.
 +
 
 +
* {{cite book | last = Hopcroft | first = John E.|author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title = Introduction to Automata Theory, Languages, and Computation| edition = 2nd | publisher = Addison–Wesley | location = Reading Mass | year = 2001 | isbn = 0-201-44124-1}} Distinctly different and less intimidating than the first edition.
 +
 
 +
* [[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North–Holland Publishing Company, Amsterdam Netherlands, 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII ''Computable functions'' is on Turing machine proofs of computability of recursive functions, etc.
 +
 
 +
* {{cite book | last = Knuth | first = Donald E. | authorlink = Donald Knuth | title = Volume 1/Fundamental Algorithms: The Art of computer Programming| edition = 2nd | publisher = Addison–Wesley Publishing Company| location = Reading, Mass.| year = 1973 }}. With reference to the role of Turing machines in the development of computation (both hardware and software) see 1.4.5 ''History and Bibliography'' pp.&nbsp;225ff and 2.6 ''History and Bibliography''pp.&nbsp;456ff.
 +
 
 +
* [[Zohar Manna]], 1974, ''[[Mathematical Theory of Computation]]''. Reprinted, Dover, 2003. {{isbn|978-0-486-43238-0}}
 +
 
 +
* [[Marvin Minsky]], ''Computation: Finite and Infinite Machines'', Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny.
 +
 
 +
* {{cite book|author = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1| author-link = Christos Papadimitriou }} Chapter 2: Turing machines, pp.&nbsp;19–56.
 +
 
 +
* [[Hartley Rogers, Jr.]], ''Theory of Recursive Functions and Effective Computability'', The MIT Press, Cambridge MA, paperback edition 1987, original McGraw-Hill edition 1967, {{isbn|0-262-68052-1}} (pbk.)
 +
 
 +
* {{cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url = https://archive.org/details/introductiontoth00sips | author-link = Michael Sipser }} Chapter 3: The Church–Turing Thesis, pp.&nbsp;125–149.
 +
 
 +
* {{cite book | last = Stone | first = Harold S. | title = Introduction to Computer Organization and Data Structures| edition = 1st | publisher = McGraw–Hill Book Company | location = New York | year = 1972 | isbn = 0-07-061726-0 }}
 +
 
 +
* [[Peter van Emde Boas]] 1990, ''Machine Models and Simulations'', pp.&nbsp;3–66, in [[Jan van Leeuwen]], ed., ''Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity'', The MIT Press/Elsevier, [place?], {{isbn|0-444-88071-2}} (Volume A). QA76.H279 1990. Valuable survey, with 141 references.
 +
 
 +
 
 +
 
 +
===Church's thesis===
 +
 
 +
* {{cite journal |author=Nachum Dershowitz |author2=Yuri Gurevich  |date=September 2008 |title=A natural axiomatization of computability and proof of Church's Thesis |journal=Bulletin of Symbolic Logic |volume=14 |issue=3 |url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf |accessdate=2008-10-15}}
 +
 
 +
* {{cite book|author = Roger Penrose | origyear = 1989| year = 1990 | title = The Emperor's New Mind | publisher = Oxford University Press, New York| edition = 2nd | isbn = 0-19-851973-7| author-link = Roger Penrose}}
 +
 
 +
 
 +
 
 +
===Small Turing machines===
 +
 
 +
* Rogozhin, Yurii, 1998, "[https://web.archive.org/web/20050308141040/http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm A Universal Turing Machine with 22 States and 2 Symbols]", ''Romanian Journal of Information Science and Technology'', 1(3), 259–265, 1998. (surveys known results about small universal Turing machines)
 +
 
 +
* [[Stephen Wolfram]], 2002, [http://www.wolframscience.com/nksonline/page-707 ''A New Kind of Science''], Wolfram Media, {{isbn|1-57955-008-8}}
 +
 
 +
* Brunfiel, Geoff, [http://www.nature.com/news/2007/071024/full/news.2007.190.html Student snags maths prize], ''Nature'', October 24. 2007.
 +
 
 +
* Jim Giles (2007), [https://www.newscientist.com/article/dn12826-simplest-universal-computer-wins-student-25000.html Simplest 'universal computer' wins student $25,000], New Scientist, October 24, 2007.
 +
 
 +
* Alex Smith, [http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf Universality of Wolfram’s 2, 3 Turing Machine], Submission for the Wolfram 2, 3 Turing Machine Research Prize.
 +
 
 +
* Vaughan Pratt, 2007, "[http://cs.nyu.edu/pipermail/fom/2007-October/012156.html Simple Turing machines, Universality, Encodings, etc.]", FOM email list. October 29, 2007.
 +
 
 +
* Martin Davis, 2007, "[http://cs.nyu.edu/pipermail/fom/2007-October/012132.html Smallest universal machine]", and [http://cs.nyu.edu/pipermail/fom/2007-October/012145.html Definition of universal Turing machine] FOM email list. October 26–27, 2007.
 +
 
 +
* Alasdair Urquhart, 2007 "[http://cs.nyu.edu/pipermail/fom/2007-October/012140.html Smallest universal machine]", FOM email list. October 26, 2007.
 +
 
 +
* Hector Zenil (Wolfram Research), 2007 "[http://cs.nyu.edu/pipermail/fom/2007-October/012163.html smallest universal machine]", FOM email list. October 29, 2007.
 +
 
 +
* Todd Rowland, 2007, "[http://forum.wolframscience.com/showthread.php?s=&threadid=1472 Confusion on FOM]", Wolfram Science message board, October 30, 2007.
 +
 
 +
* Olivier and Marc RAYNAUD, 2014, [http://www.machinedeturing.com/ang_default.asp A programmable prototype to achieve Turing machines]" LIMOS Laboratory of Blaise Pascal University (Clermont-Ferrand in France).
 +
 
 +
 
 +
 
 +
===Other===
 +
 
 +
* {{cite book|author = Martin Davis | year = 2000| title = Engines of Logic: Mathematicians and the origin of the Computer| publisher = W. W. Norton & Company, New York| edition = 1st | isbn = 978-0-393-32229-3| author-link = Martin Davis (mathematician)}}
 +
 
 +
* [[Robin Gandy]], "The Confluence of Ideas in 1936", pp.&nbsp;51–102 in [[Rolf Herken]], see below.
 +
 
 +
* [[Stephen Hawking]] (editor), 2005, ''God Created the Integers: The Mathematical Breakthroughs that Changed History'', Running Press, Philadelphia, {{isbn|978-0-7624-1922-7}}. Includes Turing's 1936–1937 paper, with brief commentary and biography of Turing as written by Hawking.
 +
 
 +
* {{cite book | author = Rolf Herken | title = The Universal Turing Machine—A Half-Century Survey | publisher = Springer Verlag | isbn = 978-3-211-82637-9 | year = 1995}}
 +
 
 +
* [[Andrew Hodges]], ''[[Alan Turing: The Enigma]]'', [[Simon and Schuster]], New York. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
 +
 
 +
* {{cite book|author = Ivars Peterson | year = 1988| title = The Mathematical Tourist: Snapshots of Modern Mathematics|url = https://archive.org/details/mathematicaltour00pete |url-access = registration | publisher = W. H. Freeman and Company, New York| edition = 1st | isbn = 978-0-7167-2064-5 | author-link = Ivars Peterson}}
 +
 
 +
* [[Roger Penrose]], ''The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics'', [[Oxford University Press]], Oxford and New York, 1989 (1990 corrections), {{isbn|0-19-851973-7}}.
 +
 
 +
* {{cite book | author = Paul Strathern | title = Turing and the Computer—The Big Idea | publisher = Anchor Books/Doubleday | isbn = 978-0-385-49243-0 | year = 1997 | url = https://archive.org/details/turingcomputer00stra | author-link = Paul Strathern }}
 +
 
 +
* [[Hao Wang (academic)|Hao Wang]], "A variant to Turing's theory of computing machines", ''Journal of the Association for Computing Machinery'' (JACM) 4, 63–92 (1957).
 +
 
 +
* [[Charles Petzold]], [http://www.theannotatedturing.com/ Petzold, Charles, ''The Annotated Turing''], John Wiley & Sons, Inc., {{isbn|0-470-22905-5}}
 +
 
 +
* Arora, Sanjeev; Barak, Boaz, [http://www.cs.princeton.edu/theory/complexity/ "Complexity Theory: A Modern Approach"], Cambridge University Press, 2009, {{isbn|978-0-521-42426-4}}, section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
 +
 
 +
* {{cite journal |title=A note on turing machine computability of rule driven systems |date=December 1, 2005 |doi=10.1145/1107523.1107525 |issue=4 |volume=36 |pages=109–110 |journal=[[SIGACT News]] |first=Isaiah Pinchas |last=Kantorovitz|s2cid=31117713 }}
 +
 
 +
* Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: [http://researchprofiles.herts.ac.uk/portal/en/publications/on-undecidability-results-of-real-programming-languages(d3f3aac0-d9da-4756-a421-b4f9ae0cf95f).html "On Undecidability Results of Real Programming Languages"], In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, Oct. 2009.
 +
 
 +
 
 +
 
 +
==External links==
 +
 
 +
{{Commons category|Turing machines}}
 +
 
 +
* {{springer|title=Turing machine|id=p/t094460}}
 +
 
 +
* [http://plato.stanford.edu/entries/turing-machine/ Turing Machine] in the [[Stanford Encyclopedia of Philosophy]]
 +
 
 +
*[http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ Turing Machine Causal Networks] by Enrique Zeleny as part of the [[Wolfram Demonstrations Project]].
 +
 
 +
Category:1936 in computing
 +
 
 +
类别: 1936年
 +
 
 +
* {{curlie|Computers/Computer_Science/Theoretical/Automata_Theory/Turing_Machines|Turing Machines}}
 +
 
 +
Category:1937 in computing
 +
 
 +
类别: 1937年
 +
 
 +
 
 +
 
 +
Category:Educational abstract machines
 +
 
 +
类别: 教育摘要机器
 +
 
 +
 
 +
 
 +
Category:Theoretical computer science
 +
 
 +
类别: 理论计算机科学
 +
 
 +
{{Formal languages and grammars}}
 +
 
 +
Category:Alan Turing
 +
 
 +
分类: 阿兰 · 图灵
 +
 
 +
 
 +
 
 +
Category:Models of computation
 +
 
 +
类别: 计算模型
 +
 
 +
{{Authority control}}
 +
 
 +
Category:Formal methods
 +
 
 +
类别: 正式方法
   −
分类: 阿兰 · 图灵
     −
{{further|Computational complexity theory}}
  −
  −
Category:Models of computation
  −
  −
类别: 计算模型
  −
  −
  −
  −
Category:Formal methods
  −
  −
类别: 正式方法
  −
  −
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.
      
Category:Computability theory
 
Category:Computability theory
第1,799行： 第2,731行：  
类别: 可计算性理论
 
类别: 可计算性理论
   −
 
+
{{DEFAULTSORT:Turing machine}}
    
Category:English inventions
 
Category:English inventions
第1,805行： 第2,737行：  
类别: 英国发明
 
类别: 英国发明
   −
====Concurrency====
+
[[Category:Turing machine| ]]
    
Category:Automata (computation)
 
Category:Automata (computation)
第1,811行： 第2,743行：  
类别: 自动机(计算)
 
类别: 自动机(计算)
   −
{{Unreferenced section|date=April 2015}}
+
[[Category:1936 in computing]]
    
Category:Formal languages
 
Category:Formal languages
第1,817行： 第2,749行：  
类别: 正式语言
 
类别: 正式语言
   −
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.)
+
[[Category:1937 in computing]]
    
Category:Abstract machines
 
Category:Abstract machines
Moonscar
1,568

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/17215”

导航菜单