150
个编辑
更改
无编辑摘要
* is a partial function called the ''transition function'', where L is left shift, R is right shift. If is not defined on the current state and the current tape symbol, then the machine halts; intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement.
* is a partial function called the ''transition function'', where L is left shift, R is right shift. If is not defined on the current state and the current tape symbol, then the machine halts; intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement.
在Hopcroft & Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q,F⟩，其中：
在Hopcroft & Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩，其中：
* Г是有限的、非空的纸带''字母符号集''；
* bᕮГ，是''空白符号''（唯一允许在计算过程中的任何步骤无限频繁地出现在纸带上的符号）；
* Σ⊆Г\{b}是''输入符号''集，即允许出现在初始纸带内容中的符号集；
* Q是有限的、非空的''状态''集；
* q_0ᕮQ是初始状态；
* F⊆Q是''最终状态''或''接受状态''的集合。初始纸带内容被认为是''接受''由M如果它最终停止在一个状态 F.
* δ: （Q \ F) Χ Г Χ {L, R}是一个偏函数，称为''转移函数''，其中 L 是左移，R 是右移。如果在当前状态和当前纸带符号上未定义，则机器停止；直观地，转移函数指定了从当前状态转移的下一个状态，哪个符号覆盖读写头指向的当前符号，以及下一个读写头运动。
In addition, the Turing machine can also have a reject state to make rejection more explicit. In that case there are three possibilities: accepting, rejecting, and running forever. Another possibility is to regard the final values on the tape as the output. However, if the only output is the final state the machine ends up in (or never halting), the machine can still effectively output a longer string by taking in an integer that tells it which bit of the string to output.
In addition, the Turing machine can also have a reject state to make rejection more explicit. In that case there are three possibilities: accepting, rejecting, and running forever. Another possibility is to regard the final values on the tape as the output. However, if the only output is the final state the machine ends up in (or never halting), the machine can still effectively output a longer string by taking in an integer that tells it which bit of the string to output.
此外，图灵机还可以有拒绝状态，使拒绝更加明确。在这种情况下，有三种可能性：接受、拒绝和永远运行。另一种可能性是将磁带上的最终值视为输出。然而，如果唯一的输出是机器最终所处的状态（或永远不停止），机器仍然可以有效地输出一个较长的字符串，通过输入一个整数，告诉它要输出字符串的哪一位。
A relatively uncommon variant allows "no shift", say N, as a third element of the set of directions <math>\{L,R\}</math>.
A relatively uncommon variant allows "no shift", say N, as a third element of the set of directions <math>\{L,R\}</math>.
一个相对不常见的变体允许“无移位”，比如 N，作为方向集的第三个元素{L, R}。
The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):
三状态繁忙的海狸（busy beaver）七元组是这样的:（关于繁忙的海狸相关的资料可以搜索“图灵机实例”了解）
* Q={A, B, C, HALT}(状态);
* Г= {0, 1}(纸带符号);
* b=0（空白符号）；
* Σ={1}（输入符号）；
* q_0 = A（初始状态）；
* F={HALT}（最终状态）；
* δ=参见下面的状态表（转换函数）。
Initially all tape cells are marked with <math>0</math>.
Initially all tape cells are marked with <math>0</math>.
最初，所有的纸带单元格都用0标记。
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|+State table for 3 state, 2 symbol busy beaver
|
! rowspan="2" | l
! rowspan="2" | Tape symbol
!Rowspan = “2” | 磁带符号
! rowspan="“2”" | 磁带符号
! colspan="3" | Current state A
! colspan="3" | Current state A
!Colspan = “3” | 当前状态 A
! colspan="“3”" | 当前状态 A
! colspan="3" | Current state B
! colspan="3" | Current state B
!Colspan = “3” | 当前状态 B
! colspan="“3”" | 当前状态 B
! colspan="3" | Current state C
! colspan="3" | Current state C
!Colspan = “3” | 当前状态 C
! colspan="“3”" | 当前状态 C
|- style="font-size:9pt"
|- style="font-size:9pt"
|
|- style="“" font-size: 9 pt”
|-style = “ font-size: 9 pt”
|
| 写入符号
| 写入符号
| Move tape
|移动磁带
移动磁带
下一个状态
|下一个状态
| Write symbol
| Write symbol
| 1
| 1
| R
| R
| '''B'''
|'''B'''
| 1
| 1
| L
| L
| '''A'''
|'''A'''
| 1
| 1
| L
| L
| '''B'''
|'''B'''
|-
|-
| 1
| 1
| 1
| 1
| L
| L
| '''C'''
|'''C'''
| 1
| 1
| R
| R
| '''B'''
|'''B'''
| 1
| 1
| R
| R
| '''HALT'''
|'''HALT'''
| '''停止'''
|'''停止'''
|}
|}