《计算模型导引》第五章习题

1

习题5.1

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

解：

主要思想是先后抹除$\overline x,\overline z$最后移到$\overline y$的头.

机器如下：

	0	1	解释
1	0R2	0R1	抹除$\overline x$并指向$\overline y$头
2	0R3	1R2	移动到$\overline z$头
3	0L4	0R3	抹除$\overline z$
4	0L4	1L5	越过$\overline y$的最后一个1
5	0R6	1L5	移到$\overline y$头

2

习题5.2

构造机器 $\boxed{\text{copy}_1}$ 使 $\boxed{\text{copy}_1}|0\underset{\uparrow}{1^x}0\cdots\twoheadrightarrow 01^x0\underset{\uparrow}{1^x}0\cdots$.

解：

主要思路是逐个减少第一个1，每次减少一个，在后面各增加一个1。最后，第一个1消失，其后增加了两个1。

设计机器 M 实现如下功能：

$M|1:0\cdots 0\underset{\uparrow}{1^{l+1}}01^k01^k0\cdots \twoheadrightarrow 1:0\cdots 0\underset{\uparrow}{1^l}01^{k+1}01^{k+1}0\cdots$

$M|1:0\cdots 0\underset{\uparrow}{1}01^k01^k0\cdots \twoheadrightarrow u:0\cdots 0\underset{\uparrow}{1^{k+1}}01^{k+1}0\cdots$

其中 $k\ge 0$，$u$ 为停机状态。

	0	1	解释
1		0R2	减少第一个1
2	0R3	1R12	发现是0,即第一个1空,准备停;否则循环
3	1R4	1R3	还需要增加第二个和第三个1,先越过第二个1,将末尾的0变为1
4		0R5	到达第三个1,将第一个1变为0
5	1R6	1R5	越过第三个1,将末尾的0变为1
6	1L7		由于第一个1变为0,这里需要再添加一个1
7	0L8	1L7	左移过第三个1
8	0R9	1L8	左移过第二个1
9			到第二个1头,停机
10
11
12	0R13	1R12	越过第一个1,移动到第二个1
13	1R14	1R13	越过第二个1,将末尾的0变为1
14		0R15	到达第三个1,将第一个1变为0
15	1R16	1R15	越过第三个1,将末尾的0变为1
16	1R17		由于第一个1变为0,这里需要再添加一个1
17	0L18	1L18	准备向左移动
18	0L19	1L18	左移过第三个1
19		1L20	准备左移
20	0L21	1L20	左移过第二个1
21	0R1	1L21	左移到第一个1,到状态1,继续循环

3

习题5.3

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

解：

设结果为 $z$。

主要思路是逐个减少 $\overline x$ ，每次减少一个，将 $\overline z$ 增加 $\overline y$。在计算 $z+y$ 时，用 0 的位置记录加法的进度。

	0	1	解释
1	0R10	0R2	减少一个$\overline x$
2	0R3	1R2	右移过$\overline x$
3	0L8	0R4	遇到1，将$\overline y$中该位置变为0;遇到0，表示加完$\overline y$
4	0R5	1R4	右移过$\overline y$
5	1L6	1R5	右移过$\overline z$,末尾添加1
6	0L7	1L6	左移过$\overline z$
7	1R3	1L7	左移到$\overline y$中的0位置，将其置为1
8	0L9	1L8	左移过$\overline y$
9	0R1	1L9	左移过$\overline x$
10	0R11	0R10	擦除$\overline y$，移动到$\overline z$，停机

4

习题5.4

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

解：

参考定理5.14，我们可将 $f$ 写为如下形式：

$$\begin{align} f(0) &= 1, \\\\ f(x+1) &= 2f(x). \end{align}$$

首先我们构造机器 $M_3$ ,作用是在纸带右面添加 $\overline{1}$

	0	1	解释
1	0R2	1R1	右移过当前值
2	1R3		添加1
3	1L4		添加1
4	0L5	1L4	左移过 $\overline{1}$
5	0R6	1L5	右移到 $\overline{1}$

再构造机器 $M_1$ 如表5.19

	0	1
1		0R2
2	0Rv	1R3
3	0R4	1R3

令 $M_2$ 为 $M_1 \Rightarrow \boxed{\text{double}} \Rightarrow \boxed{\text{compress}} \Rightarrow \boxed{\text{shiftl}}$，从而

若 $x=0$, 则 $M_2 | 1:0\underset{\uparrow}{\overline{x}}0\overline{y}0\cdots \twoheadrightarrow v:000\underset{\uparrow}{\overline{y}}0\cdots$

若 $x>0$, 则 $M_2 | 1:0\underset{\uparrow}{\overline{x}}0\overline{y}0\cdots \twoheadrightarrow w:00\underset{\uparrow}{\overline{x-1}}0\overline{g(y)}0\cdots$，其中 $w$ 为 $M_2$ 的输出时的状态，$g$ 为 double 函数。

令 $\boxed{\text{f}}= M_2[w:=1]$，$M_3\Rightarrow \boxed{\text{f}}$ 即为所求。

5

习题5.5

设机器 $M_1$ 定义如下表：

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

对于输入 $\bar{x}$ ，求输出.

注意

在定义5.2中，定义了机器如何停机。注意我们定义的图灵机纸带左端是固定的，若读头左移越过纸带左端，则机器无定义，停机。

解：

若 $x=0$:

$$ \begin{align} 1: & 0\underset{\uparrow}{1}0000\cdots & (1R2) \notag\\ 2: & 01\underset{\uparrow}{0}000\cdots & (0L3) \notag\\ 3: & 0\underset{\uparrow}{1}0000\cdots & (1L3) \notag\\ 3: & \underset{\uparrow}{0}10000\cdots & (0L3) \notag \end{align} $$ 若 $x>0$:

$$\begin{align} 1: & 0\underset{\uparrow}{1}1^x0000\cdots & (1R2) \notag\\\\ 2: & 01\underset{\uparrow}{1^x}0000\cdots & (0R1) \notag\\\\ 1: & 010\underset{\uparrow}{1^{x-1}}0000\cdots & (1R2)\notag\\\\ 2: & 0101\underset{\uparrow}{1^{x-2}}0000\cdots & (0R1) \notag\\\\ & \cdots & (1R2,0R1) \notag\\\\ 3: & \overbrace{0101\cdots 0\underset{\uparrow}{1}}^{\lfloor x/2\rfloor +1 个 01}0000\cdots & (1L3) \notag\\\\ & \cdots & (0L3,1L3) \notag\\\\ 3: & \overbrace{\underset{\uparrow}{0}101\cdots 01}^{\lfloor x/2\rfloor +1 个 01}0000\cdots & (0L3) \notag \end{align}$$

6

习题5.6

设机器 $M_2$ 定义如下表：

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

对于输入 $(2,1):01^n01^m01^k00\cdots$ , 其中 $n,m,k\in\mathbb{N}^+$ , 求输出.

解：

$$\begin{align} 1: & 0\underset{\uparrow}{1^n}01^m01^k0\cdots & (0R1) \notag\\\\ 1: & 00^n\underset{\uparrow}{0}1^m01^k0\cdots & (0R2)\notag\\\\ 2: & 00^n0\underset{\uparrow}{1^m}01^k0\cdots & (0R1)\notag\\\\ 1: & 00^n00\underset{\uparrow}{1^{m-1}}01^k0\cdots & (0R1) \notag\\\\ 1: & 00^n00^m\underset{\uparrow}{0}1^k0\cdots & (0R2) \notag\\\\ 2: & 00^n00^m0\underset{\uparrow}{1^k}0\cdots & (0R1) \notag\\\\ 1: & 00^n00^m00\underset{\uparrow}{1^{k-1}}0\cdots & (0R1) \notag\\\\ 1: & 00^n00^m00^k\underset{\uparrow}{0}0\cdots & (0R2) \notag\\\\ 2: & 00^n00^m00^k0\underset{\uparrow}{0}\cdots & (1R3) \notag\\\\ 3: & 0^{n+m+k+4}1\underset{\uparrow}{0}\cdots & (1R4) \notag\\\\ & \cdots & (1R5,1L6) \notag\\\\ 6: & 0^{n+m+k+4}11\underset{\uparrow}{1}10\cdots & (1L6) \notag\\\\ 7: & 0^{n+m+k+4}\underset{\uparrow}{1^4}0\cdots & \notag \end{align}$$

7

习题5.7

构造机器计算函数 $f(x)=\left\lfloor \sqrt{x} \right\rfloor$ .

解：

这里空白的地方太小，写不下。请听习题课讲解。