《计算模型导引》（2019）课后习题答案（五）：Turing机

个人答案，仅供参考。

查看全部

页面含有超多数学公式，打开后需要等待很长时间才能彻底完成渲染和排版，尤其是移动设备。

$$\def \calc {\twoheadrightarrow} \def \join { {\Large{\text{⤇}}} } \newcommand \tm [1] {\boxed{\mathrm{ \vphantom{\vert}#1 }}} \newcommand \btape [1] {0 1^{ #1 }} \newcommand \arrowbtape [1] {0{\underset\uparrow 1}^{ #1 }} \def \endbtape {0 \cdots} \newcommand \tape [1] {\overline{(#1)}\endbtape} \def \stdadd {\tm {add}} \def \stddouble {\tm {double}} \def \stdcompress {\tm {compress}} \def \stderase {\tm {erase}} \newcommand \stdcopy [1] [2] {\tm {copy_{ #1 }}} \newcommand \stdshiftl [1] [{}] {\tm {shiftl}^{ #1 }} \newcommand \stdshiftr [1] [{}] {\tm {shiftr}^{ #1 }}$$

5.1 构造机器计算函数$f(x,y,z)=y$。

解：

	0	1	注释
1	0R2	0R1	抹去$x$
2	0R3	1R2	跳过$y$
3	0L4	0R3	抹去$z$
4	0L4	1L5	回到$y$尾部
5	0R6	1L5	回到$y$头部，停机

5.2 构造机器$\stdcopy[1]$使$\stdcopy[1]\mid\arrowbtape x\calc\btape x\arrowbtape x$。

解：显然需要使用循环，关键点在于实现对循环,状态的记录，可以采用如下实现。

• 先把当前的位置变成0作为标记，右移：$\btape n\underset \uparrow 1 1^{x-n-1}\btape n\endbtape \calc \btape n\arrowbtape{x-n-1}\btape n\endbtape$
• 然后向右跳过全部1、一个0、再全部1：$\btape n\btape{x-n-1}\btape n\underset \uparrow 0\endbtape$
• 在此位置设置一个1，左移：$\btape n\btape{x-n-1}\btape {n-1}\underset \uparrow 11\endbtape$
• 接着向左跳过全部1、一个0、再全部1：$\btape n\underset \uparrow 0 1^{x-n-1}\btape {n+1}\endbtape$
• 将最初设置的0恢复为1并右移一格：$\btape n1\underset \uparrow 1 1^{x-n-2}\btape n 1\endbtape \equiv \btape {n+1}\underset \uparrow 1 1^{x-n-2}\btape {n+1}\endbtape$

可以看到，循环体最后回复到了初始的情形，唯一的区别是指针右移了一格并且在复制区域末尾新增了一个1，对$n=0,1,\cdots,x-1$重复便完成了上述复制操作

	0	1	注释
1	0R6	0R2	置一个0，或者停机
2	0R3	1R2	右移跳过（旧）1，再跳过一个0
3	1L4	1R3	右移跳过（新）1，再设置一个1并左移
4	0L5	1L4	左移跳过（新）1，再跳过一个0
5	1R1	1L5	左移跳过全部（旧）1，将0恢复为1并回到循环开始

5.3 构造机器计算函数$f(x,y)=x\times y$。

解：很自然地想到，乘法应该通过循环加法实现。这里可以将$x$作为循环计数量，每次累加一个$y$实现乘法。

• 构造机器用于初始化，即在最右侧添加一个0，即$M_1\mid\tape{a,b}\calc\tape{a,b,0}$，可采用如下形式

  $M_1=\stdshiftr[2]\join\tm Z\join\stdshiftl[2]$

  注：原始定义中的$\stdshiftr$是用来在输入间移动，但如果遵循表5.17的实现，其可以移动到最后一个输入的右端空位处；原始定义中的$\tm Z$接受单个输入变量，但如果遵循表5.2的实现，其也可以不需要输入，在一个空位就地产生输出0。

• 构造单次累加机器$M_2\mid\tape {a,b}\calc\tape{a,a+b}$，可有

  $M_2=\stdcopy\join\stdadd\join\stdcompress\join\stdshiftl$

• 构造减量计数并条件判断机器$M_3$如下

  	0	1	注释
  1		0R2	计数器减1
  2	0Ru	1R3	如果计数器早已为0，结束进入状态u
  3	0R4	1R3	未结束就进入状态4

• 构造条件计数单次累加机器$M_4=M_3\join M_2\join\stdshiftl$，它具有如下性质

  • 当$a=0$，$M_4\mid 1:\tape{a,b,c}\calc u:00\tape{b,c}$
  • 当$a>0$，$M_4|1:\tape{a,b,c}\calc v:0\tape{a-1,b,b+c}$

• 构造循环累加机器$M_5=M_4[v:=1][u:=maxS(M_4)+1]$

• 最后，令$\tm M=M_1\join M_5\join\stderase$，这便是计算乘法的机器

5.4 构造机器计算函数$f(x)=2^x$。

解：类似题5.3，由循环累乘来实现指数计算。

• 构造初始化机器，在最右侧添加一个数1

  $M_1=\stdshiftr\join\tm Z\join\tm S\join\stdshiftl$

• 构造条件计数机器$M_2$，其实现与题5.3中的$M_3$一致

• 构造条件倍增机器，$M_3=M_2\join\stddouble\join\stdshiftl$，在计数器非0时停机状态$v$，为0时停机状态$u$

• 构造循环倍增机器，$M_4=M_3[v:=1][u:=maxS(M_3)+1]$

• 加上初始化机器完成构造$\tm M=M_1\join M_4$

5.5 设机器$M_1$定义如表5.24。

表5.24

	0	1
1	0L3	1R2
2	0L3	0R1
3	0L3	1L3

对于输入$\overline x$，求输出。

解：

• 先观察输入1且状态为1或2的情形：1R2和0R1，它们构成了一个自循环，交替地将带上的数据设置为$1,0,1,0,\cdots$，奇数位置为1，偶数位置为0。

• 这个自循环停止的条件是遇到了输入为0，此时保持输出不变为0，进入了状态3

• 而一旦达到状态3，其内部又构成了无法停止的自循环，保持带上数据不变并不断左移，直至越界

所以，这个机器会将输入$\overline x$的第偶数个1设置为0，而读头位置向纸带最左侧越界

5.6 设机器$M_2$定义如表5.25。

表5.25

	0	1
1	0R2	0R1
2	1R3	0R1
3	1R4
4	1R5
5	1L6
6	0R7	1L6

对于输入$(2,1):\btape n\btape m \btape k0\endbtape$，其中$n,m,k\in\mathbb N^+$,求输出。

解：易知，$M_2\mid 1:\tape{\underset \uparrow x,y}\calc 7:00^x\tape{\underset \uparrow {\min(y,3)}}$

因此，分为两种情况：

1. 当$m\lt3$，输出为$7:00^n\arrowbtape{m+k+2}\endbtape$
2. 当$m\ge3$，输出为$7:00^n\arrowbtape m\btape k\endbtape$

5.7 构造机器计算函数$f(x)=\lfloor\sqrt x\rfloor$。

解：$f(x)=\lfloor\sqrt x\rfloor \iff (f(x))^2\le x\lt(f(x)+1)^2 \iff f(x)=\mu y.N((S(y))^2\text{∸}x)$

• 题5.3中已构造了乘法器，平方机器可以通过$\tm {sqrt}=\stdcopy [1]\join\stdshiftl\join\tm {multi}$构造

• 减法器参考后文题5.11构造

• 取反函数$N$可以通过如下方式构造

  	0	1	注释
  1		1R2	跳过第一个1
  2	1L5	0R3	为0则输出1停机，否则进入状态3
  3	0L4	0R3	大于0则变成0
  4	0L4	1O5	回到左端

• 正则算子可以按照书中定理5.16的方式构造

综上，可以完成平方根的机器构造。

5.8 设机器$\tm {f_1}$计算函数$f_1$，机器$\tm {f_2}$计算函数$f_2$，这里$f_1,f_2$为一元数论全函数。构造机器$\tm f$计算函数$f(x)=f_1(x)+f_2(x)$。

解：构造如下

$$\begin{split} &\stdcopy [1]\join\tm{f_1}\join\stdcompress\join\stdshiftl \\ \join & \stdcopy\join\tm{f_2}\join\stdcompress\join\stdshiftl[2] \\ \join & \stdadd \join \stdshiftl \join \stderase \end{split}$$

5.9 设$f(x)=h(g_1(x),g_2(x),g_3(x))$，试由机器$\tm{g_1},\tm{g_2},\tm{g_3}$和$\tm h$构造机器$\tm f$。

解：构造如下

$$\begin{split} &\stdcopy [1]\join\tm{g_1}\join\stdcompress\join\stdshiftl \\ \join & \stdcopy\join\tm{g_2}\join\stdcompress\join\stdshiftl[2] \\ \join & \stdcopy[3]\join\tm{g_3}\join\stdcompress\join\stdshiftl[3] \\ \join & \tm h \join \stdshiftl \join \stderase \end{split}$$

5.10 设$f:\mathbb N\rightarrow\mathbb N$定义如下：

$$f(0)=0\\ f(x+1)=g(f(x))$$

证明：若$g$为Turing-可计算，则$f$为Turing-可计算。

证明：这个问题是定理5.14当$y=0$的特殊情况，仿造其构造的机器为$\tm {M_g}$

因此只需要构造加参机器$\tm {M_0}$如下：

	0	1
1	0R2	1R1
2	1L3
3	0L4
4	0L5	1L4

如此，$\tm f = \tm {M_0} \join \tm{M_g}$

5.11 构造机器计算函数$f(x,y)=x\text{∸}y$。

解：思路很简单，每次对$x,y$减1，直到有一个为0，如果需要，还有再把剩余的$y$擦除。

	0	1	注释
1		1R2	跳过首bit的1
2	0R3	1R7	$x>0$跳到状态7，否则继续
3	0R3	0R4	向右跳过全部0
4	0L5	0R4	向右将全部1置为0
5	0L5	1L6	向左跳过全部0
6	0R12	1L6	向左跳过全部1，最后回到$x$首位停机（状态12）
7	0R8	1R7	向右跳过全部1
8	0R8	0R9	向右跳过全部0，并对$y$减1
9	0L5	1L10	遇到了0表示$y$刚才是0，进入状态5进而停机，否则继续
10	0L10	0L11	向左跳过全部0，然后对$x$减1（此处原本必有$x>0$）
11	0R1	1L11	向左跳过全部1，回到状态1重复循环

5.12 证明：$Even=\{2x:x\in\mathbb N\}$是Turing-可计算的。

思路：数一数输入有几个1就行，奇数个1（对应输入数为偶数）就输出0，否则输出1。因此要在机器内维持一个交替状态，每次遇到1就交变一下计数状态。

证明：构造如下机器计算其特征函数即完成证明之。

	0	1	注释
1	1L2	0R2	已有偶数个1。遇到1，偶变奇；否则输出1bit的1进入状态2
2	1O3	0R1	已有奇数个1。遇到1，奇变偶；否则立即再输出1bit的1并停机

5.13 证明：$S=\{a_1,a_2,\cdots,a_k\}$是Turing-可计算的。

证明：只需要证明相等比较和多个数相乘是Turing-可计算的。

• 对任意常数$n$，存在机器$\tm{eq_n}$计算函数$eq_n(x)=\begin{cases}0,&x=n,\\1,&x\neq n.\end{cases}$

  通过零函数和后继函数机器，容易构造常函数机器$\tm{C_n}$计算$C(x)=n$，

  又$a=b\iff (a\text{∸}b)+(b\text{∸}a)=0$，且减法机器$\tm {minus}$在题5.11中已构造，故

  $$\begin{split} \tm{eq_n}=&\stdcopy[1]\join\stdshiftr\join\tm{C_n}\join\stdcompress\join\stdshiftl\join \\ &\stdcopy[2]^2\join\tm{minus}\join\stdcompress\join\stdshiftl\join\\ &\stdcopy[2]\join\stdshiftl[3]\join\stdcopy[4]\join\stdshiftl\join\tm{minus}\join\stdcompress\join\stdshiftl\join\\ &\stdadd\join\stdcompress\join\stdshiftl[2]\join\stderase^2 \end{split}$$

• 存在机器$\tm{multi_k}$计算$multi_k(c_1,c_2,\cdots,c_k)=\prod\limits_{i=1}^kc_i$，其中$k\ge2$

  利用题5.3中构造的二数乘法机器$\tm{multi_2}$，其构造可以如下

  $$\begin{split} \tm {multi_k}=&\stdshiftr[k-2]\join\\ &(\; \tm{multi_2}\join\stdcompress\join\stdshiftl \;)^{k-2}\join\\ &\tm{multi_2} \end{split}$$

综上所述：

• 当$k=1$，机器$\tm{eq_{a_1}}$计算量集合$S$的特征函数

• 当$k\ge2$，可利用如下机器计算其特征函数

  $$\begin{split} &\stdcopy[1]\join\stdshiftr[0]\join\tm{eq_{a_1}}\join\stdcompress\join\stdshiftl[1]\join\\ &\stdcopy[2]\join\stdshiftr[1]\join\tm{eq_{a_2}}\join\stdcompress\join\stdshiftl[2]\join\\ &\cdots\\ &\stdcopy[k]\join\stdshiftr[k-1]\join\tm{eq_{a_k}}\join\stdcompress\join\stdshiftl[k]\join\\ &\tm{multi_k} \end{split}$$

5.14 设$f:\mathbb N\rightarrow\mathbb N$是Turing-可计算的，构造机器$M$使其输出$f$的最小零点。

解：记机器$\tm f$计算了函数$f$，且我们使用带位置$1:\arrowbtape 1\endbtape$作为输入。

同时按照题5.7可以构造机器$\tm{N^2}=\tm N^2$计算函数$N^2$

另外，构造机器$\tm {zp}$对是否达到零点进行条件停机（if语句），

	0	1	注释
1		1R2	必有1 bit的1，跳过之
2	0L3	1L5	非零点则直接转到状态5，否则继续
3	0L4	0L3	是零点，抹去这个数据
4	0Rv	1L4	是零点，移到左边一个数据，并以状态v停机

因此，可以构造$M$为

$repeat (\;\stdcopy[1]\join\tm f\join\tm{N^2}\join\stdcompress\join\tm{zp}\join\stdshiftl\join\stdadd\;)$

5.15 证明定理5.21中函数$g$为一般递归函数。

证明：需要使用题5.17中的结论。

• 如果$m\not\in S$，函数值$g(m)=0$

• 否则，可以解构出编码$m$对应的机器$M$的每一行内容$\begin{array}{|c|c|c|}\hline j&xyz&uvw\\\hline\end{array}$，

  而$M_1$计算常函数$C_{\sharp M}(x)=\sharp M=m$，其可以通过$\tm Z\join\tm S^m$构造，其每行内容显然可以通过$m$由一般递归函数计算。

  $\hat M=M_1\join M$，由于$M$置于$M_1$之后，其每行的内容需要修改，即增加对应的状态号，这个映射也是一般递归的。

  最终，这个分支的$g(m)=\sharp \hat M$是一般递归的。

综上，分支判断和每个分支的结果都是一般递归的，整个函数当然也就是一般递归函数。

证明引理5.25中的函数$e(m,l)$为一般递归函数。

证明：使用题5.17中的结论，由$m$，可以通过一般递归函数计算每一行的内容$\sharp j,\sharp x,\sharp y,\sharp z,\sharp u,\sharp v,\sharp w$

同时，由$l$也可以通过一般递归函数计算纸带编码长度$t$以及纸带位置$(j,k):a_1,a_2,\cdots, a_t$。

由以上信息，通过循环、比较、分支函数，可以计算$\sharp d(a_j,k),\sharp p(a_j,k),\sharp s(a_j,k)$

因此，$e(m,l) = \langle \sharp d(a_j,k),\sharp p(a_j,k),\sharp s(a_j,k) \rangle \in\mathcal {GRF}$。

5.17 令$S=\{\sharp M:M\text{为Turing-机}\}$，证明$S$为Turing-可计算。

证明：证明其特征函数$\gamma_S\in\mathcal{GRF}$即可。

简化表达起见，约定对于因变量$y$，同名符号也可以表示其关于对应自变量$x_1,x_2,\cdots$的函数$y(x_1,x_2,\cdots)$。

• 先应当确定机器的行数，$k=\max a\le\sharp M.P(a-1)\mid\sharp M$

• 然后是每一行的编码，$r_i=ep(i,\sharp M)$

• 再后是行内解码，对于机器的一行$\begin{array}{|c|c|c|}\hline j&xyz&uvw\\\hline\end{array}$，有

  $\sharp j=ep(0,r_i),\sharp x=ep(1,r_i),\cdots,\sharp w=ep(6,x_i)$

• 接下来是合法性检查，我们需要进行如下检验

  • 如果$\sharp x=2$即$x=L$，则应该有$\sharp y=\sharp z=2$即$xyz=LLL$；

    否则，应该有$\sharp x\in\{0,1\}\wedge\sharp y\in\{2,3,4\}$

  • 如果$\sharp u=4$即$x=R$，则应该有$\sharp v=\sharp w=4$即$xyz=RRR$；

    否则，应该有$\sharp u\in\{0,1\}\wedge\sharp v\in\{2,3,4\}$

  • $\forall i_1,i_2\le k,i_1\neq i_2\Longrightarrow \sharp j(r_{i_1})\neq\sharp j(r_{i_2})$，即每一行的状态号都是不同的。

  循环、比较、逻辑或/且都是可以通过一般递归函数实现。

综上，$\gamma_S\in\mathcal{GRF}$。

5.18 由CT证明函数$g(n)$可计算，这里

$$g(n)=\text{在自然对数之底}e\text{的十进制展开式中第}n\text{个数字}$$

证明：使用拉格朗日余项的泰勒展开公式，

$$e=\sum_{i=0}^m\frac{1}{i!}+\frac {e^\theta} {(m+1)!}, \quad 0\lt \theta \lt 1$$

展开到$m=9+n$并在两边同乘$10^n$

$$\begin{split} &10^n \cdot e\\ =&10^n\sum_{i=0}^{9+n}\frac{1}{i!}+\frac{10^ne^\theta}{(10+n)!}\\ =&\frac{10^n \sum_{i=1}^{10+n}{[i(i+1)\cdots(10+n)]}}{(10+n)!} + \frac{10^ne^\theta}{(10+n)!} \end{split}$$

又$\frac{10^ne^\theta}{(10+n)!}\le\frac{10^1e^\theta}{(10+1)!}\lt0.1$，令$f(n)=\frac{10^n \sum_{i=1}^{10+n}{[i(i+1)\cdots(10+n)]}}{(10+n)!}$

因此，在没有进位的情形下，$\lfloor f(n)\rfloor=\lfloor10^n\cdot e\rfloor$，但是应该考虑一般情形，应该对其进行修正，防止余项导致的进位而引起的整数部分变化。

修正方法很简单：取足够大的$n'\ge n$，并保证$\lfloor10f(n')\rfloor$的个位数不是9。这样做，保证了$f(n)$小数点后一位不是9，避免了0.1以内的误差也能导致进位。

即取$n'=\mu z\ge n.\lfloor10f(z)\rfloor \,mod\, 10 \neq 9$，

由于$e$无限不循环，因此上述$n'$一定有解，即$n'$相对于$n$的函数属于$\mathcal {GRF}$。

于是，修正后的$f'(n)=\frac{f(n')}{10^{n'-n}}$可以在一般情形下保证$\lfloor f'(n)\rfloor=\lfloor10^n\cdot e\rfloor$

综上，$g(n)=\lfloor f'(n)\rfloor \,mod\, 10\in \mathcal{GRF}$。

更好的解法是下面这样的，而且可以证明$f\in\mathcal{EF}$这个更小的集合，第一章题1.25也有类似如下的更佳解法。

证明：使用拉格朗日余项的泰勒展开公式，

$$e=\sum_{i=0}^m\frac{1}{i!}+R_m=\sum_{i=0}^m\frac{1}{i!}+\frac {e^\theta} {(m+1)!}, \quad 0\lt \theta \lt 1 \\ \text{其中当}m \ge2,R_m \lt1$$

令$f(n)=\lfloor en!\rfloor$，有

$$f(n)=\begin{cases} 2,&n\lt 2,\\ \sum\limits_{i=0}^n\frac{n!}{i!}=\sum\limits_{i=0}^n\lfloor\frac{n!}{i!}\rfloor,&n\ge2. \end{cases}\\ \therefore f\in\mathcal{EF}$$

从而$h(n)=\lfloor en\rfloor=\lfloor \frac{f(n)}{(n-1)!}\rfloor\in\mathcal{EF}$

$$f(n)=\begin{cases} 2,&n=0,\\ h(10^n)∸10h(10^{n∸1}),&n\ge1. \end{cases}\\ \therefore f\in\mathcal{EF}$$

$f\in\mathcal{EF}\subset\mathcal{GRF}$，其是Turing可计算的。

5.19

1. 什么是停机问题？
2. 什么是可判定问题（decision problem）？
3. 停机问题可判定吗？

答：

1. 先定义停机，机器$M$对于输入$A$停机是指从$A$开始由$M$决定的带位置的完全序列是有穷的。

   同时记集合$\hat K=\{\sharp M:M\text{对于一切输入皆停机}\}$。

   停机问题对任意机器$M$判断命题$\sharp M\in\hat K$是否为真。

2. 可判定问题指一个询问真/假的问题是否可被回答。

   等价表述为，对于集合$S$，如果其特征函数$\gamma_S$是Turing-可计算的，则称该集合是可判定的。

3. 停机问题不可判定，即不存在机器能够计算$\gamma_\hat K$

5.20

1. 什么是通用Turing机(universal Turing machine)？
2. 通用Turing机起什么作用。

答：

1. 通用Turing机是指这样的机器$U$，对任意机器$M$和任何$\overline{(n_1,\cdots,n_l)}\in\mathbb N^k$，它有

   $M|\overline{(n_1,\cdots,n_l)}\calc y\iff U|\overline{(\sharp M,n_1,\cdots,n_l)}\calc y$

2. 通用Turing机表明，只需要一个Turing机，就可以用它模拟任何Turing机进行运算。在现实中，这意味着我们只需要一台Turing机，对它进行编程（类似$\sharp M$的构造），便可以完成各种通用任务，而不再需要对每个任务场景使用一台专用机器。