计算理论导引6可计算理论的高级专题.ppt

计算理论
朴秀峰
******@
主要内容
61递归定理
611自引用
612递归定理的术语
613应用
62逻辑理论的可判定性
621一个可判定的理论
22一个不可判定的理论
63图灵可归约性
64信息的定义
641极小长度的描述

643不可压缩的串和随机性
递归定理
口递归定理是一个数学结论,在可计算性理论的高级研究中
起着重要的作用
口考察与生命科学有关的一个悖论:
1)生物都是机器
2)生物都能自再生
3)机器不能自再生。
口设有构造机器B的机器A:A肯定比B复杂,但一个机器
不会比它自己更复杂。因此没有机器能够制造它自己,故
自再生是不可能的。??
口制造能生产自己的机器是可能的。
递归的意义
口自己调用自己
从前有个庙,庙里有个老和尚,老和尚给小和尚讲故事,
讲的故事是:“从前有个庙,庙里有个老和尚,老和尚给
小和尚讲故事,讲的故事是…”
口自我繁殖
#include <>
man
i char sc="#include <stdio. h> mainolchar
ec=%c%s %c;printf(c, 34, C, 34); "
printf(c, 34, C, 34);
自引用
引理存在可计算函数q:E→,对任意串w,g)是
61图灵机P的描述,P打印出w,然后停机
口可以任取一个字符串w,然后从它构造一个图灵机,使得此图灵机将w
内装在一个表中,这样,当此图灵机开始运行后,它只要简单输出w即
可
下列TMQ计算q(w):
Q=“对于输入串w
1)构造下列图灵机P
Pw=“对于任意输入:
a)抹去输入。
b)在带上写下
c)停机。”
2)输出<P>。”
图灵机SELF
图灵机SELF忽略输入,且打印出它自己的描述
图灵机SELF有两个部分,分别叫做A和B,将A和B想象成两个分离的
过程,它们一起组成SELF。
我们希望SELF打印出<SELF>=<AB>
A部分首先运行,在根据完成情况将控制传给B。A的任务是打印出B的
描述。
使用机器PB来定义A,其中PB用函数q在<B>处的值q(<B>)描述,这
样,A部分是一个打印出<B>的图灵机。A的描述依赖于是否已经有了
B的描述,所以在构造出B之前,无法完成A的描述。
定义B,使之能打印A:B从A产生的输出来计算A
如果B能得到<B>,它就能用q来得到<A>。当A结束时,它被留在带上
所以B只要看着带子就能得到<B>。在计算q(<B>)=<A>之后,B将
之加到带的前面。
然后将A和B组合成一个机器并在带上写下它的描述。
图灵机SELF
SELF的示意图,一个打印它自己的描述的TM
A→B
(=P<B>)
SEF的控制器□「
A=PB2,且
B=“对于输入<M>,其中M是一个TM的一部分:
1)计算q(<M>)。
2)将其结果与<M>结合来组成一个完整的TM描述。
3)打印这个描述,然后停机。”
图灵机SELF
如果现在运行SELF,能观察到如下动作:
A→B
(=P<B>)
SEF的控制器□「「
1)首先A运行,它在带上打印<B>;
2)B开始运行,它查看带子,找到它的输入<B>;
3)B计算q(<B>)=<A>,然后将之与<B>合并,构成TM
SELF的描述<SELF>。
4)B打印这个描述,且停机
图灵机SELF
口容易用任何程序设计语言实现这个构造,即得到一个程序,
输出就是它自己。
口也可用自然语言实现:
打印这个句子
口考虑下面的变换
打印下面语句的两个副本,在第二个副本上加引号;
“打印下面语句的两个副本,在第二个副本上加引号;”
口本例中,B部分的构造是如下的句子
打印下面语句的两个副本,在第二个副本上加引号
口A部分与之相同,只是用引号将之括起来
口A提供了B的一个副本给B
递归定理
定理设T是计算函数t:∑*X*→∑*的一个图灵机
62则存在计算函数r:2*→2*的一个图灵机R,使得
对每一个w,有
r(w)=t(<R>,w)
只需要制造一个TMT,使之以自己的描述作为输入的一部分。
然后递归定理就产生一个新的机器R,它和T一样运行,只是R
的描述被自动地装在T中。
A十B→T
<BT>
R的控制器