《计算模型导引》第五章习题¶
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\) 写为如下形式：
首先我们构造机器 \(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\):
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}^+\) , 求输出.
解：
7¶
习题5.7
构造机器计算函数 \(f(x)=\left\lfloor \sqrt{x} \right\rfloor\) .
解：
这里空白的地方太小，写不下。请听习题课讲解。