图灵机TM及可计算性

前言

阅读本文需要集合论、图论的相关知识，在此不作有关相关知识的赘述。

笔者水平有限，存在的错误和不足请大家指正。

图灵机

图灵机的引入

$\boldsymbol{Figure\ 2.1:}$

在前文中已经介绍了有穷自动机DFA和下推自动机PDA，现在介绍一个更加强大的计算模型，这就是由Alan Turing（1912~1954）在1936年提出的 图灵机（Turing Machine,TM） ，图灵提出TM的目的是为了对算法进行形式化的描述，只考虑算法的基本特征，因此该模型应该具有以下两个性质：

具有有穷描述。

过程必须是由离散的、可以机械执行的步骤组成。

图灵给出的基本模型包括一个有穷状态控制器（finite state control,FSC）、一条含有无穷多个带方格的输入带和一个读头，这使得TM有着无限大容量的储存且可以任意访问内部数据。对基本模型来说，输入带是两端无穷的，每个方格可以容纳一个符号，在TM最初启动的时候长度为$n$的输入串被存放在输入带左端开始的连续$n$个方格中，在这$n$个带方格之后，其他带方格均含有一个表示空白的符号，它不在输入符号中。TM的每一个移动与所读的符号、所处的状态有关。读头每次读一个符号，则在所读符号所在的带方格中印刷一个符号。在一次移动中将会完成以下$3$个动作：

改变有穷状态控制器的状态。

在当前所读符号所在的带方格中印刷一个符号。

将读头向右或者向左移动一格。

TM的物理模型

图灵机的形式化定义

$\boldsymbol{Definition\ 2.2:}$

现在给出TM的形式化定义：

TM：$M$是一个七元组：$M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$，其中：

$Q$是有穷状态集，相应的也有状态的概念。
$q_0$是起始状态，也就是对于一个给定的输入串，$M$以状态$q_0$启动，读头注视着输入串最左端的符号。
$F$是终止状态集，要求$F\subseteq Q$，也有终止状态的概念。
$\Gamma$是 带符号表（tape symbol） ，$\forall X\in\Gamma$，称$X$为$M$的一个带符号，表示在$M$的运行过程中，$X$可以在某一时刻出现在输入带上。
$B$被称为 空白符（blank symbol） ，含有空白符的带方格被认为是空的。
$\Sigma$为输入字母表，要求$\Sigma\subseteq\Gamma-${$B$}，$\forall a\in\Sigma$，称$a$为$M$的一个输入符号，除$B$以外只有$\Sigma$中的符号才能在$M$刚刚启动的时候出现在输入带上。
$\delta:Q\times F\rightarrow Q\times F\times${$R,L$}称为$M$的移动函数。其中$\delta(q,X)=(p,Y,R)$表示$M$在状态$q$读入符号$X$后将状态改为$p$并在这个$X$所在的带方格中印刷符号$Y$并且将读头向右移动一格。$\delta(q,X)=(p,Y,L)$表示$M$在状态$q$读入符号$X$后将状态改为$p$并在这个$X$所在的带方格中印刷符号$Y$并且将读头向左移动一格。

这里的每一个动作都是确定的，因此也可以称这里定义的图灵机为确定的图灵机。

$\boldsymbol{Definition\ 2.3:}$

在TM的计算过程中，当前状态、当前带子内容和读写头当前位置都体现了TM现在的情况，虽然TM有着无穷长的带子，但是经过有限不饿，带上非空内容总是有限的，为此引入瞬时描述（instantaneous description,ID），也可以称为 格局（configuration） 的概念。

$X_1X_2\cdots X_{i-1}qX_iX_{i+1}\cdots X_n$被称为一个瞬时描述，其具有以下含义：

$q$是TM的当前状态。

带头在左起第$i$个非空格符$X_i$上。

$X_1\cdots X_n\in\Gamma$是从最左到最右非空格内容（$i=1$表示带头左端全是空格符号，$i=n$表示带头右端全是空格符号）。

设$X_1X_2\cdots X_{i-1}qX_iX_{i+1}\cdots X_n$是$M$的一个ID，如果有$\delta(q,X_i)=(p,Y,R)$，那么记$X_1X_2\cdots X_{i-1}qX_iX_{i+1}\cdots X_n\vdash_M X_1X_2\cdots X_{i-1}YpX_{i+1}\cdots X_n$，表示$M$在ID：$X_1X_2\cdots X_{i-1}qX_iX_{i+1}\cdots X_n$下经过一次移动后ID变为$X_1X_2\cdots X_{i-1}YpX_{i+1}\cdots X_n$。

当读头向左移动时也有类似的定义，对于一些特殊的情况也有相应的定义，在此仅作示意性的说明。

符号$\vdash_{M}$称为ID转移符号，显然这是一个二元关系，为了表示方便，用$\vdash_M^n,\vdash_M^{ + },\vdash_M^{ * }$分别表示关系$(\vdash_M)^n,(\vdash_M)^{ + },(\vdash_M)^{ * }$，其意义是显然的。在不产生混淆的情况下也可以简记为$\vdash^n,\vdash^{ + },\vdash^{ * }$。

$\boldsymbol{Example\ 2.4:}$

TM有着比FA和PDA更加强大的功能，例如下面这样一个例子：

语言$L_1=${$ww|w\in(0+1)^{ * }$}，那么可以构造出识别它的TM如下：

能够识别L1的TM

如果$M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$是一个TM，那么$M$接受的语言为$L(M)=${$w|w\in\Sigma^{ * },q_0w\vdash^{ * }\alpha p\beta,p\in F,\alpha,\beta\in\Gamma^{ * }$}。

输入串放在输入带上，$M$处于$q_0$，带头位于输入串的第一个字符上，输入串最终会导致$M$进入某个终止状态。

$\boldsymbol{Definition\ 2.5:}$

为了方便讨论，一般假定进入终止状态后$M$总会 停机（halt） ，也就是说没有下一个动作的定义，但是一个总会停机的状态不一定是终止状态，后文中为了区分这两种情况，称呼终止状态为接受状态，称总会停机的非终止状态为拒绝状态，TM进入接受状态立马就会接受，进入拒绝状态立马就会拒绝。

在一个 接受格局（accepting configuration） 中状态是接受状态，在一个 拒绝格局（rejecting configuration） 中状态是拒绝状态，它们都被称为 停机格局（halting configuration） 。

设$M$是一个TM，$w$是一个输入串。$M$在$w$上的一个 接受计算历史（accepting computation history） 是一个格局序列$C_1,C_2,\cdots,C_l$，其中$C_l$是$M$在$w$上的起始格局，$C_l$是$M$的一个接受格局，且每个$C_i$都是$C_{i-1}$的合法结果，即符合$M$的规则。$M$在$w$上的一个 拒绝计算历史（rejecting computation history） 的定义是类似的。

$\boldsymbol{Definition\ 2.6:}$

如果一个语言$L$能够被TM：$M$接受，那么称$L$是 递归可枚举（recursively enumerable language,r.e.） ，称$L$是被$M$识别的语言（language recognized by $ M $），又称该语言是 图灵可识别的（Turing-recognizable） 。

$\boldsymbol{Note\ 2.7:}$

在一个输入上运行一个TM，可能会出现三种结果：接受、拒绝或循环（loop），一旦出现了循环便意味着TM不好停机，循环动作可以很简单也可能很复杂，可以找到这样一个TM对于某个特定的输入不能停机，也就是进入了循环：

考虑TM：$M=(${$q_0,q_1$},{$0$},{$0,B$}$,\delta,q_0,B,\varnothing)$，其中$\delta(q_0,0)=(q_1,B,R),\delta(q_0,B)=(q_1,B,R),\delta(q_1,B)=(q_0,B,L)$，这个TM接受的语言为$\varnothing$，其中对于输入{$0^n|n\geq 2$}而言这个TM会发生拒绝，但是对于输入{$0,\epsilon$}而言这个TM将会进入循环，无法停机。

$\boldsymbol{Definition\ 2.8:}$

很难区分一个TM究竟是进入了循环还是需要耗费很长的时间运行，所以如果有一个TM对于所有输入都停机，它永远不会出现循环，则称它为 判定器（decider） ，因为它们总能决定是接受还是拒绝，对于可以识别某个语言的判定器，称其 判定（decide） 该语言。

$\boldsymbol{Definition\ 2.9:}$

如果一个语言$L$能够被判定器$M$接受，那么称$L$是 递归语言（recursive language） ，称$L$是被$M$判定的语言，又称该语言是 图灵可判定的（Turing decidable） 或简称为 可判定的（decidable） 。

TM除了作为语言识别器以外，还可以作为非负整函数的计算器，可以对所有非负整数进行编码，例如对于一个函数$f(n_1,n_2,\cdots,n_k)$而言可以用符号串$0^{n_1}10^{n_2}1\cdots 10^{n_k}$表示它的$k$个变元$n_1,n_2,\cdots,n_k$的值，将其作为相应的TM的输入，如果$f(n_1,n_2,\cdots,n_k)=m$那么TM的输出为$0^m$，也就是说TM会停机并且在输入带上留下字符串$0^m$。

$\boldsymbol{Definition\ 2.10:}$

设有$k$元函数$f(n_1,n_2,\cdots,n_k)=m$，存在TM：$M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$接受输入串$0^{n_1}10^{n_2}1\cdots 10^{n_k}$并输出$0^m$，当$f(n_1,n_2,\cdots,n_k)$无定义的时候$M$没有恰当的输出，则称$M$计算$k$元函数$f(n_1,n_2,\cdots,n_k)$，而$f(n_1,n_2,\cdots,n_k)$为$M$计算的函数，也称$f$是 图灵可计算的（Turing computable） 。

如果对于任意的$n_1,n_2,\cdots,n_k$，$f(n_1,n_2,\cdots,n_k)$均有定义，也就是计算$f$的TM总能给出确定的输出，则称$f$为 完全递归函数（total recursive function） 。一般地，TM计算的函数都被称为 部分递归函数（partial recursive function） 。

$\boldsymbol{Example\ 2.11:}$

现在给出一个作为非负整函数的计算器的TM：

考虑二元函数$f(n,m)$，当$n>m$时$f(n,m)=n-m$，当$n\leq m$时$f(n,m)=0$。

考虑TM：$M=(\cup_{i=0}^6${$q_i$},{$0,1$},{$0,1,X,B$}$,\delta,q_0,B,${$q_6$}$)$，其中：

$\delta(q_0,0)=(q_1,B,R),\delta(q_0,1)=(q_5,B,R),\delta(q_1,0)=(q_1,0,R),\delta(q_1,1)=(q_2,1,R)$

$\delta(q_2,X)=(q_2,X,R),\delta(q_2,0)=(q_3,X,L),\delta(q_2,B)=(q_4,B,L),\delta(q_3,X)=(q_3,X,L)$

$\delta(q_3,1)=(q_3,1,L),\delta(q_3,0)=(q_3,0,L),\delta(q_3,B)=(q_0,B,R),\delta(q_4,X)=(q_4,B,L)$

$\delta(q_4,1)=(q_6,0,R),\delta(q_5,X)=(q_5,B,R),\delta(q_5,0)=(q_5,B,R),\delta(q_5,B)=(q_6,B,R)$

图灵机的变形

$\boldsymbol{Definition\ 2.12:}$

其他形式的图灵机还有很多，它们被称为图灵机模型的 变形（variant） ，原来的模型和它所有合理的变形有着相同的能力，也就是识别相同的语言类，虽然它们的定义有了变化但它们的能力却没有改变，在形式变化中保持不变的性质被称为 稳健性（robustness） 。TM相较于FA和PDA更具惊人的稳健性。

$\boldsymbol{Figure\ 2.13:}$

带状态存储的图灵机：在有穷控制器中可以存储有限个符号的图灵机：$M’=(Q’,\Sigma,\Gamma,\delta,q’_0,B,F’)$，其中$Q’=Q\times F\times\cdots\times F,q’_0=(q_0,B,\cdots,B)$，也就是说在FCS中存储了一个有限长的缓冲，并且存储输入带上的一些符号，很明显这样的变形和原先的图灵机是等价的。

带状态存储的图灵机

$\boldsymbol{Figure\ 2.14:}$

多道图灵机（multi-track Turing machine） ：$M’=(Q,\Sigma,\Gamma’,\delta,q_0,B’,F)$，其中$\Gamma’=\Gamma\times\Gamma\times\cdots\times\Gamma$，相当于在图灵机当中输入带共有$k$条道，读头一次读入$k$个符号。显然这样的变形和原先的图灵机是等价的。

多道图灵机

$\boldsymbol{Figure\ 2.15:}$

在本文中定义图灵机要求输入带是两端无穷的，但是实际上也可以对这个要求进行限制，现在规定这样一种图灵机，它的输入带具有左端点、而它的右端是无穷的，在TM最初启动的时候从输入带的左端开始放置输入串，也就意味着读头在初始注视着输入带的最左端的符号，为了避免读头通过左端离开输入带，规定在这种情况下图灵机将不会有下一个ID。这样定义的图灵机被称为 基本图灵机（basic Turing machine） ，相对的，在前文中定义的图灵机可以被称作 双向无穷带图灵机（Turing machine with two-way infinite tape） 。

$\boldsymbol{Theorem\ 2.16:}$

对于任意一个双向无穷带图灵机$M$，都存在一个等价的基本图灵机$M’$，也就是说$L(M’)=L(M)$。

设有双向无穷带图灵机$M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$，为了构造等价的基本图灵机，很自然地会想到用一个有两条道的基本图灵机$M’$去模拟$M$的双向无穷带，其中一个带用来存放$M$开始启动时读头所注视的带方格（设其为$A_0$所在的带方格）以及其右侧所有带方格中的内容，第二个带按照相反的顺序用于存放这个位置左侧所有带方格中的内容，为了表示方便，在与$A_0$对应的带方格的第二道上印刷符号$￠$以表示这是带的最左端，例如在$M$的输入带上有符号$\cdots BA_{-n}\cdots A_{-1}A_0\cdots A_i\cdots A_mB\cdots$，那么在$M’$的输入带上就会有符号$(A_0,￠)(A_1,A_{-1})\cdots(A_i,A_{-i})\cdots (B,B)\cdots$。为了让$M’$在模拟$M$的过程中知道自己究竟在处理带子上哪一道的字符，可以利用带状态存储的图灵机来实现这一点，现在给出形式化的证明。

$\boldsymbol{Proof:}$考虑基本图灵机$M’=(Q\times${$1,2$}$,\Sigma\times${$B$}$,\Gamma\times(\Gamma\cup${$￠$}$),\delta’,q_0,(B,B),F\times${$1,2$}$)$，其中$\delta’$的定义如下：

$M’$在启动的时候需要模拟$M$的启动动作，并且要完成$￠$的印刷。对于$\forall a\in\Sigma\cup${$B$}，如果$\delta(q_0,a)=(p,X,R)$，那么令$\delta’(q_0,(a,B))=((p,1),(X,￠),R)$，如果$\delta(q_0,a)=(p,X,L)$，那么令$\delta’(q_0,(a,B))=((p,2),(X,￠),R)$。

$M’$的读头未指向带的最左端符号时，它在第一道上完全模拟$M$的动作。对于$\forall(X,Z)\in\Gamma\times\Gamma$，如果$\delta(q,X)=(p,Y,R)$，那么令$\delta’((q,1),(X,Z))=((p,1),(Y,Z),R)$，如果$\delta(q,X)=(p,Y,L)$，那么令$\delta’((q,1),(X,Z))=((p,1),(Y,Z),L)$。

$M’$的读头未指向带的最左端符号时，它在第二道上模拟$M$的动作，但移动方向要相反。对于$\forall(X,Z)\in\Gamma\times\Gamma$，如果$\delta(q,X)=(p,Y,R)$，那么令$\delta’((q,2),(X,Z))=((p,1),(Y,Z),L)$，如果$\delta(q,X)=(p,Y,L)$，那么令$\delta’((q,1),(X,Z))=((p,1),(Y,Z),R)$。

$M’$的读头指向带的最左端符号时，由于最左端的符号的第二道上的符号是$￠$，所以它只能是在第一道上运行。对于$\forall (q,X)\in Q\times\Gamma$，如果$\delta(q,X)=(p,Y,R)$，那么令$\delta’((q,1),(X,￠))=((p,1),(Y,￠),R),\delta’((q,2),(X,￠))=((p,1),(Y,￠),R)$，如果$\delta(q,X)=(p,Y,L)$，那么令$\delta’((q,1),(X,￠))=((p,2),(Y,￠),R),\delta’((q,2),(X,￠))=((p,2),(Y,￠),R)$。

可以证明$L(M)=L(M’)$，证毕，这也就意味着这两种图灵机识别同样的语言。

$\boldsymbol{Figure\ 2.17:}$

多带图灵机（multi-tape Turing machine） ：有多个带子，每个带子都是自己的读写头用于读和写，开始时输入出现在第一个带子上，其他带子都是空白的。转移函数改为允许多个带子同时进行读、写和移动带头，其形式为$\delta:Q\times\Gamma^k\rightarrow Q\times\Gamma^k\times(${$L,R$}$)^k$，例如$\delta(q_i,a_1,\cdots,a_k)=(q_j,b_1,\cdots,b_k,L,R,\cdots,L)$，表示如果机器处于状态$q_i$，读头读的符号分别为$a_1,\cdots,a_k$，那么机器的状态转移到$q_j$，并且读头分别写下符号$b_1,\cdots,b_k$，同时按照后续的移动方式移动读头。

$\boldsymbol{Theorem\ 2.18:}$

对于任意一个多带图灵机$M$，都存在一个等价的单带图灵机$S$，也就是说$L(M)=L(S)$。

$\boldsymbol{Proof:}$假设$M$有$k$条带子，$S$把这$k$个带子的信息都存储在它唯一的带子上，用来模拟$M$的效果，它用一个定界符#来分开不同带子的内容，同时$S$还要存储$M$中每个带子上的读头的位置，不妨通过在符号上加一个点来描述这种情况（例如读头注视着符号$a$就记符号为$\dot{a}$）$S$把它们想象为虚拟带子和虚拟读头，现在给出一个可行的$S$模拟$M$：

对于输入$w=w_1\cdots w_n$：

$S$在自己的带子上放入#$\dot{w_1}w_2\cdots w_n$#$\dot{B}$#$\dot{B}$#$\cdots$#以表示$M$全部带子的内容。

为了模拟多带机的一步移动，$S$在其带子上从标记左端点的第一个#开始扫描，一直扫描到标记右端点的第$k+1$个#，其目的是确定虚拟读头下的符号，然后$S$进行第二次扫描，并且根据$M$的转移函数指示的方式更新带子。

任何时候，只要$S$将某个虚拟读头向右移动至某个#上面，就意味着$M$已将自己相应的读头移动到了其所在的带子的空白区域上，即以前没有读过的区域上，因此，$S$在这个带子方格上写下$B$，并将这个带子方格到最右端的各个带子方格中的内容都向右移动一格，再继续像之前一样模拟。

$\boldsymbol{Example\ 2.19:}$

用一个带子表示三个带子

$\boldsymbol{Corollary\ 2.20:}$

一个语言是图灵可识别的，当且仅当存在多带图灵机识别它。

$\boldsymbol{Figure\ 2.21:}$

非确定型图灵机（nondeterministic Turing machine） 在计算过程中机器可以在多种可能性动作中选择一种继续进行，它的转移函数$\delta:Q\times\Gamma\rightarrow 2^T$（其中$T=Q\times\Gamma\times${$L,R$}），也就是说它对于一个输入串有着多个移动序列，只要存在一个序列可以使图灵机进入终止状态，那么这个输入串便可以被图灵机接受。

$\boldsymbol{Theorem\ 2.22:}$

每个非确定型图灵机都等价于某一个确定型图灵机。

$\boldsymbol{Proof:}$为了用确定型图灵机模拟非确定型图灵机，很容易想到非确定型图灵机的计算会对应一个树的结构，树的分支代表了非确定型图灵机的一个分支，树的结点是$N$的一个格局，根结点对应起始格局。为了让确定型图灵机搜索各个分支，可以采用“宽度优先搜索”：搜索一个深度的所有分支后再搜索下一个深度的所有分支。

被模拟的非确定型图灵机为$N$，模拟确定型图灵机$D$有三条带子（先前已经证明了这等价于只有一个带子）。第一个带子只包含输入串，且不再改变；第二个带子存放$N$的带子中的内容，此内容对应于$N$的非确定型计算的某个分支；第三个带子记录$D$在$N$的计算树中所处的位置。

先考虑第三个带子上数据的表示方式，$N$的每个格局都确定一个集合，这个集合包含了该格局可能转移的所有格局，这是由转移函数决定的，因此集合的元素个数是有限的，设集合的元素最大值为$b$，那么对于树的每一个结点都可以分配一个地址，它是$\Gamma_b=${$1,2,\cdots,b$}上的一个串（例如$231$表示从根结点出发走到第$2$个子结点，再走到第$3$个子结点，最后走到第$1$个子结点），很显然存在着无意义的地址，那么你此时它就无效。在第三个带子上放置的是$\Gamma_b$中的一个串，也就是地址，用$\epsilon$表示根地址，由于采用了“宽度优先搜索”，地址的顺序也自然确定了。

现在给出$D$的描述：

开始时，第一个带子包含输入串$w$，第二个带子和第三个带子是空的。

把第一个带子复制到第二个带子上，并且将第三个带子的字符串初始化为$\epsilon$。

用第二个带子去模拟$N$在·输入$w$上的非确定型计算的某个分支，在$N$的每一步动作前，查询第三个带子上的下一个数字，以决定在$N$的转移函数所允许的选择中作何选择。如果第三个带子上没有符号剩下，或这个非确定型的选择是无效的，则放弃这个分支，进入第4步，如果遇到了拒绝格局也进入第4步。如果遇到了接受格局就接受这个输入。

在第三个带子上用字符串顺序的下一个串来替代原有的串，再转回第2步以模拟下一个计算分支。

$\boldsymbol{Example\ 2.23:}$

模拟N的确定型图灵机D

$\boldsymbol{Corollary\ 2.24:}$

一个语言是图灵可识别的当且仅当存在非确定型图灵机识别它。

类似的，对于非确定型图灵机而言也有判定的概念，此时也称其为判定器，现在证明它判定的语言是可判定语言。

$\boldsymbol{Corollary\ 2.25:}$

一个语言是可判定的当且仅当存在非确定型图灵机判定它。

$\boldsymbol{Proof:}$也就是证明一个被非确定型图灵机$N$所判定的语言是可判定的，可以在上文中给出的确定型图灵机中进行修改，将原先的4步改为以下5步即可：

开始时，第一个带子包含输入串$w$，第二个带子和第三个带子是空的。

把第一个带子复制到第二个带子上，并且将第三个带子的字符串初始化为$\epsilon$。

用第二个带子去模拟$N$在·输入$w$上的非确定型计算的某个分支，在$N$的每一步动作前，查询第三个带子上的下一个数字，以决定在$N$的转移函数所允许的选择中作何选择。如果第三个带子上没有符号剩下，或这个非确定型的选择是无效的，则放弃这个分支，进入第4步，如果遇到了拒绝格局也进入第4步。如果遇到了接受格局就接受这个输入。

如果$N$的所有非确定型的分支都拒绝，则拒绝，进入第5步。

在第三个带子上用字符串顺序的下一个串来替代原有的串，再转回第2步以模拟下一个计算分支。

$\boldsymbol{Figure\ 2.26:}$

前文中提到TM识别的语言也叫做递归可枚举语言，这就涉及到了一个称作 枚举器（enumerator） 的机器，也是TM的一种变形。粗略的说，枚举器是有打印机的图灵机，图灵机把打印机当作是输出设备，从而可以打印串。枚举器以空白输入的工作带开始运行，如果不停机，那么它可能会打印出串的一个无限序列。枚举器$E$所枚举的语言是最终打印出的串的集合，而且$E$可能以任意顺序生成这个语言的串，甚至可以有重复。

枚举器的这种模式也可以用TM来表示，让一个TM打印出字符串后用分隔符#对不同字符串进行区分即可，这样的TM称为 作为枚举器的图灵机（Turing machine as enumerator） 。

$\boldsymbol{Theorem\ 2.27}$

一个语言是可识别的当且仅当存在枚举器枚举它。

$\boldsymbol{Proof:}$首先证明如果有枚举器$E$枚举语言$A$，则有TM：$M$识别$A$，对于输入$w$，TM：$M$按照以下方式运行：

运行$E$，每当$E$输出一个串时，将其与$w$比较。

如果$w$曾经在$E$的输出序列中出现过，则接受。

现在证明另外一个方向，设$\Sigma^{ * }$中所有可能的串，如果TM：$M$识别语言$A$，则为$A$构造枚举器$E$如下：

对$i=1,2,\cdots$重复下列步骤。

对$s_1,s_2,\cdots,s_i$中的每一个，$M$以其作为输入运行$i$步。

如果有计算接受，则打印出相应的$s_j$。

TM还有着很多的变形，在此对这些TM进行介绍。

$\boldsymbol{Figure\ 2.28:}$

多维图灵机（multi-dimensional Turing machine） 的带子是多维的，如果带子的维度为$k$，也就意味着读头总共有$2k$种移动方向，无论是沿哪个方向移动都可以不断持续下去。对于多维图灵机而言，在运行的任意时刻，在带上的非空白的内容都可以被一个有限的$k$维立方体所包含，这使得在带子上的字符串可以按照一种方式组合成在一维带上的字符串，这里的做法和在计算机种存放多维数组的方式一样。

$\boldsymbol{Theorem\ 2.29:}$

多维图灵机和基本图灵机等价。

$\boldsymbol{Figure\ 2.30:}$

多头图灵机（multi-head Turing machine） 是指在一条带上有多个读头，它们都受到图灵机的有穷控制器的统一控制，图灵机根据当前的状态和这多个读头当前读到的字符决定要执行的移动，各个读头要印刷的字符和所移动的方向都可以是相互独立的。

$\boldsymbol{Theorem\ 2.31:}$

多头图灵机和基本图灵机等价。

$\boldsymbol{Figure\ 2.32:}$

离线图灵机（off-line Turing machine） 是一种多带图灵机，其中一条输入带是只读带，通常用符号$￠$放在左边、$$ $放在右边来限定其有限长的输入串存放区域，不允许读头移出它们所限定的输入串之外。它是多带图灵机的一种特例。如果还限制只读带上的读头从左向右移动，那么称这种图灵机为 在线图灵机（on-line Turing machine） 。

$\boldsymbol{Theorem\ 2.33:}$

离线图灵机和基本图灵机等价，在线图灵机和基本图灵机等价。

$\boldsymbol{Figure\ 2.34:}$

下推自动机可以被视作是一种非确定的多带图灵机。它有一条只读的输入带且输入带不能左移，还有一条存储带可以印刷符号且读头可以左右移动，但是当其向左移动时必须在当前注视的带方格种印刷空白符号$B$，因此读头所注视的字符右边都是空白符号。一般情况下，当它向右移动时，应该在注视的带方格上印刷一个非空白字符。满足这些条件的图灵机为称为是 多栈机（mulit-stack machine） 。

一个确定的 双栈机（double stack machine） 是一个确定的图灵机，它具有一条只读的输入带和两条存储带。存储带上的读头左移时只能印刷空白符号。

$\boldsymbol{Theorem\ 2.35:}$

任意一个单带图灵机都可以被一个确定的双栈机模拟。

$\boldsymbol{Figure\ 2.36:}$

计数机（counter machine） 是一种离线图灵机，它除了一条只读输入带以外还有若干条用来计数的单向无穷带，用于$n$个用于计数的计数机被称为$n$计数机。用于计数的带上仅有两种字符：一个为相当于作为栈底符号的$Z$，该字符也可以看作计数带的首符号，它仅出现在用于计数的带的最左端；另一个是空白符$B$，总共带上所记的数就是从$Z$开始到读头当前位置所含的$B$的个数。

$\boldsymbol{Theorem\ 2.37:}$

任意一个图灵机都可以被一个双计数机模拟。

$\boldsymbol{Figure\ 2.38:}$

队列自动机（queue automaton） 类似于PDA，只是把栈换成了队列，这个过程也可以用图灵机来表示。

$\boldsymbol{Theorem\ 2.39:}$

一个语言被一个确定型队列队列自动机识别当且仅当该语言是图灵可识别的。

$\boldsymbol{Figure\ 2.40:}$

随机存取机（random access machine,RAM） 含有无穷多个存储单元，这些存储单元被编号成$0,1,2,\cdots$，每个存储单元可以存放一个任意的整数。RAM还有有穷个可以保存任意整数的算术寄存器，这些整数可以被译码成各类计算机指令。显然如果选择合适的指令集合，RAM就可以模拟现有的任何计算机。

$\boldsymbol{Theorem\ 2.41:}$

如果RAM的基本指令都能用图灵机实现，那么就可以用图灵机实现RAM。

图灵机和PSG的等价性

$\boldsymbol{Theorem\ 2.42:}$

对于任意一个PSG：$G=(V,T,P,S)$，存在TM：$M$，使得$L(M)=L(G)$。

$\boldsymbol{Proof:}$让$M$有两条带，第一条带用于存放输入字符串$ww$，第二条带用于产生$w$，在第二条带上存放的是一个句型，开始启动的时候这个句型是$S$。如果第二条带上的句型是$\gamma$，$M$将按照某种策略在$\gamma$中选择一个字串$\alpha$使得它为$G$的某个产生式的左部，再用$\alpha$的产生式的某个候选式去替换$\alpha$。当第二条带上的内容为一个句子的时候，就将其与第一条带上的$w$比较，如果相等就接受$w$，否则就继续去寻找能够产生$w$的派生。

$\boldsymbol{Theorem\ 2.43:}$

对于任意一个TM：$M$，存在一个PSG：$G=(V,T,P,S)$，使得$L(G)=L(M)$。

$\boldsymbol{Proof:}$设$L$是$G$接受的语言，为了使得$G$产生$M$所识别的字符串，首先考虑让$G$产生$\Sigma^{ * }$中任意一个字符串的变形，然后让$G$模拟$M$处理这个字符串的变形，如果$M$接受它就把字符串的变形还原成该字符串。这里的变形是指让每个字符对应一个二元组，例如对于$a$生成$(a,a)$。对于$\forall(a_1,a_1)(a_2,a_2)\cdots(a_n,a_n)\in(\Sigma\times\Sigma)^{ * }$，可以将其看成$a_1a_2\cdots a_n$的两个副本，这一的字符串称为 双副本串（double-copy string） 。然后$G$在一个副本上模拟$M$的识别动作，如果$M$进入终止状态，则$G$将句型中除另一个副本以外的所有字符消去以得到句子。

下面给出一个合理的$G=((\Sigma\cup${$\epsilon$}$)\times\Gamma\cup${$A_1,A_2,A_3$}$\cup Q,\Sigma,P,A)$，其中{$A_1,A_2,A_3$}$\cap\Gamma=\varnothing$，$P$包含如下的产生式：

$A_1\rightarrow q_0A_2$，准备模拟$M$从$q_0$启动。

对于$\forall a\in\Sigma,A_2\rightarrow(a,a)A_2$，$A_2$首先生成任意的形如$(a_1,a_1)(a_2,a_2)\cdots(a_n,a_n)$的串。

$A_2\rightarrow A_3$，生成双副本子串$(a_1,a_1)(a_2,a_2)\cdots(a_n,a_n)$后准备用$A_3$在子串后生成一系列相当于空白符的子串，为$G$能够顺利地模拟$M$在处理相应的输入字符串的过程中将读头移向输入串右侧的初始为$B$的带方格做准备。

$A_3\rightarrow(\epsilon,B)A_3$，由于$M$在处理一个字符时不知道要用到输入串右侧的多少个初始为$B$的带方格，所以让$A_3$生成一系列相当于空白符的子串$(\epsilon,B)(\epsilon,B)\cdots(\epsilon,B)$。

$A_3\rightarrow\epsilon$。

对于$\forall a\in\Sigma\cup${$\epsilon$}$,\forall q,p\in Q,\forall X,Y\in\Gamma$，如果$\delta(q,X)=(p,Y,R)$则$q(a,X)\rightarrow(a,Y)p$，这是$G$模拟$M$的一次右移。

对于$\forall a,b\in\Sigma\cup${$\epsilon$}$,\forall q,p\in Q,\forall X,Y,Z\in\Gamma$，如果$\delta(q,X)=(p,Y,L)$则$(b,Z)q(a,X)\rightarrow p(b,Z)(a,Y)$，这是$G$模拟$M$的一次左移。

对于$\forall a\in\Sigma\cup${$\epsilon$}$,\forall q\in F,(a,X)q\rightarrow qaq,q(a,X)\rightarrow qaq,q\rightarrow\epsilon$。

丘奇-图灵论题

读者读到这里可能会很奇怪，为什么在前文中有些证明给出了TM的转移函数和形式化定义，但是有些证明却只能简单地描述了读头的移动方式和带子的管理方式，这并不是没有理由的，现在对丘奇-图灵论题进行介绍。

非形式化地说，算法是为实现某个任务而构造的简单指令集，在20世纪以前入门对算法只有直观的认识，在Alonzo Church（1903~1995）和Alan Turing（1912~1954）在1936年所写的文章中给出了算法的明确定义，丘奇使用$\lambda$-演算这一记号系统来定义算法，图灵使用机器来左同样的事情，这两个定义是等价的，算法的非形式化概念和精确定义之间的这个联系被称为 丘奇-图灵论题（Church-Turing thesis） ，现在给出丘奇-图灵论题的一个说明：

丘奇创造了一种称为$M$的机械方法，它通过数学和逻辑的方式来完成任务，这个方法$M$满足以下条件：

$M$中的指令的数目必须是有限的。

方法在执行有限数量的步骤后就会产生输出。

它不应该是虚构的，在现实生活中可以实现。

它不需要任何复杂的理解。

这个论题认为对于任何可以用有效算法解决的问题，都存在解决此问题的TM。这个论题无法被证明，因为它涉及到了有效算法的直观概念，但TM是形式化的、严格的。丘奇-图灵论题指出TM是被用作算法定义的一个精确模型，实际上不必划分过多的时间在TM的低层次程序上，只需要相信TM刻画了所有的算法即可。在承认这一点的前提下，下面将描述TM算法的方法标准化：

形式化描述：详细地写出TM的状态、转移函数等，也是先前最常见的描述方式。

实现描述：使用日常语言描述TM的动作，如如何移动读写头、怎么在带子上存储数据等，这种程度的描述没有给出状态和转移函数的细节。

高层次描述：使用日常语言来描述算法，但忽略了实现的细节，这种程度的描述不提及TM应该如何管理它的带子和读头。

前文已经给出了很多TM的描述，它们都是形式化描述或者是实现描述，这有助于理解TM并增强使用它们的信心，有了这样的信心便足以进行高层次描述。

TM的输入总是一个串，要想让TM解决更多问题，例如把多项式、图、文法、自动机等作为输入，就要把这些对象字符串化，可以设计一个TM来对这些串进行适当的解码，使之被解释为所希望的对象，为了方便描述，对于一个对象$O$，称它编码成字符串的记号是$< O >$，也可以将多个对象$O_1,O_2,\cdots,O_n$编码成一个串$< O_1,O_2,\cdots,O_n >$。选择何种方式进行编码是不重要的，因为TM总能将一种转换成另一种。

图灵可识别语言和可判定语言的封闭性

$\boldsymbol{Theorem\ 2.44:}$

图灵可识别语言类在并、连接、克林闭包、交和同态运算下封闭。

$\boldsymbol{Proof:}$

（1）并运算：

有TM：$M_X,M_Y$分别识别语言$X,Y$，识别$X\cup Y$的TM：$M_{XY}$如下：

对于输入串$w$：

逐步地在$w$上交替运行$M_X,M_Y$，如果其中任何一个接受，那么$M_{XY}$接受。如果两个机器都停机且拒绝，那么$M_{XY}$就拒绝。

（2）连接运算：

有TM：$M_X,M_Y$分别识别语言$X,Y$，识别$XY$的TM：$M_{XY}$如下：

对于输入串$w$：

$M_{XY}$将会非确定地将输入串分为$s_1$和$s_2$。

在$s_1$上运行$M_X$，如果$M_Y$接受就进入步骤3，如果$M_X$停机且拒绝，那么$M_{XY}$就拒绝。

在$s_2$上运行$M_Y$，如果$M_Y$接受那么$M_{XY}$就接受，如果$M_Y$停机且拒绝，那么$M_{XY}$就拒绝。

（3）克林闭包运算：

有TM：$M_X$识别语言$X$，识别$X^{ * }$的TM：$M$如下：

对于输入串$w$：

$M$将会非确定地将输入串$w$分为子串$s_1,s_2,\cdots,s_n$。

在这些串上运行$M_X$，如果$M_X$接受了所有子串那么$M$就接受，否则$M$就拒绝。

（4）交运算：

有TM：$M_X,M_Y$分别识别语言$X,Y$，识别$X\cap Y$的TM：$M_{XY}$如下：

对于输入串$w$：

在$w$上运行$M_X$，如果$M_X$接受就进入步骤2，否则$M_{XY}$就拒绝。

在$w$上运行$M_Y$，如果$M_Y$接受那么$M_{XY}$接受。否则$M_{XY}$就拒绝。

（5）同态运算：

有TM：$M_X$分别识别语言$X$，有同态$h$，识别$h(X)$的TM：$M$如下：

对于输入串$w$：

$M$会按照字典顺序选择全体字符串中的一个字符串$s$，如果有$h(s)=w$就进入步骤2.

在$s$上运行$M_X$，如果$M_X$接受那么$M$就接受。

$\boldsymbol{Theorem\ 2.45:}$

可判定语言类在并、连接、克林闭包、补和交运算下封闭。

$\boldsymbol{Proof:}$

（1）并运算：

有TM：$M_X,M_Y$分别判定语言$X,Y$，判定$X\cup Y$的TM：$M_{XY}$如下：

对于输入串$w$：

在$w$上运行$M_X$，如果它接受那么$M_{XY}$就接受，如果$M_X$拒绝了就进入步骤2。

在$w$上运行$M_Y$，如果它接受那么$M_{XY}$就接受，如果$M_Y$拒绝了$M_{XY}$就拒绝。

（2）连接运算：

有TM：$M_X,M_Y$分别判定语言$X,Y$，判定$XY$的TM：$M_{XY}$如下：

对于输入串$w$：

$M_{XY}$将会非确定地将输入串分为$s_1$和$s_2$。

在$s_1$上运行$M_X$，如果$M_Y$接受就进入步骤3，如果$M_X$拒绝，那么$M_{XY}$就拒绝。

在$s_2$上运行$M_Y$，如果$M_Y$接受那么$M_{XY}$就接受，如果$M_Y$拒绝，那么$M_{XY}$就拒绝。

（3）克林闭包运算：

有TM：$M_X$识别语言$X$，识别$X^{ * }$的TM：$M$如下：

对于输入串$w$：

$M$将会非确定地将输入串$w$分为子串$s_1,s_2,\cdots,s_n$。

在这些串上运行$M_X$，如果$M_X$接受了所有子串那么$M$就接受，如果有子串的结果是拒绝那么$M$就拒绝。

（4）补运算：

有TM：$M_X$识别语言$X$，识别$\overline{X}$的TM：$M$如下：

对于输入串$w$：

在$w$上运行$M_X$，如果$M_X$接受那么$M$就拒绝，否则$M$就接受。

（5）交运算：

有TM：$M_X,M_Y$分别识别语言$X,Y$，识别$X\cap Y$的TM：$M_{XY}$如下：

对于输入串$w$：

在$w$上运行$M_X$，如果$M_X$接受就进入步骤2，否则$M_{XY}$就拒绝。

在$w$上运行$M_Y$，如果$M_Y$接受那么$M_{XY}$接受。否则$M_{XY}$就拒绝。

线性有界自动机和上下文有关语言

线性有界自动机

$\boldsymbol{Definition\ 3.1:}$

现在给出 线性有界自动机（linear bounded automaton,LBA） 的介绍，它是一种非确定的图灵机，这个图灵机满足下列两个条件：

输入字母表包含两个特殊的符号$￠$和$¥$，其中$￠$作为输入符号串的左端标志，¥作为输入符号串的右端标志。
LBA的读头只能在$￠$和$¥$之间移动，且LBA不能在端点符号$￠$和$¥$上面打印另外一个符号。

一台LBA可以被视为一个八元组$M=(Q,\Sigma,\Gamma,\delta,q_0,￠,¥,F)$，其接受的语言$L(M)=${$w|w\in(\Sigma-${$￠,¥$}$)^{ * }且\exists q\in F使得q_0￠w$\vdash^{ * }￠\alpha q\beta¥$}，其中$\alpha,\beta,w\in\Sigma^{ * }$。在LBA中它所提供的存储空间受限于它的输入规模，这也是这个计算模型的名称的由来。

类似地，LBA也有格局的概念，显然如果$M$是一个有$q$个状态和$g$个带子符号的LBA，对于长度为$n$的带子，$M$恰好有$qng^n$个格局。

线性有界自动机示意图

线性有界自动机和上下文有关文法的等价性

$\boldsymbol{Theorem\ 3.2:}$

如果$L$是CSL且$\epsilon\notin L$，则存在LBA：$M$使得$L=L(M)$。

$\boldsymbol{Proof:}$由于$L$是CSL，不妨设CSG：$G=(V,T,P,S)$使得$L=L(G)$，用一个双道的图灵机来模拟$G$，在$M$的第一道上存放字符串$￠w¥$，在第二道上全是空白符。$M$启动后首先在第二道的与$w$的首字符对应的带方格内印刷上$G$的开始符号$S$，然后类似于前文中证明图灵机与PSG等价那样的在第二道上生成$w$的推导，由于$G$是CSG，所以如果第二道上的句型长度超过$|w|$就意味着这次推导失败了，如果某次推导成功了就接受$w$，显然对于LBA而言推导是有上限的，此时依旧都是推导失败那么就拒绝。

$\boldsymbol{Theorem\ 3.3:}$

对于任意$L$，若$\epsilon\notin L$且存在LBA：$M=(Q,\Sigma,\Gamma,\delta,q_0,￠,¥,F)$使得$L=L(M)$，那么$L$是CSL。

$\boldsymbol{Proof:}$也类似于前文中证明TM与PSG等价的过程，主要是根据给定的LBA构造出$G$，这里的双副本串是形如$(a_1,q_0￠a_1)(a_2,a_2)\cdots(a_n,a¥)$的符号行，当长度为一时其为$(a,q_0￠a¥)$，$P$包含如下的产生式：

对于$\forall a\in\Sigma-${$￠,¥$}有$A_1\rightarrow(a,q_0￠a)A_2$，准备模拟$M$从$q_0$启动并生成双副本串$(a_1,q_0￠a_1)(a_2,a_2)\cdots(a_n,a¥)$中的$(a_1,q_0￠a_1)$并将生成剩余子串的任务交给$A_2$。

对于$\forall a\in\Sigma-${$￠,¥$}有$A_1\rightarrow(a,q_0￠a¥)$，用于生成双副本串$(a,q_0￠a¥)$。

对于$\forall a\in\Sigma-${$￠,¥$}有$A-2\rightarrow(a,a)A_2|(a,a¥)$，$A_2$生成子串。

对于$\forall a,b\in\Sigma-${$¥$}$,\forall q,p\in Q,\forall X,Y,Z\in\Gamma,X\neq¥$，如果$\delta(q,X)=(p,Y,R)$，则有$(a,qX)(b,Z)\rightarrow(a,Y)(b,pZ)$，$G$模拟$M$的一次右移。

对于$\forall a,b\in\Sigma-${$￠$}$,\forall q,p\in Q,\forall X,Y,Z\in\Gamma$，如果$\delta(q,X)=(p,Y,L)$，则有$(b,Z)(a,qX)\rightarrow(b,pZ)(a,Y)$，$G$模拟$M$的一次左移。

对于$\forall a\in\Sigma,\forall q\in F,\forall X,Y\in\Gamma-${$B$}有$(a,XqY)\rightarrow a$，由于$q$为终止状态，可以消除句型中的状态$q$。

对于$\forall a\in\Sigma-${$￠,¥$}$,\forall X\in\Gamma-${$B$}有$(a,X)b\rightarrow ab,a(b,X)\rightarrow ab$。

上下文有关语言的性质

之前因为还没有介绍LBA，所以没有给出CSL的性质，下文将进行介绍。

$\boldsymbol{Theorem\ 3.4:}$

CSL类在并、连接、交、补、克林闭包和反转运算下封闭，在此仅对前两者进行证明。

$\boldsymbol{Proof:}$

（1）并运算：

有CSG：$G_1=(N_1,T_1,P_1,S_1),G_2=(N_2,T_2,P_2,S_2),L_1=(G_1),L_2=L(G_2)$，不妨令$N_1\cap N_2=\varnothing$，考虑文法$G=(S\cup N_1\cup N_2,T_1\cup T_2,${$S\rightarrow S_1,S\rightarrow S_2$}$\cup P_1\cup P_2,S)$，其中$S\notin N_1\cup N_2$，这里的$G$显然是CSG。

（2）连接运算：

设CSG：$G_1=(N_1,T,P_1,S_1),G_2=(N_2,T,P_2,S_2),L_1=(G_1),L_2=L(G_2)$，不妨令$N_1\cap N_2=\varnothing$，考虑文法$G=(S\cup N_1\cup N_2,T,${$S\rightarrow S_1S_2$}$\cup P_1\cup P_2,S)$，其中$S\notin N_1\cup N_2$，这里的$G$显然是CSG。

$\boldsymbol{Note\ 3.5:}$

不同于RL和CFL，CSL没有对应的“泵引理”，事实上CSL的表示能力是相当强大的，例如{$a^p|p是素数$}也是一个CSL，这样一个语言显然不具有先前介绍的“泵引理”那样的性质。到目前为止也不具备判断一个语言不是CSL的好的方法，但是依旧可以证明部分语言不是CSL。

根据乔姆斯基文法体系，可以知道CSL是图灵可识别语言，但是无法得知CSL是否是可判定的，下面给出了相关定理。

$\boldsymbol{Theorem\ 3.6:}$

任意CSL都是可判定的，也就是说CFL、DCFL和RL也都是可判定的。

$\boldsymbol{Proof:}$对于任意CSL：$L$，有CSG使得$L(G)=L$，下面给出一个判定$L$的TM：$M$：

$M=$“对于输入$< w >$，其中$w$是CSL：

模拟LBA：$A$使得$L(G)=L(A)$，$A$有$q$个状态、$g$个带子符号和长度为$n$的带子。

在$w$上运行$A$，并且记录$A$在这个过程中产生的格局。

如果$A$接受则$M$接受，如果$A$拒绝或记录的格局超过了$qng^n$个就拒绝。

$\boldsymbol{Theorem\ 3.7:}$

CSL类是可判定语言类的真子类。

$\boldsymbol{Proof:}$考虑所有可能的CSG：$G_i=(N_i,${$0,1,\cdots,9$}$,S_i,P_i)$，这些文法可以用于生成数字字符串，它们按照某种顺序排列。现在定义语言$L=${$i|i\notin L(G_i)$}，显然判定一个CSG是否能生成一个长度有限的字符串是可以由TM解决的，所以$L$一定是一个PSL。假定$L$是CSL，那么就存在一个CSG：$G_k$使得$L(G_k)=L$，因为$G_1,G_2,\cdots$已经包含了所有可能的CSG。若$k\in L(G_k)$，根据$L$的定义，那么$k\notin L$，发生矛盾；若$k\in L(G_k)$便也会发生矛盾。故$L$表示一个CSL，CSL都是可判定的，所以CSL类是可判定语言类的真子类。

可判定性

可判定语言

根据丘奇-图灵论题，前文用TM定义了算法的概念，虽然计算机科学的绝大部分是研究可求解问题的，但是实际上也存在着算法解决不了的问题。通常人们追求问题的答案，而在此时试图证明该问题的不可解性似乎没有什么用处。但是研究不可解性有两个理由：

知道一个问题在算法上是不可解的，也就不必浪费去寻找不可能的解法，为了更好地使用计算机，就必须正确地认识它的能力和局限。

锻炼人的能力，即使处理的问题都是可解的，了解不可解性也能激发想象力，并使人全面而透彻地理解什么是计算。

在之前已经介绍了RL、CFL的判定问题，在介绍了TM之后，可以回过头来看这些问题，例如DFA的 接受问题（acceptance problem） ，即检测一个特定的DFA是否接受一个事先给定的串，不妨令$A_{DFA}=${$< B,w >|B是DFA且接受输入串w$}，那么问题“DFA是否接受输入$w$和问题“$< B,w >$是否是$A_{DFA}$的元素”是相同的，如果可以证明$A_{DFA}$是可判定的，也就意味着“一个给定的DFA是否接受一个给定的串”是可判定的。

$\boldsymbol{Theorem\ 4.1:}$

$A_{DFA}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$A_{DFA}$的TM：$M$：

$M=$“对于输入$< B,w >$，其中$B$是DFA，$w$是串”：

在输入$w$上模拟$B$。

如果模拟以接受状态结束则接受，如果以非接受状态结束则拒绝。

$\boldsymbol{Theorem\ 4.2:}$

$A_{NFA}=${$< B,w >|B是NFA且接受输入串w$}，$A_{NFA}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$A_{NFA}$的TM：$M$：

$M=$“对于输入$< B,w >$，其中$B$是NFA，$w$是串”：

将$B$转换成等价的DFA：$C$。

在输入$w$上模拟$C$。

如果模拟以接受状态结束则接受，如果以非接受状态结束则拒绝。

$\boldsymbol{Theorem\ 4.3:}$

$A_{REX}=${$< B,w >|B是正则表达式，w是串，R派生w$}，$A_{REX}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$A_{REX}$的TM：$M$：

$M=$“对于输入$< R,w >$，其中$R$是正则表达式，$w$是串”：

将$R$转换成等价的DFA：$C$。

在输入$w$上模拟$C$。

如果模拟以接受状态结束则接受，如果以非接受状态结束则拒绝。

上面很清晰地说明了对于可判定性，用DFA、NFA或正则表达式表达图灵机都是等价的，因为TM可以将它们的编码进行相互转换。

在之前也介绍了DFA的空性质测试，也就是检查一个DFA是否根本不接受任何串。令$E_{DFA}=${$< A >|A是一个DFA且L(A)=\varnothing$}。同时也有检查两个DFA是否识别同一个语言的问题，记$EQ_{DFA}=${$< A,B >|A和B都是DFA且L(A)=L(B)$}。

$\boldsymbol{Theorem\ 4.4:}$

$E_{DFA}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$E_{DFA}$的TM：$M$：

$M=$“对于输入$< A >$，其中$A$是DFA：

标记$A$的初始状态。

重复下列步骤，直到出现无法标记新状态的情况。

对于一个状态，如果有一个到达它的转移是从某个已经标记过的状态出发的，则将其标记。

如果没有接受状态被标记就接受，否则就拒绝。

$\boldsymbol{Theorem\ 4.5:}$

$EQ_{DFA}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$EQ_{DFA}$的TM：$T$：

$T=$“对于输入$< A,B >$，其中$A$和$B$是DFA：

模拟一个DFA：$C$使得$L(C)=((L(A)\cap\overline{L(B)})\cup(\overline{L(A)}\cap L(B)))$。

在输入$< C >$上运行$\boldsymbol{Theorem\ 4.4}$中给出的TM：$M$。

如果$M$接受就接受，否则就拒绝。

由于先前已经给出了CFG和PDA之间的相互转换过程，它们的可判定性问题之间也可以相互转换。

$\boldsymbol{Theorem\ 4.6:}$

$A_{CFG}=${$< G,w >|G是CFG，w是串，G派生w$}，$A_{CFG}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$A_{CFG}$的TM：$S$：

$S=$“对于输入$< G,w >$，其中$G$是CFG，$w$是串”：

将$G$转换成等价的CNF。

列出所有$2|w|-1$步的派生，除非$|w|=0$，此时列出一步以内的派生。

如果这些派生中有一个产生了$w$则接受，否则拒绝。

$\boldsymbol{Theorem\ 4.7:}$

$E_{CFG}=${$< G >|G是一个CFG且L(A)=\varnothing$}，$E_{CFG}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$E_{CFG}$的TM：$M$：

$M=$“对于输入$< G >$，其中$G$是CFG：

标将$G$中所有的终结符全部作上标记。

重复下列步骤，直到出现无法标记新的变元。

如果$G$有产生式$A\rightarrow U_1U_2\cdots U_k$且$U_1,U_2,\cdots,U_k$中的每一个符号都已经被作过标记，那么将变元$A$标记。

如果起始变元没有被标记就接受，否则就拒绝。

$\boldsymbol{Theorem\ 4.8:}$

$A_{LBA}=${$< M,w >|M是LBA，w是串，M接受w$}，$A_{LBA}$是可判定语言。

$\boldsymbol{Proof:}$下面给出一个判定$A_{LBA}$的TM：$L$：

$L=$“对于输入$< M,w >$，其中$M$是LBA，$w$是串：

在$w$上模拟$M$共$qng^n$步，或者直到它停机，其中$M$有$q$个状态、$g$个带子符号和长度为$n$的带子。

如果$M$停机则当它接受时接受，否则拒绝，如果它没有停机那么拒绝。

不可判定语言

$\boldsymbol{Theorem\ 4.9:}$

$A_{TM}=${$< M,w >|M是TM，w是串，M接受w$}，$A_{TM}$是可识别语言。

$\boldsymbol{Proof:}$下面给出一个判定$A_{TM}$的TM：$U$：

$U=$“对于输入$< M,w >$，其中$M$是TM，$w$是串：

在输入$w$上模拟$M$。

如果$M$进入接受状态那么接受，如果$M$进入拒绝状态那么拒绝。

注意如果$M$在$w$上发生了循环，则机器$U$在输入$< M,w >$上循环，这也是为何$U$无法判定$A_{TM}$的原因。$U$本身也很有意思，它是所谓 通用图灵机（universal Turing machine） 的一个例子，之所以称为是通用图灵机，是因为它能够模拟其他任何的图灵机。

$\boldsymbol{Theorem\ 4.10:}$

$A_{TM}$是不可判定语言。

$\boldsymbol{Proof:}$假设$A_{TM}$是可判定的，它的判定器是$H$，令$M$为TM、$w$为一个串，在输入$< M,w >$上，如果$M$接受$w$则$H$就停机且接受$w$，如果$M$不接受$w$则$H$也会停机但拒绝$w$。考虑TM：$D$：

$D=$“对于输入< M >，其中$M$是一个TM”：

在输入$< M,< M > >$上运行$H$。

如果$H$接受就拒绝，反之就接受。

也就是说当$M$不接受$< M >$的时候$D$就接受输入$< M >$，如果$M$接受$< M >$的时候$D$就拒绝输入$< M >$，并且$D$是一个判定器。当以$D$的描述$< D >$作为$D$的输入时会发生矛盾，故$D$不存在，于是$H$不存在，证毕。

$\boldsymbol{Theorem\ 4.11:}$

存在不能被任何TM识别的语言。

$\boldsymbol{Proof:}$在集合论的学习中可以知道自然数集合$N$是可数的，而实数集合$R$是不可数的，也就是说$N$的势比$R$的势要小，不存在一个从$N$到$R$的双射。在证明中也将会这么做。

对于任意的字母表$\Sigma$，其上所有串的集合$\Sigma^{ * }$是可数的，这是因为对于每个自然数$n$，长度为$n$的串只有有限多个，可以以此写下长度为$0$的串、长度为$1$的串、长度为$2$的串，这样就可以构造出$\Sigma^{ * }$的序列。

所有TM构成的集合是可数的，因为每个TM：$M$都可以对应于一个编码$< M >$，只要去掉不是图灵机编码的串便得到了一个TM的序列。

$\Sigma$上所有语言构成的集合$\mathcal{L}$实际上是所有串的集合$\Sigma^{ * }$的幂集，利用集合论中的康托尔定理可知$\mathcal{L}$是不可数的，这也就意味着所有语言的集合与所有TM的集合之间不能有一一对应，可以下结论：存在不能被任何TM识别的语言。

$\boldsymbol{Definition\ 4.12:}$

一个语言的补是由不在这个语言中的所有串构成的语言，如果一个语言是一个图灵可识别语言的补集，就称它是 补图灵可识别的（co-Turing-recognizable） 。

$\boldsymbol{Theorem\ 4.13:}$

一个语言都是可判定的当且仅当它既是图灵可识别的，也是补图灵可识别的。

$\boldsymbol{Proof:}$如果$A$是可判定的，那么$\overline{A}$也是可判定的，故$A$是图灵可识别的，也是补图灵可识别的。

如果$A$和$\overline{A}$都是图灵可识别的，令它们的识别器分别为$A_1,A_2$，现在给出$A$的判定器：

$M=$“对于输入$w$”：

在输入$w$上并行运行$M_1$和$M_2$。

如果$M_1$接受就接受，如果$M_2$接受就拒绝。

$\boldsymbol{Corollary\ 4.14:}$

$\overline{A_{TM}}$不是图灵可识别的。

可归约性

语言理论中的不可判定问题

$\boldsymbol{Definition\ 5.1:}$

归约（reduction） 旨在将一个问题转化成另一个问题，且使得可以用第二个问题的解来解第一个问题。例如在新城市中认路，如果有一张地图在身那就容易多了，认路问题就归约得到地图问题。

当$A$可归约到$B$时解$A$不可能比解$B$更难，因为$B$的一个解给出了$A$的一个解，根据可计算性理论，如果$A$可归约到$B$，且$B$是可判定的，则$A$也是可判定的。如果$A$是不可判定的，且可归约到$B$，则$B$也是不可判定的。

$\boldsymbol{Theorem\ 5.2:}$

确定一个TM对给定的输入是否会停机的问题被称为 停机问题（halting problem） ，$HALT_{TM}=${$< M,w >|M是一个TM且对输入w停机$}，$HALT_{TM}$是不可判定的。

$\boldsymbol{Proof:}$设TM：$R$判定$HALT_{TM}$，可以构造识别$A_{TM}$的TM：$S$：

$S=$“在输入$< M,w >$上，此处$< M,w >$是TM：$M$和串$w$的编码”：

在输入$< M,w >$上运行TM：$R$。

如果$R$拒绝就拒绝。

如果$R$接受就在$w$上模拟$M$直到它停机。

如果$M$已经接受就接受，否则拒绝。

$\boldsymbol{Theorem\ 5.3:}$

$E_{TM}=${$< M >|M是一个TM且L(M)=\varnothing$}，$E_{TM}$是不可判定的。

$\boldsymbol{Proof:}$假定判定$E_{TM}$的TM为$R$，下面给出一个判定$A_{TM}$的TM：$S$：

$M_1=$“对于输入$x$，其中$x$是串：

如果$x\neq w$则拒绝。

如果$x=w$则在输入$w$上运行$M$，当$M$接受时则接受。

$S=$“对于输入$< M,w >$，其中$M$是TM、$w$是串：

用$M$和$w$的描述来构造上述TM：$M_1$。

在输入$< M_1 >$上运行$R$。

如果$R$接受就拒绝，否则就接受。

$\boldsymbol{Theorem\ 5.4:}$

$REGULAR_{TM}=${$< M >|M是一个TM且L(M)是正则语言$}，$REGULAR_{TM}$是不可判定的。

$\boldsymbol{Proof:}$假定判定$REGULAR_{TM}$的TM为$R$，下面给出一个判定$A_{TM}$的TM：$S$：

$M_2=$“对于输入$< M,w >$，$M$是TM，$x$是串”：

如果$x$具有形式$0^n1^n$则接受。

如果$x$不具有此形式，则在输入$w$上运行$M$，如果$M$接受则接受。

$S=$“对于输入$< M,w >$，其中$M$是TM，$w$是串”：

利用$M$和$w$构造相应的TM：$M_2$。

在输入$< M_2 >$上运行$R$。

如果$R$接受则接受，否则拒绝。

$\boldsymbol{Theorem\ 5.5:}$

$EQ_{TM}=${$< M_1,M_2 >|M_1和M_2都是TM且L(M_1)=L(M_2)$}，$EQ_{TM}$是不可判定的。

$\boldsymbol{Proof:}$假定判定$EQ_{TM}$的TM为$R$，下面给出一个判定$E_{TM}$的TM：$S$：

$S=$“对于输入$< M >$，其中$M$是TM”：

在输入$< M,M_1 >$上运行$R$，其中$M_1$是拒绝所有输入的TM。

如果$R$接受则接受，否则拒绝。

$\boldsymbol{Theorem\ 5.6:}$

$E_{LBA}=${$|B是一个LBA且L(B)=\varnothing$}，$E_{LBA}$是不可判定的。

$\boldsymbol{Proof:}$通过构造LBA：$B$使得它识别的语言包含了$M$在$w$上的所有接受计算历史就可以实现归约。设$x$是$M$在$w$上的一个接受计算历史$C_1,C_2,\cdots,C_l$，不妨表示为一个串并用#相互隔开。$B$首先对于输入的接受计算历史$x$会先将其分解为$C_1,C_2,\cdots,C_l$，之后$B$检查$C_i$是否满足接受计算历史的三个条件：

$C_1$是$M$在$w$上的起始格局。

每个$C_{i+1}$都是$C_i$的合法结果。

$C_l$是$M$的一个接受格局。

很容易实现这样的$B$，在此不作详细的说明。

假设TM：$R$判定$E_{LBA}$，下面给出一个判定$A_{TM}$的TM：$S$：

$S=$“对于输入$< M,w >$，其中$M$是TM，$w$是串”：

按照上述思路从$M$和$w$中构造LBA：$B$。

在输入$$上运行$R$。

如果$R$拒绝则接受，否则拒绝。

$\boldsymbol{Theorem\ 5.7:}$

$ALL_{CFG}=${$< G >|G是一个CFG且L(G)=\Sigma^{ * }$}，$EQ_{CFG}=${$< G_1,G_2 >|G_1和G_2都是CFG且L(G_1)=L(G_2)$}，$ALL_{CFG}$和$EQ_{CFG}$都是不可判定的，$EQ_{CFG}$是补图灵可识别的，在此不作证明。

$\boldsymbol{Theorem\ 5.8:}$

赖斯定理（Rice’s theorem） 指出图灵可识别语言的所有非平凡性质都是不可判定的。

具体地说，设$P$是一个语言，它由TM的描述组成，且$P$满足两个条件：

$P$是非平凡的，它包含TM的描述但不是所有的。
$P$是TM的语言的属性，对于任意TM：$M_1,M_2$，若有$L(M_1)=L(M_2)$，那么$< M_1 >\in P$当且仅当$< M_2 >\in P$。

那么$P$就是一个不可判定语言。

$\boldsymbol{Proof:}$设$P$是满足属性的可判定语言，其判定机为$R_P$，设$T_\varnothing$是一个总是拒绝的TM，那么有$L(T_\varnothing)=\varnothing$。不妨设$< T_\varnothing >\notin P$，由于$P$是非平凡的，存在一个TM：$T$使得$< T >\in P$，下面给出一个判定$A_{TM}$的TM：$S$：

$S=$“对于输入$< M,w >$，其中$M$是TM，$w$是串”：

用$M$和$w$构造TM：$M_w$，其对于输入$x$：首先在$w$上模拟$M$，如果拒绝就拒绝；如果接受那么在$x$上模拟$T$，如果依旧是接受那么$M_w$就接受。

用TM：$R_P$确定是否有$< M_w >\in P$，如果是那么接受，如果否那么拒绝。

如果$M$接受$w$，那么TM：$M_w$可以模拟$T$。如果$M$接受$w$还接受$\varnothing$，那么$L(M_w)$等于$L(T)$，因此当且仅当$M$接受$w$时$< M_w >\in P$。

映射可归约性

$\boldsymbol{Definition\ 5.9:}$

函数$f:\Sigma^{ * }\rightarrow\Sigma^{ * }$是一个 可计算函数（computable function） ，如果有某个TM：$M$使得在每个输入$w$上$M$停机且此时只有$f(w)$出现在带子上。

$\boldsymbol{Definition\ 5.10:}$

语言$A$是 映射可归约（mapping reducible） 到语言$B$的，如果存在可计算函数$f:\Sigma^{ * }\rightarrow\Sigma^{ * }$使得1对于1每个$w$都有$w\in A\Leftrightarrow f(w)\in B$，记作$A\leq_m B$，称函数$f$为从$A$到$B$的归约。显然$\leq_m$是一个传递关系。

从A归约到B的函数f

$\boldsymbol{Theorem\ 5.11:}$

如果$A\leq_mB$且$B$是可判定的，则$A$也是可判定的。

$\boldsymbol{Proof:}$设$M$是$B$的判定器，$f$是从$A$到$B$的归约，下面给出$A$的判定器$N$：

$N=$“对于输入$w$，其中$w$是串”：

计算$f(w)$。

在$f(w)$上运行$M$，输出$M$的输出。

$\boldsymbol{Corollary\ 5.12:}$

如果$A\leq_mB$且$A$是不可判定的，则$B$也是不可判定的。

$\boldsymbol{Example\ 5.13:}$

在$\boldsymbol{Theorem\ 5.5}$的证明中隐含了一个从$E_{TM}$到$EQ_{TM}$的映射归约，此归约$f$将输入$< M >$映射到输出$< M,M_1 >$，其中$M_1$是拒绝所有输入的机器。

$\boldsymbol{Theorem\ 5.14:}$

如果$A\leq_mB$且$B$是图灵可识别的，则$A$也是图灵可识别的。

$\boldsymbol{Proof:}$设$M$是$B$的识别器，$f$是从$A$到$B$的归约，下面给出$A$的识别器$N$：

$N=$“对于输入$w$，其中$w$是串”：

计算$f(w)$。

在$f(w)$上运行$M$，输出$M$的输出。

$\boldsymbol{Corollary\ 5.15:}$

如果$A\leq_mB$且$A$不是图灵可识别的，则$B$不是图灵可识别的。

$\boldsymbol{Theorem\ 5.16:}$

$EQ_{TM}$既不是图灵可识别的，也不是补图灵可识别的。

$\boldsymbol{Proof:}$首先证明$EQ_{TM}$不是图灵可识别的，只要证明从$A_{TM}$可归约到$\overline{EQ_{TM}}$，考虑计算归约函数$f$的TM：$F$：

$F=$“对于输入$< M,w >$，其中$M$是TM，$w$是串”：

构造两个机器$M_1$和$M_2$：$M_1$对于任何输入都拒绝；$M_2$对于任何输入都在$w$上运行$M$，如果接受就接受。

输出$< M_1,M_2 >$。

证明$EQ_{TM}$不是补图灵可识别的，只要证明从$A_{TM}$可归约到$EQ_{TM}$，考虑计算归约函数$g$的TM：$G$：

$G=$“对于输入$< M,w >$，其中$M$是TM，$w$是串”：

构造两个机器$M_1$和$M_2$：$M_1$对于任何输入都接受；$M_2$对于任何输入都在$w$上运行$M$，如果接受就接受。

输出$< M_1,M_2 >$。

显然$w\in A_{TM}\Leftrightarrow f(w)\in\overline{EQ_{TM}}$且$w\in A_{TM}\Leftrightarrow g(w)\in EQ_{TM}$，也就是说$A_{TM}\leq_mEQ_{TM}$且$A_{TM}\leq_m\overline{EQ_{TM}}$。

$\boldsymbol{Note\ 5.17:}$

在之前和本文中都对一些语言之间的关系进行了讨论，下面给出了一个韦恩图表示各种语言之间的关系。

语言之间的关系

图灵可归约性

直观上来看$A_{TM}$和$\overline{A_{TM}}$应该是可以相互归约的问题，因为它们当中任一个问题的解都可以用来解另一个问题，但是$\overline{A_{TM}}\leq_mA_{TM}$是不正确的，因为$A_{TM}$是图灵可识别的而$\overline{A_{TM}}$不是。

$\boldsymbol{Definition\ 5.18:}$

语言$B$的一个 谕示（oracle） （也称为预言者）是一个能够报告某个串$w$是否为$B$的成员的外部装置，这个术语本身就意味着一种神奇的能力，意味着谕示的能力超越了算法的能力。一个 谕示图灵机（oracle Turing machine） （也称为预言机）是一种修改过的图灵机，它有着询问一个谕示的额外能力，记$M^B$为对语言$B$有谕示的谕示图灵机。

$\boldsymbol{Example\ 5.19:}$

考虑$A_{TM}$的一个谕示，那么可以给出判定$E_{TM}$的方法：

$T^{A_{TM}}=$“对于输入$< M >$，其中$M$是一个TM”：

构造TM：$N$，它对于任何输入，先对$\Sigma^{ * }$中的所有串并行运行$M$，如果$M$接受了其中任何一个串$N$就接受。

询问谕示以确定$< N,0 >\in A_{TM}$是否成立。

谕示回答“不”则接受，否则拒绝。

可以看出$T^{A_{TM}}$判定$E_{TM}$，于是说$E_{TM}$是相对于$A_{TM}$可判定的（decidable relative）。

$\boldsymbol{Note\ 5.20:}$

带$A_{TM}$的谕示的图灵机的能力依旧是有限的，它不能判定{$< M,w >|M是一个谕示图灵机且M^{A_{TM}}接受w$}。

$\boldsymbol{Definition\ 5.21:}$

称语言$A$ 图灵可归约（Turing reducible） 到语言$B$，如果$A$相当于$B$是可判定的，记作$S\leq_TB$。显然如果有$A\leq_mB$，那么$A\leq_TB$。显然$\leq_T$是一个传递关系。

$\boldsymbol{Theorem\ 5.22:}$

如果$A\leq_TB$且$B$是可判定的，那么$A$也是可判定的。

$\boldsymbol{Proof:}$如果$B$是可判定的，用判定$B$的时间过程来替换$B$的谕示即可。

递归定理

递归定理（recursion theorem） 是一个数学结论，在可计算性理论中起着重要作用，它与数理逻辑、自再生系统理论以及计算机病毒都有联系。递归定理指出，一台机器是有可能能够生产自己的。

$\boldsymbol{Theorem\ 6.1:}$

存在可计算函数$q:\Sigma^{ * }\rightarrow\Sigma^{ * }$，对任意串$w$，$q(w)$是TM：$P_w$的描述，$P_w$打印出$w$然后停机。

$\boldsymbol{Proof:}$可以给出一个计算$q(w)$的TM：$Q$：

$Q=$“对于输入串$w$”：

构造TM：$P_w$，其对于任何输入都会抹去输入、在带上写下$w$而后停机。

输出$< P_w >$。

接下来将试图给出一个TM：$SELF$，它可以打印出自己的描述，也就是可以实现 自引用（self-reference） ，它含有两个部分$A$和$B$，也就是说要让$SELF$打印出$< SELF >=< AB >$。$A$会先于$B$运行，它的任务是打印出$B$的描述，反过来$B$的任务是打印出$A$的描述，首先使用$P_{}$来定义$A$，也就是说$A$是一个打印出$$的TM，但是不能用$q(< A >)$定义$B$，否则会产生 循环定义（circular definition） ，这是违背逻辑法则的，为此还要找到一种方式定义$N$。

如果$B$能够获得到$$，那么它自然可以得到$q()$，也就是$A$，当$A$结束后留下了$$在带子上，也就是说$B$可以从带子上获得$$，在计算得到$< A >$后$B$便将其加在带子的前面，然后将$A$和$B$组合成一个机器写在带子上得到$< AB >=< SELF >$。总之：

$A=P_{}$，$B=$“对于输入$< M >$，其中$M$是一个TM的一部分”：

计算$q(< M >)$。

将其结果与$< M >$结婚来组成一个完整的图灵机描述。

打印这个描述，然后停机。

SELF的示意图

$\boldsymbol{Example\ 6.2:}$

打印下面两个语句的副本，在第二个副本上加引号：

“打印下面两个语句的副本，在第二个副本上加引号：”

上面这个句子便是一种自引用,第一行是$B$，第二行是$A$。

$\boldsymbol{Example\ 6.3:}$

Quine以哲学家Willard van Orman Quine（1908~2000）命名，表示一个可以生成他自己的完全的源代码的程序，图灵奖得主Ken Thompson（1943~）设计了一个可以实现该功能的C语言程序，虽然这段程序忽略了 #include < stdio.h >还假设了双引号的值为ASCII的值，并且要求程序写在同一行。

1

char*s="char*s=%c%s%c;main(){printf(s,34,s,34);}"; main(){printf(s,34,s,34);}

那么$A$对应于 "char*s=%c%s%c;main(){printf(s,34,s,34);}"，而$B$对应于 main(){printf(s,34,s,34);}。

$\boldsymbol{Theorem\ 6.4:}$

递归定理：设$T$是计算函数$t:\Sigma^{ * }\times\Sigma^{ * }\rightarrow\Sigma^{ * }$的一个TM。则存在计算函数$r:\Sigma^{ * }\rightarrow\Sigma^{ * }$的一个TM：$R$是的对于每一个$w$都有$r(w)=t(< R >,w)$。

这个定理表明，为了能够得到自己的描述还能用这个描述来计算的TM，只需要制造一个在这个定理中称为$T$的TM，使之以自己的描述作为输入的一部分，然后递归定理就产生一个新的机器$R$，它和$T$一样运行，只是$R$的描述被自动地装在$T$中，那么$T$便可以利用它自身的描述了。

$\boldsymbol{Proof:}$类似于构造$SELF$，分三部分$A,B,C$来构造TM：$R$，其中$T$由定理的叙述得出，$A$是由$q(< BT >)$描述的TM：$P_{< BT >}$，为了保持输入$w$只需要重新设计$q$使得$P_{< BT >}$先打印$w$即可，这样带子上包含$w< BT >$，然后$B$依旧是相同操作得到了$< ABT >=< R >$，最后把$< R,w >$传给$T$。

R的图示

递归定理是解决问题的有力工具，现在回到之前证明的一个定理，下面将使用递归定理证明它。

$\boldsymbol{Theorem\ 4.10:}$

$A_{TM}$是不可判定语言。

$\boldsymbol{Proof:}$假设$H$可以判定$A_{TM}$，构造下列TM：$B$：

$B=$“对于输入$w$，其中$w$是串”：

由递归定理得到自己的一个描述$$。

在输入$< B,w >$上运行$H$。

如果$H$拒绝则接受，否则拒绝。

产生了矛盾，所以$H$不存在。

$\boldsymbol{Theorem\ 6.5:}$

递归定理的 不动点（fixed point） 形式：设$t:\Sigma^{ * }\rightarrow\Sigma^{ * }$是一个可计算函数，则存在一个TM：$F$使得$t(< F >)$描述一个与$F$等价的TM。这里假设如果串不是一个正确的图灵机编码，那么它描述的TM立即拒绝。

$\boldsymbol{Proof:}$，现在给出TM：$F$：

$F=$“对于输入$w$”：

由递归定理得到它自己的一个描述$< F >$。

计算$t(< F >)$得到TM：$G$的描述。

在输入$w$上模拟$G$。

显然$< F >$和$t(< F >)=< G >$都描述了等价的TM。