第六章：可计算性理论的高级专题
Contents
6 Advanced Topics in Computability Theory
关于其他章节的内容，请点这：《计算理论导引》学习笔记
6.1 The Recursion Theorem
自引用
病毒？
思考一个问题：一个程序如何自我复制？
日常中我们对病毒可以自我复制这一点司空见惯，但如果仔细思考一下，一般会产生这样的疑问：（没有的可以直接右上角了）
假设A能生产B，那A总要比B多一点东西吧？
例如一个输出”Hello World”的C++程序：
|
1 2 3 4 5 6 |
#include <iostream> int main() { std::cout << "Hello World"; return 0; } |
最起码要比”Hello World”这个字符串多了输出语句吧
如果以此为出发点，正常人就会感觉“一个程序输出自己的全部源代码”是不可能的
所以下面的内容真的非常天才，ORZ，看了两遍才看得懂
lemma 6.0
首先要来个引理作铺垫：
There is a computable function \( q: \Sigma^* \longrightarrow \Sigma^*\), where if w is any string, q(w) is the description of a Turing machine \( P_w\) that prints out w and then halts.
简单地说
\( P_w\)是一台只会输出w的图灵机
q是一个把w映射为\( \langle P_w \rangle\)的函数
然后lemma 6.0说这个函数总是存在的
证明：
The following TM Q computes q(w).
Q = “On input string w:
1. Construct the following Turing machine \( P_w\).
\( \quad P_w\) = “On any input:
- Erase input.
-
Write w on the tape.
-
Halt.”
2. Output \( \langle P_w \rangle\).”
<SELF>
令SELF是一个会输出<SELF>的图灵机，这就是我们要构造的。
总体思路：令SELF由两个子程序组成，先是A执行，然后轮到B执行
所以A的任务就是输出B，B的任务就是输出A。。。才怪，这样做输出的是BA
假设我们要的就是BA，那怎么做呢？
先令\( \langle A \rangle = q(\langle B \rangle)\)，这样A就会输出B了
然后呢？令\( \langle B \rangle = q(\langle A \rangle)\)？
这样做就循环定义了，是错误的，为什么？
（\( \langle A \rangle = q(\langle B \rangle)\)的前提是已经定义好了一个不依赖于A的B）
不能直接把A给B，那怎么办呢？B决定计算出A；
注意到，A会在磁带上输出<B>，所以轮到B执行的时候，可以根据磁带上的<B>，计算出<A>
\( q(\langle B \rangle) = \langle A \rangle\)
具体而言：
\( A = P_{\langle B \rangle}\), and
B = “On input <M>, where M is a portion of a TM:
1. Compute q(<M>).
2. Combine the result with <M> to make a complete TM.
3. Print the descriptin of this TM and halt.”
If we now run SELF, we observe the following behavior.
- First A runs. It prints <B> on the tape.
-
B starts. It looks at the tape and finds its input, <B>.
-
B calculates \( q(\langle B \rangle) = \langle A \rangle\) and combines that with <B> into a TM description, <SELF>.
-
B prints this description and halts.
自然语言中的例子
|
1 2 |
把下一行输出两遍，其中只有第二遍带引号 “把下一行输出两遍，其中只有第二遍带引号” |
第二行是PART A，定义了一个字符串（B的副本）给B用
第一行是PART ，是一个执行语句：
先把A定义的字符串（B的副本）输出一遍（即输出B）
然后根据A定义的字符串（B的副本）计算出A（即加个引号），再输出A
C语言中的例子
|
1 |
p="p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);} |
其中，
p="p=%c%s%c;main(){printf(p,34,p,34);}"; 是PART A
main(){printf(p,34,p,34);} 是PART B
这里根据C的特点做了些修改，比如A定义的字符串里不仅仅只有<B>
不过本tao质lun还是一样的
递归定理
SELF确实很强大，能输出自身
但换句话说，它拿到自身的描述之后，就只能输出去，这样看，SELF又好像很弱
其实SELF拿到自身的描述之后，既然可以输出，为什么不做一些更有意义的事呢？
于是就有了递归定理：
Recursion theorem
Let T be a Turing machine that computes a function \( t: \Sigma^* \times \Sigma^* \longrightarrow \Sigma^*\).
There is a Turing machine R that computes a function \( r: \Sigma^* \longrightarrow \Sigma^*\),
where for every w, \( r(w) = t(\langle R \rangle,w)\)
其实说的就是刚刚那些中文
证明
增加一个子程序T，B拿到自身的描述<R>后，就把<R>与w（输入）一起交给T
具体而言：
A is a Turing machine \( P_{\langle BT \rangle}\)
(To preserve the input w, we redesign q so that \( P_{\langle BT \rangle}\) writes its output following any string preexisting on the tape.
B examines its tape, convert the <BT> to <A>.
Then, B combines A,B and T into a single machine and obtains its description <ABT> = <R>
Finally, it encodes that description together with w, places the resulting string <R,w> on the tape, and pass control to T.
术语
根据这个定理，以后用高级语言描述图灵机的时候，就可以这么说：
Obtain, via recursion theorem, its own description
无敌
应用
（又回到最初的起点。。。黑板上的图灵机，你舍得判定吗？。。。谁与谁等它又识别它。。。）
\( A_{TM}\) is undecidable
再来审视这个问题，递归定理，你值得拥有！
证明：
Assume that Turing machine H decides \( A_{TM}\), for the purpose of obtaining a contradiction.
We construct the following machine B.
B = “On input w:
1. Obtain, via recursion theorem, own description <B>.
2. Run H on input <B,w>
3. Do the opposite of what H says.”
DNOE!
其实本质还是一样的，表现形式从“理发师悖论”变成了“我在说谎”
书上还有两个例子，略。。。
The topic covered in each section is mainly independent of the others, except for an application of the recursion theorem at the end of the section on logical theories.
Part Three of this book doesn’t depend on any material from this chapter.
于是，后面暂略🙂