Skip to content

图灵机

基本定义

  • 纸带可以左移/右移，或者 向当前位置读/写字符
  • \(\triangleright\) 代表纸带的最左端
  • \(\sqcup\) 代表空格

\(M=(K,\Sigma,\delta,s,H)\)

  • \(K\)是状态集合
  • \(\Sigma\) 是纸带上的所有符号。包括空格和最左端标记
  • s是起始状态
  • H是终止状态集合
  • 转移函数\(\delta: (K-H)\times \Sigma \to K \times({\leftarrow,\rightarrow})\) 不能向纸带上写 \(\triangleright\), 读到\(\triangleright\) 只能右移

格局

左边必须有\(\triangleright\) 右边表示读写头右边的位置 到 最后一个非空格字符 的串。 如果读写头右边没有非空格字符,就是e

简化写法 \((q,w\underline{a}u)\) 表示当前读写头在a,左边是w, 右边是u 如果u=e就不写

基本图灵机

symbol writing \(M_a\)

如果当前位置不是\(\triangleright\) 就写入\(a\) 。否则右移1位。 \(K=\set{s,h}.s=s,H=\set{h}\) \(\delta(s,b)=(h,a),b\neq \triangleright\) \(\delta(s,\triangleright)=(s,\rightarrow)\)

head moving left \(M_{\leftarrow}\)

如果不是最左端就左移一格，否则不动 \(K=\set{s,h}.s=s,H=\set{h}\) \(\delta(s,b)=(h,\leftarrow),b\neq \triangleright\) 左移然后停机 \(\delta(s,\triangleright)=(s,\rightarrow)\) 先右移, 然后左移并停机。相当于直接不动并停机

同理构造moving right \(M_{\rightarrow}\) 写a, 左移,右移的图灵机分别简写为\(a,L,R\)

图灵机的组合

  • \(>\) 表示起始位置
  • 箭头上的表示转移条件(读写头的字符是什么) 箭头a表示字符为a \(\bar{a}\) 表示字符不是a
  • 如果无条件可以省略箭头 如\(Ra\) 相同的机器可以用上标，如\(RR\)和\(R^2\)等价

左移机

\(\triangleright \sqcup w \underline{\sqcup}\) 变成 \(\triangleright w \underline{\sqcup}\) w不包含空格 解释: 先左移找到字符串最左边的空格,右移。如果不是空格，就把当前位置设为\(\sqcup\),左移,写入a,然后右移回当前位置。再右移到下一个字符，如此循环。

注意起始和结束时读写头的位置

复制机

\(\underline{\sqcup} w \sqcup\) 变成 \(\sqcup w \sqcup w \underline{\sqcup}\) w不包含空格但可以为空 解释: 对于字符串的某字符a, 先把它设为空格(为了回来的时候定位)。然后\(R_{\sqcup}\) 2次(第一次是为了找到中间的空格符,第二次是找到新字符串最右边) 写入a。同理2次\(L_{\sqcup}\)就可以返回到a原来的位置,把a写回去。 如果\(a=\sqcup\) 那就说明串已经复制完了，现在在两串中间, 利用\(R_{\sqcup}\) 移动到最末尾

]

Example

计算\(succ(n)=n+1\) 比如把\(\triangleright \underline{\sqcup} 101\)变成 \(\triangleright \underline{\sqcup} 110\)

解释: 从右往左, 如果是1就把这一位变成0,然后继续左移(进位). 如果是0,就把这一位设为1,结束。如果是空格,就说明多了一位,要整体右移(SR表示右移机) 最后的\(L_{\sqcup}\)是为了让读写头回到最左边。

递归语言

对于字符串\(w\),起始格局为\((s,\triangleright\underline{\sqcup}w)\)

半判定

  • 语言中的字符串会停机，不属于语言的字符串不停机

判定

  • H={y,n}, 语言中的字符串停机到y, 不属于语言的字符串停机到n

  • 有图灵机判定一个语言，则称这个语言是 recursive / decidable 的

  • 有图灵机半判定一个语言，则称这个语言是 recursively enumerable / recognizable 的

Warning

如果 L和\(\bar{L}\)都是RE, 那么L一定是recursive

证明: 同时跑L和\(\bar{L}\)的两个图灵机M1,M2 如果M1停机了那就是yes M2停机了那就是no

图灵机的变种

定义: k条纸带,每个纸带都有一个读写头,。

K带图灵机等价于单带图灵机，思路:

  • 构建新的symbol 把k条带上同一位置的k个字符(包括下划线标记)合成为一个字符

  • two-way infinite tape 纸带两侧都无限长的图灵机

    • 可以用双带图灵机模拟，也就可以用标准图灵机模拟

  • multiple head 多读写头图灵机

    • 用下划线标记每个头的位置，然后操作之前先扫一遍，获取所有头的位置

  • 2-dimensional tape 二维纸带图灵机

    • 从左上角开始沿反对角线编号，延展成一维纸带

  • random access 随机访问图灵机

    • 每次移动读写头可以不止一步
    • 将多步移动拆成多次单步移动即可

非确定性图灵机

判定: \(H=\set{y,n}\)

  1. 对于任意字符串\(w\in \Sigma_0^*\) 存在常数\(N\), 不存在格局\(c\) 使得\((s,\triangleright \underline{\sqcup}w) \vdash^N_M c\) (N步内停机, 即树高不超过N)
  2. \(w\in L\) 当且仅当 \((s,\triangleright \underline{\sqcup}w) \vdash^N_M (y,...)\) (有一条分支可以停机到状态y)

NTM判断所有合数构成的语言

假设输入字符串为 w，则先猜测两个数，得到 ⊳⌴w⌴p⌴q，然后将 p 和 q 相乘，如果等于 ww 则停机到 y，否则停机到 n，满足第二个条件。猜测是有限的，而且都可以有限步停机，满足第一个条件

3-tape DTM模拟NTM

  1. 装输入
  2. 模拟NTM 每一步根据3选择用哪个转换
  3. 是一个01串 枚举在树上向左/向右走

语法

一个语言由一个 Grammar 产生，当且仅当它被某个 TM semidecided，即它是 RE 的。

Comments