图灵机

# 确定的图灵机的瞬时描述(Instantaneous Description, ID)

图灵机的输入虽然是有限长，在有限步内所到达的字符串的非空内容总是有限的，因此可以使用字符串和状态 $q$ 以及 $q$ 在字符串上的位置定义图灵机的瞬时描述：

$X_1X_2...X_{i-1}qX_iX_{i+1}...X_n$

• $q$ 为图灵机的当前状态
• $i$ 为图灵机当前读取的位置
• $X_i,i\in[1,n]$

# ID转移： $\vdash$

在图灵机 $M$ 中， $(q_1,Y,L)=\delta(q_0,X)$

$X_1X_2...X_{i-1}q_0X_iX_{i+1}...X_n\vdash_MX_1X_2...X_{i-2}q_1X_{i-1}YX_{i+1}...X_n$

在图灵机 $M$ 中， $(q_1,Y,R)=\delta(q_0,X)$

$X_1X_2...X_{i-1}q_0X_iX_{i+1}...X_n\vdash_MX_1X_2...X_{i-1}Yq_1X_{i+1}X_{i+2}...X_n$

若某ID $I_1$

# 图灵机的语言

某个 图灵机 定义为 $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$

$\bm L(M)=\{w\in\Sigma^*|(\exist p\in F,\alpha\in\Gamma^*,\beta\in\Gamma^*)q_0w\vdash_M^*\alpha p\beta\}$

• 递归可枚举语言/图灵可识别语言 ： $L=\bm L(M)$
• 递归语言/可判定语言 ： $L=\bm L(M)\wedge(\forall w\in\Gamma^*)\text{M能停机}$

注：图灵机不保证对所有字符串输入都停机。保证停机的图灵机在实际应用中是算法的好模型，是算法概念的形式化。

# 图灵机变种

以下的图灵机都可证明与确定的图灵机等价 ，但可以让图灵机的设计更加简单。

# 可以存储有限个符号的图灵机

$M=(Q',\Sigma,\Gamma,\delta,q_0',B,F)$

• $Q'=Q\times\Gamma\times...\times\Gamma$
• $q_0'=[q_0,B,...,B]$

# 多道图灵机

$M=(Q,\Sigma,\Gamma',\delta,q_0,B',F)$

• $\Gamma'=\Gamma\times\Gamma\times...\times\Gamma$

# 半无穷带图灵机

字符串输入只有一侧是无穷的

# 多带图灵机

• 字符串输入有多个
• 图灵机在每个字符串上可以处于不同的位置
• 图灵机在每个字符串上的位置移动相互独立
• 图灵机在字符串上的移动除向左向右外，还可以是停止状态

# 非确定的图灵机(Nondeterministic Turing Machine, NTM)

$M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$

• $\delta$ ：状态转移函数， $\delta:Q\times\Gamma\rightarrow 2^{Q\times\Gamma\times\{L,R\}}$

# 计算复杂性引入

• 运行时间 ：图灵机在某个输入上停机前移动的步数

• 时间复杂度 $T(n)$ ：图灵机 $M$ 在所有长度为 $n$ 的输入上的运行时间的最大值。

• 只有保证停机的图灵机 $T(n)$ 才有意义

• 只有多项式时间的 $T(n)$ 才能在实际的计算机上可解

上面这些图灵机变种都与确定的图灵机等价，它们都能用来模拟确定的图灵机（显然），也都能被确定的图灵机所模拟。接下来看看如何模拟并分析一下模拟的时间复杂度。

# 用确定的图灵机模拟可以存储有限个符号的图灵机

显然，令确定的图灵机的状态集合为可以存储有限个符号的图灵机的所有可能的状态和存储符号的组合即可。模拟移动 $n$ 步的时间复杂度为 $O(n)$ 。

# 用确定的图灵机模拟多道图灵机

显然，令确定的图灵机的输入为字符元组就是一个多道图灵机了。模拟移动 $n$ 步的时间复杂度为 $O(n)$ 。

# 用确定的图灵机模拟可以存储有限个符号的多道图灵机

显然，令确定的图灵机的状态集合为可以存储有限个符号的图灵机的所有可能的状态和存储符号的组合，并令其输入为字符元组即可。模拟移动 $n$ 步的时间复杂度为 $O(n)$ 。

# 用可以存储有限个符号的多道图灵机模拟多带图灵机

思路：对于 $k$ 带图灵机，用 $2k$ 道图灵机模拟之。对于每个带，都用两个道模拟，一个道存带的内容，一个道存图灵机在当前带的位置。

1. 从左到右扫描一次，存储图灵机在所有带的位置和对应位置的输入
2. 执行状态转移函数，存储图灵机在所有带的移动状态和要修改动作
3. 从右到左扫描一次，按照移动状态修改道上的位置记录、按照修改动作修改道上的数据
4. 重复1~3直到可接受状态

模拟移动1步需要左右扫描一次，时间复杂度 $O(n)$ ，因此模拟移动 $n$ 步的时间复杂度为 $O(n^2)$

# 用多带图灵机 $M$ 模拟NTM $N$ ：广度优先搜索

思路：同NDA一样，NTM的运行过程也可以看作是树，其节点是ID，分支是由于NTM选择了多个状态转移而产生多个ID转移进而产生多个ID。若要用“串行”的图灵机模拟之，则可考虑对NTM运行时树上的ID进行广度优先搜索。

$M$ 有两条带，第一条带保存 $N$ 中产生而未处理的ID，第二条带用于对ID进行处理。

1. 把第一条带开头的ID复制到第二条带
2. 若第二条带上的ID可接受则停止
3. 否则将第二条带上的可能的ID转移复制到第一条带的末端
4. 抹去第二条带开头的ID
5. 重复1~4

模拟每个ID都要读取复制和删除长度为 $n$ 的ID，时间复杂度 $O(n)$ ，若每一个ID至多产生 $m$ 个选择，那经过 $n$ 步要模拟 $\sum_{i=1}^nm^i=\frac{m^{n+1}-1}{m-1}$

# $P=NP$

前面分析出来了用NTM能用多带图灵机进行模拟，但模拟需要指数时间，但这只是一种最直观的模拟方法，是否存在多项式时间的模拟方法？目前还是未知的。

这个问题可以概括为：NTM以多项式时间解决的问题，TM是否也可以以多项式时间解决？

简称 $P=NP$

• $P$ 表示“Polynomial”——“多项式”，指 确定的图灵机 在 多项式时间内 可以解决的问题的问题类
• $NP$ 表示“Non-Deterministic Polynomial”——“非确定的多项式”，指 非确定的图灵机 在 多项式时间内 可以解决的问题的问题类
• “ $NP$ 完全”表示任何NP问题都可以在多项式时间内规约到这个问题

虽然问题目前还没解决，但是实际应用中通常认为 $P\not ={NP}$

# 图灵机的二进制表示

显然，由 $0$ 和 $1$ 组成的字符串可以编码任何的字符系统，因此所有的图灵机都可以编码为 $\Sigma=\{0,1\}$

# 对 $\Sigma^\ast=(\bm 0+\bm 1)^\ast$

将 $(\bm 0+\bm 1)^*$

$(i)_2=1w_i$

因此可以构造如下编码

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$\dots$
$(i)_2$	$1\varepsilon$	$10$	$11$	$100$	$101$	$110$	$111$	$\dots$
$w_i$	$\varepsilon$	$0$	$1$	$00$	$01$	$10$	$11$	$\dots$

# 对图灵机的状态转移函数编码

• 令 $Q=\{q_1,q_2,\dots,q_{|Q|}\}$
• 令 $\Gamma=\{X_1,X_2,\dots,X_{|\Gamma|}\}$
• 令移动方向 $L=D_1$

因此，图灵机的每一个状态、输入符号和移动方向都可以由一个数字表示，进而根据 $01$ 字符串的编码规则，它们也都可以由 $(\bm 0+\bm 1)^*$

由于图灵机的状态转移函数 $\delta:Q\times\Gamma\rightarrow 2^{Q\times\Gamma\times\{L,R\}}$

$\Delta=\left\{(q,X)\rightarrow(q',X',D)|q,q'\in Q\wedge X,X'\in\Gamma\wedge D\in\{L,R\}\right\}$

在此定义下的状态转移函数则表示为：

$\delta(q,X)=(q',X',D)\quad(q,X)\rightarrow(q',X',D)\in\Delta$

而根据上述编码规则，任何一个转移规则 $(q_i,X_j)\rightarrow(q_k,X_l,D_m)\in\Delta$

$C=0^i10^j10^k10^l10^m\quad\delta(q_i,X_j)=(q_k,X_l,D_m)$

# 对图灵机编码

根据上面的分析可以看出，所有的图灵机的状态、输入符号和移动方向都可以由相同的编码方式表示，不同的图灵机本质上只在转移规则上有所不同，因此对一个图灵机的编码就是对其转移规则的编码。

因此，根据上述对图灵机的状态转移函数编码规则，我们可以将图灵机编码为一个由状态转移规则的编码组成的字符串，中间用两个字符 $1$ 分隔：

$C_111C_211C_311\dots C_{n-1}11C_n$

即得到图灵机编码，也即图灵机的二进制表示。

进而根据对 $\Sigma^*=(\bm 0+\bm 1)^*$

$\text{图灵机}M_i:=\text{编码为}w_i\text{的图灵机}$

# 通用图灵机

# 对角化语言 $L_d$

对角化语言是所有不能接受自身编码的图灵机的编码组成的集合：

$L_d=\{w_i|w_i\not\in\bm L(M_i)\}$

注： $L_d$

图灵机 $\rightarrow$
字符串 $\downarrow$	$M_1$	$M_2$	$M_3$	$M_4$	$M_5$	$\dots$
$w_1$	拒绝	拒绝	接受	接受	拒绝
$w_2$	接受	拒绝	拒绝	接受	拒绝
$w_3$	拒绝	接受	接受	拒绝	拒绝
$w_4$	拒绝	拒绝	接受	接受	接受
$w_5$	接受	接受	拒绝	拒绝	拒绝
$\vdots$

# 证明对角化语言不是图灵可识别语言（不存在识别它的图灵机）

假设有一个图灵机 $M_i$

$L_d=\bm L(M_i)$

那么有对于它的编码 $w_i$

$\begin{aligned} &w_i\in L_d\\ \Leftrightarrow&w_i\in\{w_i|w_i\not\in\bm L(M_i)\}&L_d\text{的定义}\\ \Leftrightarrow&w_i\not\in\bm L(M_i)&L_d\text{的定义}\\ \Leftrightarrow&w_i\not\in L_d&L_d=\bm L(M_i)\\ \Rightarrow&\text{矛盾}\\ \end{aligned}$

因此识别对角化语言的图灵机不存在，故对角化语言不是递归可枚举语言。

# 通用语言 $L_u$

根据上文所属的编码方式，我们可以将图灵机 $M_i$

$w_i111w$

进而构造一种“通用语言”：

$L_u=\{w_i111w|w\in L(M_i)\wedge i\in\mathbb N\}$

# 证明通用语言是图灵可识别语言（通用图灵机 $U$ ）

可以构造一个多带图灵机 $U$ ，当输入 $w_i111w\in L_u$

1. 读取 $w_i$
2. 读取 $w$ 写到第二条带上
3. 第三条带存储 $M_i$

从而模拟图灵机 $M_i$

这里的 $U$ 被称为“通用图灵机”，是现代计算机的理论基础。 $U$ 的编码是可以写出来的，罗杰 · 彭罗斯在《皇帝的新脑》中就给出过一个 $U=M_i$

# 证明通用语言不是可判定语言（不能保证所有输入全部停机）

我们可以用通用语言 $L_u$

$L_{du}=\{w_i111w_i|w_i\not\in\bm L(M_i)\}\subset L_u$

进而：

$\begin{aligned} &L_u\text{是可判定语言}&\\ \Leftrightarrow&U\text{在}L_u\text{上保证停机}&\text{可判定语言定义}\\ \Rightarrow&U\text{在}L_{du}\text{上保证停机}&L_{du}\subset L_u\\ \Leftrightarrow&U\text{可识别}L_d&L_{du}\text{和}L_u\text{等价}\\ \Rightarrow&L_d\text{是图灵可识别语言}&\text{图灵可识别语言定义}\\ \Rightarrow&\text{矛盾}&L_d\text{不是图灵可识别语言}$