文章目录
一、图灵机
二、图灵机设计
三、图灵机设计示例 1
一、图灵机
图灵机要素 :
① 有限多状态集 , Q \rm QQ ;
② 有限多个字符集 , Σ \rm \SigmaΣ ;
③ 带子字符集 , Γ \rm \GammaΓ , 包含 Σ \rm \SigmaΣ ;
④ 转换函数 , 即指令集 , δ \deltaδ ;
⑤ 开始状态 , q 0 \rm q_0q
0
, 包含在 Q \rm QQ 中 ;
⑥ 空白字符 , u \rm uu , 包含在 Γ − Σ \rm \Gamma - \SigmaΓ−Σ ( 相对补集 ) 集合中 ;
⑦ 一些接受状态 , F \rm FF , 其中 F ⊆ Q \rm F \subseteq QF⊆Q ;
指令与转换函数 : 图灵机是根据指令进行计算的 , 指令 是一个 转换函数 δ \rm \deltaδ ;
转换函数 δ \rm \deltaδ 两个输入参数 :
参数一 : 状态 q \rm qq , 该状态是 Q \rm QQ 中的元素 , q ∈ Q q \in\rm Qq∈Q ;
参数二 : 带子字符 Z ZZ , 该字符是 Γ \rm \GammaΓ 集合中的元素 , Z ∈ Γ \rm Z \in \GammaZ∈Γ ;
转换函数 δ \rm \deltaδ 输出是一个三元组 :
输出一 : 状态 p \rm pp ;
输出二 : 带子字符 Y \rm YY ;
输出三 : 方向 D \rm DD , 向左或向右 , 读取头下面要移动的方向 ;
指令 δ \rm \deltaδ 表示的含义解析 :
δ ( q , Z ) = ( p , Y , D ) \rm \delta(q, Z) = (p, Y, D)δ(q,Z)=(p,Y,D) 转换函数 , 其中 q , Z \rm q,Zq,Z 是两个输入 , p , Y , D \rm p, Y, Dp,Y,D 是三个输出 ,
开始时图灵机的 状态是 q \rm qq 状态 , 读取头指向的字符是 Z \rm ZZ ,
执行该转换函数 δ \rm \deltaδ , 会将 状态转变为 p \rm pp 状态 , 将 读取头指向的带子上的字符 Z \rm ZZ 擦除 , 并改为 Y \rm YY , 然后 沿着 D \rm DD 方向 , 移动一格单位 ;
其中 D \rm DD 方向可以是 L \rm LL 向左移动 , 也可以是 R \rm RR 向右移动 ;
格局 Configuration , 格局是给图灵机照一个 快照 , 下图就是图灵机在计算过程中 , 某一个时刻的快照 ;
将图灵机计算过程 , 每个步骤都照一份快照 , 通过轨迹将这些快照联系到一起 , 就可以得到一个数据结构 ,
上述格局可以记作 00 q 1 B \rm 00q1B00q1B , 该写法表示 与 某个格局 ( 快照 ) 一一对应 ;
在 图灵机中 , 读头指向 1 11 , 就将状态写在 1 11 的左边 ;
二、图灵机设计
图灵机的设计很复杂 , 一般情况下 , 不需要设计出图灵机的具体的指令 ,
只需要 使用语言描述图灵机的读写头在带子上的操作 即可 ;
设计图灵机 , 只需要 将图灵机描述出来 即可 ;
证明问题属于 P \rm PP , 只需要将问题使用图灵机判定的过程描述出来 , 计算出该问题的时间复杂度的数量级 ;
三、图灵机设计示例 1
给定语言 : A = { 0 k 1 k : k ≥ 0 } \rm A = \{ 0^k1^k : k \geq 0 \}A={0
k
1
k
:k≥0} , 设计出该语言对应的图灵机 ;
M 1 \rm M_1M
1
图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;
M 1 = \rm M_1 =M
1
= "在长度为 n \rm nn 的字符串 w \rm ww 上进行如下计算 :
① 扫描整个带子上的字符串 , 查看 0 00 和 1 11 的顺序 , 所有的 0 00 必须在所有的 1 11 前面 ; 如果顺序错误 , 进入拒绝状态 ;
② 扫描整个带子 , 遇到一个 0 00 , 就划掉一个 1 11 ; 如果带子上存在 0 00 和 1 11 , 该操作重复进行 ;
③ 如果最后只剩下 0 00 或只剩下 1 11 , 说明 两个数字的个数不等 , 进入拒绝状态 ; 如果最后带子上只剩下空白字符 , 说明两个数字个数相等 , 进入接受状态 ; "
