ITOC chapter6 可计算理论高级专题

6 ADVANCED TOPICS IN COMPUTABILITY THEORY 可计算理论的高级专题

THE RECURSION THEOREM 递归定理

递归悖论

构造机器,它构造自己的复制。(制造能生产自己的机器)

直观感觉是不行的:

现实中汽车生产线肯定比它构造的汽车复杂,设计生产线要比设计汽车更困难,因为生产线除了含有加工机器人的设计之外,还含有汽车的设计。

以此推到机器,机器B能构造机器A,B肯定比A复杂,但机器不能比自己更复杂,所以没有机器能够制造自己。

这就是递归悖论。实际上制造能生产自己的机器是可能的。

自引用

制造一个打印出自身描述的图灵机SELF

引理6.1:存在可计算函数 q:Σ∗⟶Σ∗, 对任意串w, q(w)是图灵机Pw的描述,Pw打印出w,然后停机。

简单地说
Pw是一台只会输出w的图灵机
q是一个把w映射为⟨Pw⟩的函数,q是存在的。

所以制造一个以自身描述为输入,打印出自身描述的图灵机就可以了,这很简单。

The following TM Q computes q(w).
Q = “On input string w:
1. Construct the following Turing machine Pw.
Pw = “On any input:

  1. Erase input.
  2. Write w on the tape.
  3. Halt.”

2. Output ⟨Pw⟩.”

有了引理6.1我们来构造SELF:

思路:令SELF由两个子程序组成,先是A执行,然后轮到B执行。

我们可以让A输出B,然后B输出A,这样不行,第一循环定义了,第二就算可以输出的也是<BA>而非<AB>.

这样不能把A给B,我们又要B输出A,我们可以让B计算出<A>.

注意到,A会在磁带上输出<B>,所以轮到B执行的时候,可以根据磁带上的<B>,计算出<A>

SELF:
A=P⟨B⟩, and
B = “对于输入<M>,其中M是一个TM的一部分:
1.计算 q(<M>).
2.将其结果与 <M> 合并来组成一个完整的TM描述.
3.打印这个描述,然后停机。”

运行SELF:

  1. A运行,他在纸带上打印<B>
  2. B运行,它查看纸带,找到它的输入<B>
  3. B计算q(⟨B⟩)=⟨A⟩ 然后与<B>合并,构成了TM <SELF>
  4. B打印这个描述,然后停机

自然语言:

把下一行引号内的部分输出两遍,其中只有第二遍带上引号
“把下一行引号内的部分输出两遍,其中只有第二遍带上引号”

第二行是PART A,定义了一个字符串(B的副本)给B用
第一行是PART B ,是一个执行语句

这段话就能输出自身,666

C:

#include <bits/stdc++.h>
char* p = "#include <bits/stdc++.h>%cchar* p=%c%s%c;%cint main(){printf(p,10,34,p,34,10,10);}%c";
int main(){printf(p,10,34,p,34,10,10);}

Python:

p='p=%r\nprint p %% p'  
print p % p

 

SELF构造成功,递归定理就来了:

令T是计算函数t:Σ∗×Σ∗⟶Σ∗的一个图灵机.
则存在计算函数r:Σ∗⟶Σ∗的一个图灵机R,使得对每个w,有: r(w)=t(⟨R⟩,w)。

感觉它借助R证明了这是有解的,但是具体怎么做是不知道的。

应用

有了递归定理,解决一些问题就很舒服了。

ATM不可判定:假设图灵机H判定ATM。

构造B = “对于输入 w:
1. 由递归定理得到它自己的一个描述 <B>.
2. 在输入<B,w>上运行H
3. 输出与H相反的结果。”

B不接受w,就会接受w。所以H不存在。

从理发师悖论变成了问“我这句是假话”这句话是不是真话hh

定义:MINTM{<M>|M是一个极小TM}(极小TM意味在所有等价TM中描述的长度最小)

定理:MINTM不是图灵可识别的。

反证法老套路,假设TM E枚举MINTM:

构造C = “对于输入w:
1. 由递归定理得到它自己的一个描述 <C>.
2. 运行枚举器E,直到一个比C的描述更长的机器D出现。
3. 在输入w上模拟D”

MINTM是无限的,所以E的序列里一定含有一个D比C的描述更长,然后C就模拟D,且与之等价,所以D不可能是极小的,但是D又在E产生的序列里出现,这样就产生了矛盾。

递归定理的不动点形式:考虑图灵机描述的可计算的转换函数:对任意一个这样的转换,都存在一个图灵机,使得他的行为不随这个转换改变。

定理:设t:Σ∗⟶Σ∗是一个可计算函数,则存在一个图灵机F,使得t(<F>)描述一个与F等价的图灵机。F就是“不动点”。

证明:

构造F = “对于输入w:
1. 由递归定理得到它自己的一个描述 <F>.
2. 计算t(<F>)得到一个TM G的描述。
3. 在输入w上模拟G”

显然F与G等价,因为F模拟G。

发表评论

电子邮件地址不会被公开。 必填项已用*标注