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

《计算理论导引_6_可计算理论的高级专题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、康熠华计算理论第6章可计算性理论的高级专题1主要内容6.1递归定理6.1.1自引用6.1.2递归定理的术语6.1.3应用6.2逻辑理论的可判定性6.2.1一个可判定的理论6.2.2一个不可判定的理论6.3图灵可归约性6.4信息的定义6.4.1极小长度的描述6.4.2定义的优化6.4.3不可压缩的串和随机性2逻辑理论的可判定性数理逻辑是数学的一个分支，它研究数学本身。数理逻辑关心如下问题：什么是定理？什么是证明？什么是真？算法能判定哪些命题是真的？所有真命题都是可证的吗？关心的焦点：能否确定一个数学命题是真是假，以及这种问题的可判定性。3逻辑理论的可判

2、定性命题1称，有无限多个素数存在，在大约2300年以前的欧几里德时代，就已知道这个命题是真的。命题2称为费马大定理，这个命题几年前由安德鲁·威尔士(AndrewWiles)证明为真。命题3称，有无限多个素数对存在，这被称为孪生素数猜想(twinprimeconjecture)。它到现在还未被解决。首先需要建立一个精确的语言来将这些问题形式化。我们的要求是能够考虑如下数学命题：4符号∧，∨，┐称为布尔运算；“(”和“)”是括号；符号和是量词；符号x用来代表变元；符号R1，…，Rk称为关系。逻辑理论的可判定性为了将之进一步精确化，现在描述这个语言的字

3、母表：5公式公式是字母表上的良构串。形如Ri(x1,x2,…,xj)的串是原子公式，值j是关系符号Ri的元数。一个良构公式中所有出现的相同关系符号必须有相同的元数。一个串∮如满足一下条件，则是一个公式：1)是一个原子公式；2)具有形式∮1∧∮2或∮1∨∮2或┐∮1。其中∮1和∮2是更小的公式。3)具有形式∮1∧∮2或∮1∨∮2或∮1。其中x[∮1]或x[∮1]，其中∮1是更小的公式。6公式辖域：紧跟在量词化变元后的一对括号中的部分。前束范式：所有量词都出现在公式的前面。自由变元：没有被量词的辖域所约束的变元。句子或命题：没有自由变元的公式。(1

4、)x(F(x,y)→G(x,z))(2)x(F(x)→G(y))→y(H(x)∧L(x,y,z))7例6.7在下列公式中，只有最后一个是句子：逻辑理论的可判定性8逻辑理论的可判定性论域：覆盖变元可能的取值。将关系符号指定为确定的关系。而关系是从论域上的k元组到{TRUE，FALSE}的函数。关系符号的元数必须和指派给它的关系和元数相同。论域连同关系到关系符号的指派一起称为模型。形式上，一个模型M是一个元组(U,P1,…,Pk)，其中U是论域，P1到Pk是指派给符号R1到Rk的关系。模型语言：在公式的集合中，只使用此模型指派的关系符号，且对每个关

5、系符号，使用正确的元数。如果∮是某个模型语言中的句子，则∮在这个模型中不为真就为假。如果∮在模型M中为真，则说M是∮的一个模型。9逻辑理论的可判定性例6.8设∮是句子xy[R1(x,y)∨R1(y,x)]，模型M1=(N,≤)是如下的模型：它的论域是自然数集，它将“小于或等于”关系分配给符号R1。显然∮在M1中为真，因为对于任意两个自然数a和b，a≤b和b≤a必有一个成立。但如果M1将“小于”关系（而不是“小于或等于”关系）指派给R1，则∮将不真，因为当x和y相等时，它不再成立。如果事先知道什么关系将指派给Ri，就可以用这个关系的惯用记号来代替R

6、i，且按习惯，可用中缀记法。对于M1，可以将∮写成xy[x≤y∨y≤x]10例6.9设M2是如下的模型：它的论域是是实数集R，且讲关系PLUS指派给R1，其中：只要当a+b=c时PLUS(a,b,c)=TURE。则M2是ψ=yx[R1(x,x,y)]的一个模型。但如果用N代替R作为M2的论域，则此句子为假。逻辑理论的可判定性如果M是一个模型，这个模型语言中所有真句子的集合称为M的理论系统，简称为理论，记为Th(M)。11一个可判定性的理论定理6.10Th(N,+)是可判定的。设3包含所有高度为3的0和1的列。3上的字符串给出三行0和1。把

7、每一行看作一个二进制数，令B={w∈3

8、w最下面的一行等于上面两行的和}则B是正则的。12Th(N,+)是可判定的考虑如下一个实例：构造有限自动机：{(x1,x2,x3)

9、x1+x2=x1+x3}然后构造NFA：{(x1,x2)

10、x3x1+x2=x1+x3}同样：{(x1)

11、x2x3x1+x2=x1+x3}…为真时，得到{()},为假时得到。13一个可判定性的理论定理6.10Th(N,+)是可判定的。思路：对于输入为(N,+)的语言中的句子∮检查其在模型中是否为真。∮=Q1x1Q2x2…Qlxl[ψ]对于0~l的每一个i，令公式∮i为∮i

12、=Qi+1xi+1Qi+2xi+2…Qlxl[ψ]这样，∮0=∮且∮l=ψ。对于从0到l的每个i，算法构造了