数理逻辑5 -- 计算理论2

图灵机的示意图（Diagram）

上节笔记给出了图灵机的定义，那一大堆四元组构成的指令集真个是比汇编代码还要难懂。不仅难写，更难检查。因此，我们需要一种“简便”的图灵机表示方式。

我们说，一个图灵机的示意图包含以下内容：
(1) 令F1,F2,...,Fr${\mathcal{F}}_1,{\mathcal{F}}_2,...,{\mathcal{F}}_r$为任意图灵机，它们有共同的字符集为A={a0,a1,...,ak}$A=\{a_0,a_1,...,a_k\}$；
(2) 从平面上选择任意有限个点，称为顶点（vertex）；
(3) 对每个顶点，填上一个图灵机Fi${\mathcal{F}}_i$，同一个图灵机可填到多个顶点；
(4) 用箭头连接顶点，允许指向自身的肩头。每个箭头标上一个整数i$i$，其中1≤i≤k$1\le i\le k$。从同一个顶点出发的两个不同箭头，不许打同一个标签；
(5) 其中一个顶点画个圈圈围住它，表示初始顶点（initial vertex）

下图就是一个图灵机的示意图。

每个图灵机示意图都定义出了一个图灵机，它的四元组指令集由如下方法构成：
(1) 对图中的图灵机，写下它们所有的指令四元组，改写它们的状态符号，使得任意两个图灵机都没有共同的状态符号。但是，初始图灵机的状态符号保留不变；
(2) 对某个箭头→u$\stackrel{u}{\to }$连接的两个图灵机Fi,Fj${\mathcal{F}}_i,{\mathcal{F}}_j$，若左边的图灵机Fi${\mathcal{F}}_i$中的任意状态符号qs$q_s$，都不存在qsau$q_s{a}_u$开头的四元组指令，那么就增加qsauauqt$q_s{a}_u{a}_u{q}_t$指令进新构造的图灵机，其中qt$q_t$是右边图灵机Fj${\mathcal{F}}_j$的状态符号。

以上第2点是为了保证，若原本的图灵机Fi${\mathcal{F}}_i$停在qsau$q_s{a}_u$上时，右边的图灵机Fj${\mathcal{F}}_j$可以接着继续工作。

因此，图灵机示意图就构造了一个新的图灵机，给定磁带上的任意输入，它的工作方式如下：
(1) 示意图中的初始图灵机开始工作；
(2) 当某个图灵机停止时，查看此时磁头读取的符号au$a_u$，然后查看该图灵机对应的朝外的箭头，若这些箭头都不含有标签u$u$，那么整个示意图停止工作；
(3) 若(2)中的某一个箭头的标签是u$u$，那么该箭头对应的右边图灵机接着继续工作。

因此，我们就可以用示意图来构造各种图灵机。为此，我们需要进一步简化示意图的表达：
(1) 若一个顶点和另一个顶点相连接的箭头包含了所有的0,1,...,k$0,1,...,k$，那么我们用一个无标签箭头取代这k$k$个箭头；
(2) 若一个顶点和另一个顶点相连接的箭头包含了所有除u$u$以外的标签，那么我们用箭头−→−≠u$\stackrel{\ne u}{\to }$来表示这k−1$k-1$个箭头；
(3) 令F1F2${\mathcal{F}}_1{\mathcal{F}}_2$表示F1→F2${\mathcal{F}}_1\to {\mathcal{F}}_2$，令F1F2F3${\mathcal{F}}_1{\mathcal{F}}_2{\mathcal{F}}_3$表示F1→F2→F3${\mathcal{F}}_1\to {\mathcal{F}}_2\to {\mathcal{F}}_3$，等等。令F2${\mathcal{F}}^2$表示F→F$\mathcal{F}\to \mathcal{F}$，F3${\mathcal{F}}^3$表示F→F→F$\mathcal{F}\to \mathcal{F}\to \mathcal{F}$，等等。
(4) 若没有顶点被圈圈包起来，那么最左边的顶点就表示初始图灵机。

上述话语讲得云里雾里，我们来看几个具体的示意图。首先，我们需要三个基本的图灵机。

基本图灵机

假设字符集为A={a0,a1,...,ak}$A=\{a_0,a_1,...,a_k\}$，
1. r$\mathbf{\text{r}}$（右移机, right machine）：四元组指令形如q0aiRq1$q_0{a}_{i}R{q}_1$，因此右移机的指令个数为k+1$k+1$，它的操作很简单，读取一个符号，右移一格，停止。
2. l$\mathbf{\text{l}}$（左移机，left machine）：指令形如q0aiLq1$q_0{a}_{i}L{q}_1$，读一个符号，左移一格，停止。
3. aj$a_j$（常数机，constant machine）：指令形如q0aiajq1$q_0{a}_i{a}_j{q}_1$，因此它的指令个数也是k+1$k+1$个，操作是读一个符号，把它变成aj$a_j$，然后停止。

常用示意图

基于上面的基本图灵机，我们构造几个常用的示意图。这些就是比机器码好一点，比汇编难一点的“图灵机代码”。

首先，我们定义一些缩写。

缩写

∼$\sim$：表示任意符号
B⋯B$B\cdots B$：连续的空字符串
B⋯$B\cdots$：右边全是空字符
⋯B$\cdots B$：左边全是空字符
W$W$：任意非0长度的非空字符串
X$X$：形如BW1BW2B⋯Wn$B{W}_{1}B{W}_{2}B\cdots W_n$，其中n≥1$n\ge 1$

1. P$\mathbf{\text{P}}$，称P$P$机器。如下图， 它的作用是找出当前符号右边（不含当前）第一个空字符。它的指令集是q0aiRq1,1≤i≤k$q_0{a}_{i}R{q}_1,1\le i\le k$，以及q1aiaiq0，i>0$q_1{a}_i{a}_i{q}_0，i>0$。
   

2. Λ$\mathrm{\Lambda }$，称Λ$\mathrm{\Lambda }$机器，如下图，找出当前符号左边（不含当前）的第一个空字符。
   

3. R$\mathcal{R}$，右止机器（right-end machine），如下图，它的操作是∼––XBB⇒∼XB––B$\underset{\_}{\sim }XBB\Rightarrow \sim X\underset{\_}{B}B$，即若任意X$X$右边以两个空字符结束，那么从左往右，把磁头移到X$X$右边的第一个空字符位置。注意，上述式子中的下划线表示磁头位置。
   

4. L$\mathcal{L}$，左止机器（left-end machine），如下图，它的操作是BBX∼––⇒BB––X∼$BBX\underset{\_}{\sim }\Rightarrow B\underset{\_}{B}X\sim$，即找到X$X$左边第一个空字符位置。
   

5. T$\mathbf{\text{T}}$，左漂机器（left-translation machine），如下图，操作是∼––BWB⇒∼WB––B$\underset{\_}{\sim }BWB\Rightarrow \sim W\underset{\_}{B}B$，即把W$W$移到左边的空字符左方。
   

6. σ$\sigma$，漂移机器（shift machine），如下图，操作是BW1BW2B––⇒BW2B––⋯B$B{W}_{1}B{W}_2\underset{\_}{B}\Rightarrow B{W}_2\underset{\_}{B}\cdots B$，即W2$W_2$把W1$W_1$覆盖掉
   

7. C$\mathbf{\text{C}}$，清洗机器（clean-up machine），如下图，操作是∼BBXBWB––⇒∼WB––⋯B$\sim BBXBW\underset{\_}{B}\Rightarrow \sim W\underset{\_}{B}\cdots B$，即把中间的X$X$清洗掉。
   

8. K$\mathbf{\text{K}}$，词复制机器（word-copier），如下图，操作是BWB––⋯⇒BWBWB––⋯$BW\underset{\_}{B}\cdots \Rightarrow BWBW\underset{\_}{B}\cdots$。注意，那个绕回来的箭头是指向r$\mathbf{\text{r}}$的。
   

9. Kn$K_n$，n价复制机器（n-shift copier），如下图，操作是BWnBWn−1B⋯W1B––⇒BWnBWn−1B⋯W1BWnB––⋯$B{W}_{n}B{W}_{n-1}B\cdots W_1\underset{\_}{B}\Rightarrow B{W}_{n}B{W}_{n-1}B\cdots W_{1}B{W}_n\underset{\_}{B}\cdots$，即把Wn$W_n$复制到最右边的位置。
   

最后，下面这个不难证的引理告诉我们，示意图等价与图灵机。
引理5.2.1：对任意以A={a0,a1,...,ak}$A=\{a_0,a_1,...,a_k\}$为字符集的图灵机，存在一个示意图，它由r$\mathbf{\text{r}}$，l$\mathbf{\text{l}}$，a0,a1,...,ak$a_0,a_1,...,a_k$构成，并且它们对所有磁带的作用效果一样。