一、图灵机图示

下图是图灵机的简单示意图 : 图灵机由 无穷长的带子 , 读头 , 状态 组成 ;

带子 :

无穷长度 , 每个格子有一个字符 ;

读头 :

上图中的箭头是读头 , 用于读写数据 ;

读头作用是 读取带子上的字符 , 然后擦掉该字符 , 写入新的字符 ;

然后该读头可以 向左或向右移动一格单位 ;

状态 :

箭头上的矩形框中表示当前的状态 , 状态个数是有限多个 , 其作用是指挥图灵机如何进行计算 ;

上述图灵机是理想的图灵机 , 带子是无穷长的 , 带子上的字符是有限多个 , 状态是有限多个 , 指令也是有限多个 ;

二、图灵机形式定义

图灵机要素 :

① 有限多状态集 , $\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}$ 向右移动 ;

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

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