更改

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 name=":0">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 name=":1">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 name=":2">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 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.

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)(根据观察到的符号和机器自身在表中的状态)继续执行后续指令或停止计算。

机器在一个无限<ref name=":0" />大的存储磁带上运行，磁带被分割成若干个离散的“单元”。<ref name=":1" /> 机器将它的“头”定位在一个单元上，并“读取”或“扫描”<ref name=":2" /> 那里的符号。然后，根据符号和机器本身在用户指定指令的“有限表”中的现状，机器（i）将符号（例如，有限字母表中的一位数字或一个字母）写入单元（某些型号允许擦除符号或不写入字符），然后(ii)将磁带向左或向右移动一个单元格(有些模型允许不移动，有些模型允许移动磁头) ，然后(iii)(根据观察到的符号和机器自身在表中的状态)继续执行后续指令或停止计算。

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

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

In the 4-tuple models, erasing or writing a symbol (a_j1) and moving the head left or right (d_k) 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.

In the 4-tuple models, erasing or writing a symbol (a_j1) and moving the head left or right (d_k) 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)两个动作。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。

在四元组模型中，擦除或写入符号(a < sub > j1 )和向左或向右移动头(d < sub > k )被指定为单独的指令。该表告诉机器擦除或写入一个符号，或者(ib)向左或向右移动磁头，然后(ii)按照规定假定相同或新的状态，但不能在同一指令中同时进行(ia)和(ib)两个动作。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。

 

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_m listed immediately after the scanned symbol S_j:

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_m listed immediately after the scanned symbol S_j:

其他作者(Minsky(1967)第119页，霍普克罗夫特Hopcroft和乌尔曼Ullman(1979)第158页，斯通Stone(1972)第9页)采用了另一种约定，在扫描符号s </sub > j </sub > 之后立即列出新状态q </sub > m </sub > :

其他作者(Minsky(1967)第119页，霍普克罗夫特Hopcroft和乌尔曼Ullman(1979)第158页，斯通Stone(1972)第9页)采用了另一种约定，在扫描符号s j 之后立即列出新状态q m :

: (definition 2): '''(q_i, S_j, q_m, S_k/E/N, L/R/N)'''

: (definition 2): '''(q_i, S_j, q_m, S_k/E/N, L/R/N)'''

  (definition 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

  (definition 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

(定义2) : (q < sub > i </sub > ，s < sub > j </sub > ，q < sub > m </sub > ，s < sub > k </sub >/E/N，L/R/N)

(定义2) : (q < sub > i ，s < sub > j ，q < sub > m ，s < sub > k /E/N，L/R/N)

:: '''(''' current state '''q_i''' ''',''' symbol scanned '''S_j''' ''',''' new state '''q_m''' ''',''' print symbol '''S_k'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''')'''

:: '''(''' current state '''q_i''' ''',''' symbol scanned '''S_j''' ''',''' new state '''q_m''' ''',''' print symbol '''S_k'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''')'''

  ( current state q_i , symbol scanned S_j , new state q_m , print symbol S_k/erase E/none N , move_tape_one_square left L/right R/none N )

  ( current state q_i , symbol scanned S_j , new state q_m , print symbol S_k/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 >/擦除 E/无 n，move _ tape one _ square left L/right R/none n)

(当前状态 q <sub> i </sub > ，符号扫描 s < sub > j ，新状态 q < sub > m ，打印符号 s < sub > k /擦除 E/无 n，move _ tape one _ square left L/right R/none n)

For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.

For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.

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₀ = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S_k" 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:

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₀ = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S_k" 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:

在下表中，图灵最初的模型只允许前三行，他称之为 N1，N2，N3。参见图灵在The Undecidable一书中，第126页)。他通过命名第0个符号 s < sub > 0 </sub > = “ 擦除”或“ 空白”等，允许擦除“扫描方块”。但是，他不允许不打印，所以每条指令行都包括“打印符号 s < sub > k </sub > ”或“ 擦除”(参见Post（1947），The Undecidable，第300页中的脚注12 ）。这些缩写是图灵的(The Undecidable，第119页)。在图灵于1936-1937年发表原始论文之后，机器模型已经允许所有九种可能的五元组类型:

在下表中，图灵最初的模型只允许前三行，他称之为 N1，N2，N3。参见图灵在The Undecidable一书中，第126页)。他通过命名第0个符号 s < sub > 0 = “ 擦除”或“ 空白”等，允许擦除“扫描方块”。但是，他不允许不打印，所以每条指令行都包括“打印符号 s < sub > k ”或“ 擦除”(参见Post（1947），The Undecidable，第300页中的脚注12 ）。这些缩写是图灵的(The Undecidable，第119页)。在图灵于1936-1937年发表原始论文之后，机器模型已经允许所有九种可能的五元组类型:

{| class="wikitable" style="text-align: center"

{| class="wikitable" style="text-align: center"

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

[[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).|链接=Special:FilePath/State_diagram_3_state_busy_beaver_2B.svg]]

"3态穷忙"图灵机的有限状态表示。每个圆圈代表表的一个 "状态"--一个 "m-配置 "或 "指令"。状态转换的 "方向 "用箭头表示。出状态附近的标签(如0/P,R)(在箭头的 "尾部")指定了引起特定转换的扫描符号(如0)，后面是斜线/，接着是机器的后续 "行为"，如 "P打印 "然后移动磁带 "R右"。没有普遍接受的格式存在。所显示的约定是以McClusky（1965）、Booth（1967）、Hill和Peterson（1974）为蓝本。

"3态穷忙"图灵机的有限状态表示。每个圆圈代表表的一个 "状态"--一个 "m-配置 "或 "指令"。状态转换的 "方向 "用箭头表示。出状态附近的标签(如0/P,R)(在箭头的 "尾部")指定了引起特定转换的扫描符号(如0)，后面是斜线/，接着是机器的后续 "行为"，如 "P打印 "然后移动磁带 "R右"。没有普遍接受的格式存在。所显示的约定是以McClusky（1965）、Booth（1967）、Hill和Peterson（1974）为蓝本。

[[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.]]i

[[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.|链接=Special:FilePath/Moves_of_a_3-state_Busy_Beaver.jpg]]i

The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.

The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.

主条目：’’’<font color=’’#ff8000’’>通用图灵机 Universal Turing machine</font>’’’

主条目：’’’<font color=’’#ff8000’’>通用图灵机 Universal Turing machine</font>’’’

[[File:Model of a Turing machine.jpg|thumb|An implementation of a Turing machine]]

[[File:Model of a Turing machine.jpg|thumb|An implementation of a Turing machine|链接=Special:FilePath/Model_of_a_Turing_machine.jpg]]

An implementation of a Turing machine

An implementation of a Turing machine

与真实机器的比较

与真实机器的比较

[[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces]]

[[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces|链接=Special:FilePath/Lego_Turing_Machine.jpg]]

A Turing machine realization using [[Lego pieces]]

A Turing machine realization using [[Lego pieces]]

图灵机简化了算法的陈述。运行在图灵机等效的抽象机上的算法通常比运行在真实机器上的同类算法更通用，因为它们有任意精度的数据类型可用，而且永远不用处理意外情况（包括但不限于内存耗尽）。

图灵机简化了算法的陈述。运行在图灵机等效的抽象机上的算法通常比运行在真实机器上的同类算法更通用，因为它们有任意精度的数据类型可用，而且永远不用处理意外情况（包括但不限于内存耗尽）。

[[File:Turingmachine.jpg|thumb|An experimental prototype of a Turing machine]]

[[File:Turingmachine.jpg|thumb|An experimental prototype of a Turing machine|链接=Special:FilePath/Turingmachine.jpg]]

An experimental prototype of a Turing machine

An experimental prototype of a Turing machine