更改

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

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

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

===图灵机的状态图===

 

{|class="wikitable"

{|class="wikitable"

|+ The table for the 3-state busy beaver ("P" = print/write a "1")

|+  

3状态穷忙的表格("P" = 打印/写入 a "1")

繁忙的海狸的表格("P" = 打印/写入 a "1")

|-

|-

! Tape symbol

!  

! colspan="3" | Current state A

! colspan="3" |  

当前状态A

当前状态A

! colspan="3" | Current state B

! colspan="3" |  

当前状态B

当前状态B

! colspan="3" | Current state C

! colspan="3" |  

当前状态C

当前状态C

|-

|-

|

|

| Write symbol

|  

写入符号

写入符号

| Move tape

|  

| Next state

|

下一个状态

下一个状态

| Write symbol

|  

写入符号

写入符号

| Move tape

|  

| Next state

|  

下一个状态

下一个状态

| Write symbol

|  

写入符号

写入符号

| Move tape

|  

| Next state

|  

下一个状态

下一个状态

|-

|-

| P

| P

| R

| R

| '''HALT'''

| '''停机'''

|}

|}

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

[[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）为蓝本。

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

To the right: the above table as expressed as a "state transition" diagram.

To the right: the above table as expressed as a "state transition" diagram.

右边：上面的表格表示为"状态转换 "图。

右边：上面的表格表示为"状态转换 "图。

Usually large tables are better left as tables (Booth, p. 74). They are more readily simulated by computer in tabular form (Booth, p. 74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p. 244ff)—can be more readily seen when viewed as a drawing.

Usually large tables are better left as tables (Booth, p. 74). They are more readily simulated by computer in tabular form (Booth, p. 74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p. 244ff)—can be more readily seen when viewed as a drawing.

通常大表最好是以表的形式留下（Booth，第74页）。它们更容易由计算机以表格形式模拟出来（Booth，p.74）。然而，某些概念，例如具有 "复位 "状态的机器和具有重复模式的机器（参见Hill和Peterson p. 244ff）在被视为图纸时更容易被看到。

通常大的表哥最好是留作表格（Booth，第74页）。它们更容易由计算机以表格形式模拟出来（Booth，p.74）。然而，某些概念，例如具有 "复位 "状态的机器和具有重复模式的机器（参见Hill和Peterson p. 244ff）在被视为图纸时更容易被看到。

 

 

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.

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.

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.

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

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

再次提醒读者，这种图表示的是在时间上冻结的表的快照，而不是计算在时间和空间上的过程("轨迹")。虽然穷忙的机器每次 "运行 "都会遵循相同的状态轨迹，但对于可以为变量输入“参数”提供信息的“复制”机器而言，情况并非如此。

再次提醒读者，这种图表示的是在时间上冻结的表的快照，而不是计算在时间和空间上的过程("轨迹")。虽然繁忙的海狸的机器每次 "运行 "都会遵循相同的状态轨迹，但对于可以为变量输入“参数”提供信息的“复制”机器而言，情况并非如此。

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

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 "情况"，Hopcroft-Ullman "瞬时描述"）。如果机器被停止并清空 "状态寄存器 "和整个磁带，则可以使用这些“配置”在其进行中的任何地方重新启动计算（参见Turing（1936）The Undecidable 第139– 140页）。

“计算进度 "图显示了三态繁忙的海狸从开始到结束的计算过程中的 "状态"（指令）进度。最右边是每一步的图灵 "完整配置"。如果机器停止并清空 "状态寄存器 "和整个纸带，则可以使用这些“配置”在其进行中的任何地方重新启动计算（参见Turing（1936）The Undecidable 第139– 140页）。

==Models equivalent to the Turing machine model==

==Models equivalent to the Turing machine model==