文章目录

• 一、图灵机示例
• 二、图灵机示例 2

一、图灵机示例

---

指令 $\mathrm{L}:(\mathrm{p},1)\to (\mathrm{q},0,\mathrm{L})$

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

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

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

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

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

二、图灵机示例 2

---

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

算法 :

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

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

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

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

图灵机设计 :

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

② 输入字符集 $\mathrm{\Sigma }=\{0,1\}$ ;

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

④ 指令 $\delta (\mathrm{q},0)=(\mathrm{q},0,\mathrm{R})$

⑤ 指令 $\delta (\mathrm{q},1)=(\mathrm{f},0,\mathrm{R})$

⑥ 指令 $\delta (\mathrm{q},\mathrm{B})=(\mathrm{q},1,\mathrm{L})$

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

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

下面图灵机后续都是 $\mathrm{B}$ 空白字符 ;

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

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

如下图 :

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

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

如下图 :

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

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

如下图 :

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

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

如下图 :

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

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

此时的状态 $\mathrm{f}$ 是接受状态 , 自动机停止运行 ;

如下图 :

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

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

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

总结

以上是生活随笔为你收集整理的【计算理论】图灵机 ( 图灵机示例 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。