指令 L : ( p , 1 ) → ( q , 0 , L ) \rm L : (p,1) \to (q, 0, L) L:(p,1)→(q,0,L)

初始状态下 , 状态是 p \rm p p 读取头 指向的字符是 1 1 1 , 如下图 :

执行完 L \rm L L 指令之后 , p \rm p p 状态变为 q q q 状态 , 读取头将指向的字符 1 1 1 擦除 , 改为 0 0 0 , 向左移动一个单位 ( 这里不进行移动 ) ;

左端点向左移动默认不动说明 :

一般情况下我们计算时涉及的图灵机都是 向右无限延长的带子 , 带子有一个左端点 ;

当读写头当前已经指向左端点时 , 如果再向左移动 , 此时默认不进行移动 ;

任务 : 设计一个图灵机 , 给定输入之后 , 图灵机会 在输入中寻找 1 1 1 字符 ;

算法 :

如果 找到了 1 1 1 字符 , 就会将该字符转变成 0 0 0 字符 , 然后将当前状态改为接受状态 f \rm f f , 然后停下来 ;

如果带子上的字符都读取完毕后 , 没有找到 1 1 1 , 只找到了空白字符 , 将该空白字符改为 1 1 1 , 然后向左移动一格 , 然后停下来 ;

( 自动机停下的前提是处于可接受状态 )

根据上述算法 , 构造图灵机 ;

图灵机设计 :

① 状态集 Q = { q , f } \rm Q = \{ q , f \} Q={q,f} , 其中 q \rm q q 是开始状态 , f \rm f f 是接受状态 ;

② 输入字符集 Σ = { 0 , 1 } \rm \Sigma = \{ 0, 1 \} Σ={0,1} ;

③ 带子字符集 Γ = { 0 , 1 , B } \rm \Gamma = \{ 0, 1, B \} Γ={0,1,B} , 其中 B \rm B B 是空白字符 ;

④ 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R) δ(q,0)=(q,0,R)

⑤ 指令 δ ( q , 1 ) = ( f , 0 , R ) \rm \delta (q, 1) = (f, 0, R) δ(q,1)=(f,0,R)

⑥ 指令 δ ( q , B ) = ( q , 1 , L ) \rm \delta (q, B) = (q, 1, L) δ(q,B)=(q,1,L)

上述图灵机设计中 , 最关键的部分是三条指令 ;

图灵机处于开始状态 q \rm q q , 读头指向 0 0 0 字符 , 左端的 00 0 0 00 是输入字符 , 查看图灵机是否接受 00 0 0 00 字符串 ;

下面图灵机后续都是 B \rm B B 空白字符 ;

根据指令 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R) δ(q,0)=(q,0,R) , 当前状态 q \rm q q , 当前指向字符 0 \rm 0 0 , 输出内容是 q , 0 , R \rm q, 0, R q,0,R ,

即 状态变为 q \rm q q , 读头指向的字符变为 0 \rm 0 0 , 向右移动一个字符 ;

如下图 :

此时继续 根据指令 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R) δ(q,0)=(q,0,R) , 当前状态 q \rm q q , 当前指向字符 0 \rm 0 0 , 输出内容是 q , 0 , R \rm q, 0, R q,0,R ,

即 状态变为 q \rm q q , 读头指向的字符变为 0 \rm 0 0 , 向右移动一个字符 ;

如下图 :

此时继续 根据指令 指令 δ ( q , B ) = ( q , 1 , L ) \rm \delta (q, B) = (q, 1, L) δ(q,B)=(q,1,L) , 当前状态 q \rm q q , 当前指向字符 B \rm B B , 输出内容是 q , 1 , L \rm q, 1, L q,1,L ,

即 状态变为 q \rm q q , 读头指向的字符变为 1 \rm 1 1 , 向左移动一个字符 ;

如下图 :

此时继续 根据指令 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R) δ(q,0)=(q,0,R) , 当前状态 q \rm q q , 当前指向字符 0 \rm 0 0 , 输出内容是 q , 0 , R \rm q, 0, R q,0,R ,

即 状态变为 q \rm q q , 读头指向的字符变为 0 \rm 0 0 , 向右移动一个字符 ;

如下图 :

此时继续 根据指令 指令 δ ( q , 1 ) = ( f , 0 , R ) \rm \delta (q, 1) = (f, 0, R) δ(q,1)=(f,0,R) , 当前状态 q \rm q q , 当前指向字符 1 \rm 1 1 , 输出内容是 f , 0 , R \rm f, 0, R f,0,R ,

即 状态变为 f \rm f f , 读头指向的字符变为 0 \rm 0 0 , 向右移动一个字符 ;

此时的状态 f \rm f f 是接受状态 , 自动机停止运行 ;

如下图 :

图灵机 与 自动机 接受的条件是不同的 ;

图灵机计算过程中 , 一旦到达接受状态 , 立刻停机 , 不再继续进行计算 ; 并且称该图灵机是可接受的 ;

自动机即使到达接受状态 , 也要把自动机读取的字符读取完毕 , 才停止计算 ; 然后在查看最终的状态是否是接受状态 ;