一、图灵机

图灵机要素 :

① 有限多状态集 , $\mathrm{Q}$ ;

② 有限多个字符集 , $\mathrm{\Sigma }$ ;

③ 带子字符集 , $\mathrm{\Gamma }$ , 包含 $\mathrm{\Sigma }$ ;

④ 转换函数 , 即指令集 , $\delta$ ;

⑤ 开始状态 , ${\mathrm{q}}_0$ , 包含在 $\mathrm{Q}$ 中 ;

⑥ 空白字符 , $\mathrm{u}$ , 包含在 $\mathrm{\Gamma }-\mathrm{\Sigma }$ ( 相对补集 ) 集合中 ;

⑦ 一些接受状态 , $\mathrm{F}$ , 其中 $\mathrm{F}\subseteq \mathrm{Q}$ ;

指令与转换函数 : 图灵机是根据指令进行计算的 , 指令 是一个 转换函数 $\delta$ ;

转换函数 $\delta$ 两个输入参数 :

• 参数一 : 状态 $\mathrm{q}$ , 该状态是 $\mathrm{Q}$ 中的元素 , $q\in \mathrm{Q}$ ;
• 参数二 : 带子字符 $Z$ , 该字符是 $\mathrm{\Gamma }$ 集合中的元素 , $\mathrm{Z}\in \mathrm{\Gamma }$ ;

转换函数 $\delta$ 输出是一个三元组 :

• 输出一 : 状态 $\mathrm{p}$ ;
• 输出二 : 带子字符 $\mathrm{Y}$ ;
• 输出三 : 方向 $\mathrm{D}$ , 向左或向右 , 读取头下面要移动的方向 ;

指令 $\delta$ 表示的含义解析 :

$\delta (\mathrm{q},\mathrm{Z})=(\mathrm{p},\mathrm{Y},\mathrm{D})$ 转换函数 , 其中 $\mathrm{q},\mathrm{Z}$ 是两个输入 , $\mathrm{p},\mathrm{Y},\mathrm{D}$ 是三个输出 ,

开始时图灵机的 状态是 $\mathrm{q}$ 状态 , 读取头指向的字符是 $\mathrm{Z}$ ,

执行该转换函数 $\delta$ , 会将 状态转变为 $\mathrm{p}$ 状态 , 将 读取头指向的带子上的字符 $\mathrm{Z}$ 擦除 , 并改为 $\mathrm{Y}$ , 然后 沿着 $\mathrm{D}$ 方向 , 移动一格单位 ;

其中 $\mathrm{D}$ 方向可以是 $\mathrm{L}$ 向左移动 , 也可以是 $\mathrm{R}$ 向右移动 ;

格局 Configuration , 格局是给图灵机照一个 快照 , 下图就是图灵机在计算过程中 , 某一个时刻的快照 ;

将图灵机计算过程 , 每个步骤都照一份快照 , 通过轨迹将这些快照联系到一起 , 就可以得到一个数据结构 ,

上述格局可以记作 $00\mathrm{q}1\mathrm{B}$ , 该写法表示 与 某个格局 ( 快照 ) 一一对应 ;

在 图灵机中 , 读头指向 $1$ , 就将状态写在 $1$ 的左边 ;

二、图灵机设计

图灵机的设计很复杂 , 一般情况下 , 不需要设计出图灵机的具体的指令 ,

只需要 使用语言描述图灵机的读写头在带子上的操作 即可 ;

设计图灵机 , 只需要 将图灵机描述出来 即可 ;

证明问题属于 $\mathrm{P}$ , 只需要将问题使用图灵机判定的过程描述出来 , 计算出该问题的时间复杂度的数量级 ;

三、图灵机设计示例 1

给定语言 : $\mathrm{A}=\{0^{\mathrm{k}}{1}^{\mathrm{k}}:\mathrm{k}\ge 0\}$ , 设计出该语言对应的图灵机 ;

${\mathrm{M}}_1$ 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;

${\mathrm{M}}_1=$ "在长度为 $\mathrm{n}$ 的字符串 $\mathrm{w}$ 上进行如下计算 :

① 扫描整个带子上的字符串 , 查看 $0$ 和 $1$ 的顺序 , 所有的 $0$ 必须在所有的 $1$ 前面 ; 如果顺序错误 , 进入拒绝状态 ;

② 扫描整个带子 , 遇到一个 $0$ , 就划掉一个 $1$ ; 如果带子上存在 $0$ 和 $1$ , 该操作重复进行 ;

③ 如果最后只剩下 $0$ 或只剩下 $1$ , 说明 两个数字的个数不等 , 进入拒绝状态 ; 如果最后带子上只剩下空白字符 , 说明两个数字个数相等 , 进入接受状态 ; "

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111488027