《计算模型导引》第五章习题
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.
解：
分情况处理：
(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 的最小零点。
解：
这里空白的地方太小，写不下。请听习题课讲解。