《计算模型导引》第五章习题
8
习题5.8
设机器 \(\boxed{\text{f}_1}\) 计算函数 \(f_1\) ，机器 \(\boxed{\text{f}_2}\) 计算函数 \(f_2\) ，这里 \(f_1,f_2\) 为一元数论全函数。构造机器 \(\boxed{\text{f}}\) 计算函数 \(f(x)=f_1(x)+f_2(x)\) .
解：
先 copy 一个 \(\overline{x}\) ，利用 \(f_1\) 计算结果，使用 compress 和 shiftl 得到 \(0\underset{\uparrow}{\overline{x}}0\overline{f_1(x)}\)。
再 copy 一个 \(\overline{x}\) ，利用 \(f_2\) 计算结果。删掉第一个 \(\overline{x}\) 并将两个结果拼起来。
\[
\begin{align}
& 0\underset{\uparrow}{\overline{x}}0\cdots \notag\\\\
\boxed{\text{copy}_1}\twoheadrightarrow & 0\overline{x}0\underset{\uparrow}{\overline{x}}0\cdots \notag\\\\
\boxed{\text{f}_1}\twoheadrightarrow & 0\overline{x}0^m\underset{\uparrow}{\overline{f_1(x)}}0\cdots \notag\\\\
\boxed{\text{compress}}\twoheadrightarrow & 0\overline{x}0\underset{\uparrow}{\overline{f_1(x)}}0\cdots \notag\\\\
\boxed{\text{shiftl}}\twoheadrightarrow & 0\underset{\uparrow}{\overline{x}}0\overline{f_1(x)}0\cdots \notag\\\\
\boxed{\text{copy}_2}\twoheadrightarrow & 0\overline{x}0\underset{\uparrow}{\overline{f_1(x)}}0\overline{x}0\cdots \notag\\\\
\boxed{\text{shiftr}}\twoheadrightarrow & 0\overline{x}0\overline{f_1(x)}0\underset{\uparrow}{\overline{x}}0\cdots \notag\\\\
\boxed{\text{f}_2}\twoheadrightarrow & 0\overline{x}0\overline{f_1(x)}0^n\underset{\uparrow}{\overline{f_2(x)}}0\cdots \notag\\\\
\boxed{\text{compress}}\twoheadrightarrow & 0\overline{x}0\overline{f_1(x)}0\underset{\uparrow}{\overline{f_2(x)}}0\cdots \notag\\\\
\boxed{\text{shiftl}}^2\twoheadrightarrow & 0\underset{\uparrow}{\overline{x}}0\overline{f_1(x)}0\overline{f_2(x)}0\cdots \notag\\\\
\boxed{\text{erase}}\twoheadrightarrow & 0^l\underset{\uparrow}{\overline{f_1(x)}}0\overline{f_2(x)}0\cdots \notag\\\\
\boxed{\text{add}}\twoheadrightarrow & 0^l\underset{\uparrow}{\overline{f(x)}}0\cdots \notag
\end{align}
\]
故
\[
\begin{align}
\boxed{\text{f}} &= \boxed{\text{copy}_1} \Rightarrow \boxed{\text{f}_1} \Rightarrow \boxed{\text{compress}} \Rightarrow \boxed{\text{shiftl}} \\
& \Rightarrow \boxed{\text{copy}_2} \Rightarrow \boxed{\text{shiftr}} \Rightarrow \boxed{\text{f}_2} \Rightarrow \boxed{\text{compress}} \Rightarrow \boxed{\text{shiftl}}^2 \\
& \Rightarrow \boxed{\text{erase}} \Rightarrow \boxed{\text{add}}
\end{align}
\]
9
习题5.9
设 \(f(x)=h(g_1(x), g_2(x), g_3(x))\)， 试由机器 \(\boxed{\text{g}_1}\), \(\boxed{\text{g}_2}\), \(\boxed{\text{g}_3}\) 和 \(\boxed{\text{h}}\) 构造机器 \(\boxed{\text{f}}\) .
解：
先 copy 一个 \(\overline{x}\) ，利用 \(g_1\) 计算结果，使用 compress 和 shiftl 得到 \(0\underset{\uparrow}{\overline{x}}0\overline{g_1(x)}\)。
copy 一个 \(\overline{x}\) ，利用 \(g_2\) 计算结果，使用 compress 和 shiftl 得到 \(0\underset{\uparrow}{\overline{x}}0\overline{g_1(x)}0\overline{g_2(x)}\)。
copy 一个 \(\overline{x}\) ，利用 \(g_3\) 计算结果，使用 compress 和 shiftl 得到 \(0\underset{\uparrow}{\overline{x}}0\overline{g_1(x)}0\overline{g_2(x)}0\overline{g_3(x)}\)。
擦除最左边的 \(\overline{x}\) ，利用 \(h\) 计算结果。
故
\[
\begin{align}
\boxed{\text{f}} &= \boxed{\text{copy}_1} \Rightarrow \boxed{\text{g}_1} \Rightarrow \boxed{\text{compress}} \Rightarrow \boxed{\text{shiftl}} \\
& \Rightarrow \boxed{\text{copy}_2} \Rightarrow \boxed{\text{shiftr}} \Rightarrow \boxed{\text{g}_2} \Rightarrow \boxed{\text{compress}} \Rightarrow \boxed{\text{shiftl}}^2 \\
& \Rightarrow \boxed{\text{copy}_3} \Rightarrow \boxed{\text{shiftr}}^2 \Rightarrow \boxed{\text{g}_3} \Rightarrow \boxed{\text{compress}} \Rightarrow \boxed{\text{shiftl}}^3 \\
& \Rightarrow \boxed{\text{erase}} \Rightarrow \boxed{\text{h}}
\end{align}
\]
10
习题5.10
设 \(f:\mathbb{N}\rightarrow\mathbb{N}\) 定义如下：
$$
\begin{align}
f(0) &= 0,\\
f(x+1) &= g(f(x)).
\end{align}
$$
证明：若 \(g\) 为Turing-可计算，则 \(f\) 为Turing-可计算。
证：
参考定理5.14的证明。我们只需要在5.14的证明的基础上，做一个预处理，添加一个输入 \(\overline{0}\) 即可。
构造机器 \(M_3\) 实现添加输入 \(\overline{0}\)
|
0 |
1 |
| 1 |
0R2 |
1R1 |
| 2 |
1L3 |
|
| 3 |
0L4 |
|
| 4 |
0R5 |
1L4 |
按照定理5.14的证明构造机器 \(\boxed{f'}\)
注意
在作业或考试中，这里需补充 \(\boxed{f'}\) 的完整构造过程。
\[
\begin{align}
f'(0, 0) &= 0,\\\\
f'(x+1, 0) &= g(f'(x, 0)).
\end{align}
\]
最后结果为 \(M_3 \Rightarrow \boxed{f'}\)
11
习题5.11
构造机器计算函数 \(f(x,y)=x \dot- y\).
解：
分情况处理：
\[
0 \dot- y = 0
\]
\[
x \dot- 0 = x
\]
\[
(x+1) \dot- (y+1) = x \dot- y
\]
|
0 |
1 |
解释 |
| 1 |
|
0R2 |
减少一个 \(\overline x\) |
| 2 |
0R3 |
1R4 |
若为0，则 \(x=0\)，进入状态3；否则 \(x>0\)，进入状态4 |
| 3 |
1Ou |
0R3 |
擦除 \(\overline y\)，添加 \(\overline 0\) 作为结果，停机 |
| 4 |
0R5 |
1R4 |
右移过 \(\overline x\) |
| 5 |
0R5 |
0R6 |
右移过若干0，到达 \(\overline y\) ，减小一个 \(\overline y\) |
| 6 |
0L7 |
1L9 |
若为0，则 \(y=0\)，进入状态7；否则 \(y>0\)，进入状态9 |
| 7 |
0L7 |
1L8 |
左移过若干0，到 \(\overline x\) 右侧末端 |
| 8 |
1Ov |
1L8 |
左移过 \(\overline x\)，增加一个 \(\overline x\)，作为结果停机 |
| 9 |
0L9 |
1L10 |
左移过若干0，到 \(\overline x\) 右侧末端 |
| 10 |
0R1 |
1L10 |
左移到 \(\overline x\)，进入状态1，继续循环 |
12
习题5.12
证明：\(Even=\{2x:x\in\mathbb{N}\}\) 是Turing-可计算的。
解：
构造机器 \(E\) 满足：
\(E|1:0\underset{\uparrow}{1^{2x+1}}0\cdots \twoheadrightarrow u:0\cdots 0\underset{\uparrow}{1}0\cdots\)
\(E|1:0\underset{\uparrow}{1^{2x}}0\cdots \twoheadrightarrow u:0\cdots 0\underset{\uparrow}{1}10\cdots\)
|
0 |
1 |
| 1 |
1L3 |
0R2 |
| 2 |
1O3 |
0R1 |
| 3 |
1O3 |
|
13
习题5.13
证明：\(S=\{a_1,a_2,\cdots,a_k\}\) 是Turing-可计算的。
解：
\(S\) 的特征函数为 \(\chi_{S}\) 为
\[
f(x) = N(x \ddot- a_1) + N(x \ddot- a_2) + \cdots + N(x \ddot- a_k)
\]
显然 \(f\in\mathcal{GRF}\) ，由定理5.18，\(f\) 是Turing-可计算的。
14
习题5.14
设 \(f:\mathbb{N}\rightarrow\mathbb{N}\) 是Turing-可计算的，构造机器 \(M\) 使其输出 \(f\) 的最小零点。
解：
这里空白的地方太小，写不下。请听习题课讲解。