更改

较少遇到使用4元组的情况：这些代表了图灵指令的进一步原子化（参见Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；

较少遇到使用4元组的情况：这些代表了图灵指令的进一步原子化（参见Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；

===The "state"===

===状态===

 

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:

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:

图灵机上下文中使用的“状态”一词可能会引起混淆，因为它可能意味着两件事。图灵之后的大多数研究者都使用“状态”来表示要执行的当前指令的名称/指示符——即状态寄存器的内容。但是图灵 (1936) 在他所谓的机器“m-配置”的记录和机器（或人）通过计算的“进展状态”——整个系统的当前状态——之间做出了强有力的区分。图灵所说的“状态公式”包括当前指令和纸带上的所有符号：

 

{{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, ’’’<font color=’’#32CD32’’> emphasis added </font>’’’}}

{{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, ’’’<font color=’’#32CD32’’> emphasis added </font>’’’}}

- The Undecidable》，第139-140页，’’’<font color=’’#32CD32’’> 强调是后加的</font>’’’。

—  The Undecidable , pp. 139–140, 强调补充

 

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.

早些时候，图灵在他的论文中进行了进一步的研究：他举了一个例子，在该示例中，他把当前 "m-构型 "的符号（指令的标签）和磁带上的所有符号一起放在扫描的方块下面（The Undecidable，第121页）；他把这个称为 "完整的构型"（The Undecidable，第118页）。为了将 "完整配置 "打印在一行，他将状态标签/m-配置放在扫描符号的左边。

早些时候，图灵在他的论文中进行了进一步的研究：他举了一个例子，在该示例中，他把当前 "m-配置 "的符号（指令的标签）和纸带上的所有符号一起放在扫描的方块下面（The Undecidable，第121页）；他把这个称为 "完整的配置"（The Undecidable，第118页）。为了将 "完整配置 "打印在一行，他将状态标签/m-配置放在扫描符号的左边。

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₄ 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₄" 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 Kleene shows how to write the Gödel number of a machine's "situation": he places the "m-configuration" symbol q₄ 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₄" 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展示了如何写出一台机器的 "情况 "的’’’<font color=’’#ff8000’’> 哥德尔数Gödel number </font>’’’：他把 "m-配置 "符号q₄放在磁带上6个非空白方格的大致中心的扫描方格上(见本文图灵-磁带图)，并把它放在扫描方格的右边。但Kleene把 "q₄ "本身称为 "机器状态"（Kleene，第374-375页）。Hopcroft和Ullman把这种组合称为 "瞬时描述"，并遵循图灵约定，把 "当前状态"（指令标签，m-配置）放在扫描符号的左边（第149页）。

在Kleene(1952)中可以看到这样的一个变体，Kleene展示了如何写出一台机器的 "状态"的哥德尔数：他把 "m-配置 "符号q₄放在磁带上6个非空白方格的大致中心的扫描方格上(见本文图灵-纸带图)，并把它放在扫描方格的右边。但Kleene把 "q₄ "本身称为 "机器状态"（Kleene，第374-375页）。Hopcroft和Ullman把这种组合称为 "瞬时描述"，并遵循图灵规定，把 "当前状态"（指令标签，m-配置）放在扫描符号的左边（第149页）。

Example: total state of 3-state 2-symbol busy beaver after 3 "moves" (taken from example "run" in the figure below):

Example: total state of 3-state 2-symbol busy beaver after 3 "moves" (taken from example "run" in the figure below):

:: 1'''A'''1

:: 1'''A'''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'''.

这意味着：经过三次移动后，纸带上有......000110000......，读写头正在扫描最右边的1，状态为A。空白（在这种情况下用 "0 "表示）可以成为总状态的一部分，如图所示。B01；纸带上有一个 "1"，但读写头正在扫描它左边的 "0"（"空白"），状态是B。

 

这意味着：经过三次移动后，磁带上有......000110000......，磁头正在扫描最右边的1，状态为A。空白（在这种情况下用 "0 "表示）可以成为总状态的一部分，如图所示。B01；磁带上有一个 "1"，但磁头正在扫描它左边的 "0"（"空白"），状态是B。

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

"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)磁带上的符号列表连同当前指令放在扫描符号的左边或扫描符号的右边。

图灵机情况中，应阐明 "状态 "是哪种状态。(i)当前指令，或(ii)纸带上的符号列表连同当前指令，或(iii)纸带上的符号列表连同当前指令放在扫描符号的左边或扫描符号的右边。

Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.

Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.

图灵的传记作者安德鲁 · 霍奇斯Andrew Hodges (1983:107)注意到并讨论了这种混淆。

图灵的传记作者Andrew Hodges (1983:107)注意到并讨论了这种混淆。

===Turing machine "state" diagrams===

===Turing machine "state" diagrams===