《计算理论》复习题总结

1《计算理论》复习题总结1、自动机、可计算性、复杂性内涵及关系；计算理论的三个传统的核心领域：自动机、可计算性和复杂性。通过“计算机的基本能力和局限性是什么？“这一问题将这三个领域联系在一起。可计算理论与复杂性理论是密切相关的，在复杂性理论中，目标是把问题分成容易计算的和难计算的；而在可计算理论中，是把问题分成可解的和不可解。自动机阐述了计算的数学模型的定义和性质，主要包含两种模型：有穷自动机模型；上下文无关文法模型。可计算性理论和复杂性理论需要对计算机给了一个准确的定义。自动机理论允许在介绍与计算机科学的其他非理论领域有关的概念时使用计算的形式化定义。2、有穷自动机、正则语言、正则表达式、非确定有穷自动机、非正则语言；有穷自动机：描述能力和资源极其有限的计算机模型。是一个5元组（Q，∑，δ，q0,F），其中1）Q是一个有穷集合，称为状态集。2）∑是一个有穷集合，称为字母表。3）δ：Q×∑→Q是转移函数。4）q0Q是起始状态。5）FQ是接受状态集。正则语言：如果一个语言能被有穷自动机识别。正则表达式：用正则运算符构造描述语言的表达式。称R是正则表达式，如果R是：1）a，a是字母表中的一个元素；2）；3）;4）（R1R2）；5）(R1R2)；6）(R1*)非确定有穷自动机：是一个5元组（Q，∑，δ，q0,F），其中1）Q是有穷状态集。2）∑是有穷字母表。3）δ：Q×∑→P（Q）是转移函数。4）q0Q是起始状态。5）FQ是接受状态集。3、上下文无关语言及上下文无关文法、歧义性、乔姆斯基范式、下推自动机、等价性、非上下文无关语言；上下文无关语言：用上下文无关文法生成的语言。上下文无关文法：是一个4元组（V，∑，R，S）且1）V是一个有穷集合，称为变元集2）∑是一个与V不相交的有穷集合，称为终结符集3）R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成，4）SV是起始变元歧义性：如果字符串W在上下文无关文法G中有两个或者两上以上不同的最左派生，则称G歧义地产生的字符串W。如果文法G歧义的产生某个字符串则称G是歧义的。乔姆斯基范式：一个上下文无关文法如果它的每一个规则具有如下形式A→BCA→a其中a为任意终结符，ABC为任意变元且BC不是起始变元，此外允许规则S→其中S是起始变元。下推自动机：是6元组Q，∑，，δ，q0,F），这里Q，∑，，F都是有穷集合，并且1）Q是状态集2）∑是字母表3）是栈字母表4）δ：Q×∑×→P（Q×）是转移函数学5）q0Q是起始状态。6）FQ是接受状态集。4、各种等价性；每一台非确定型有穷自动机等价于一台确定的有穷自动机；一个语言是正则的当且仅当可以用正则表达式描述；一个语言是上下文无关的则存在一台下推自动机识别它。5、计算科学；能性问题；Church-Turing论题；计算；可计算；计算科学：系统的研究信息描述和变换的算法，包括其理论、分析、设计、效率、实现和应用。用计算科学涵盖并称谓计算机科学和计算机工程。计算机科学所研究问题的核心是能行问题。能行问题：什么能被（有效的）自动化？什么不能被（有效）的自动化？Church－Turing论题：可计算性等价于Turing机可计算性。计算：Truing机所进行的工作就是计算。可计算：Turing机能够进行的工作就叫可计算。6、几个计算模型；各种计算模型的特点；图灵机的特点；计算模型：1、递归函数。Gödel，Church，等人提出并完善了递归函数理论。从数学演算的思想出发，考虑从简单的、直观上可计算的函数出发构复杂的可计算函数。2、Turing机（理论模型）：Turing研究的Turing机计算模型与现代计算机更接近，在Turing机的基础上引进了大量的自动机。3、Church－λ演算：用来描述计算过程，基本思想主要用于函数式程序语言的研制。4、Post系统（符号变换系统）：Post系统的基础上引进了大量的形式语言。Turing机的特点：存储无穷，时间无限制。Turing机可计算只是理论上可计算，并不是现实可计算。现实可计算：研究计算复杂性。但如果Turing机不可计算则现实更不可计算。7、原语言，指令系统，输入输出规定；原语言：变元、标号（语句标号）、指令：X＝X＋1；X＝X－1；ToAIFX≠0；ToA；Y＝X输入变元用x表示x，x1，x2，x3，……输出变元用y表示，函数只输出一个值。对程序做如下两点规定：1、当程序开始执行时自动认为一切变元的值为0（输入变元除外）2、当程序出现下列两种情形之一时，自动认为停机。a、转向无定义的标号b、执行程序的最后一条指令。8、n元程序对应的n元函数的定义；若程序P恰有n个输入变元X1，X2，……，Xn，而没有其它X变元，则称P为n元程序。n元程序P对应的函数Ψp（X1，X2，……，Xn）定义如下：Ψp（a1，a2，……，an）=9、部分可计算，全函数，可计算函数；答：函数f（X1，X2，……，Xn）被称为部分可计算的，若有一程序P使得Ψp（X1，X2，……，Xn）＝f（X1，X2，……，Xn），“＝”表示：或者两边都无定义，或者两边都有定义并且其值相同。函数f（X1，X2，……，Xn）被称为全函数，若它对一切X1，X2，……，Xn的值都有定义。函数f（X1，X2，……，Xn）被称为可计算函数，若它是部分可计算的且是全函数。10、复合、递归、取极小，正则；初始函数，原始递归函数答：复合：设有函数Y=f（Z1，Z2……，Zm）和函数Z1=g1（X1，……，Xn）……Zm＝gm（X1，……，Xn）则n元函数Y＝h（X1，……，Xn）＝f（g1（X1，……，Xn），……，gm（X1，……，Xn））被称为函数f和g1，g2，……，gm的复合函数。递归：设m（X1，X2，……，Xn）和φ（X1，X2，……，Xn，Xn+1，Xn+2）是全函数，定义h（X1，X2，……，Xn，o）＝m（X1，……，Xn）h（X1，X2，……，Xn，t＋1）＝φ（X1，……，Xn，h（X1，……，Xn，t），t）称h是递归算子作用于函数m和φ得到的n+1元递归函数，且是全函数。2取极小：设f（X1，X2，……，Xn，Z）为全函数，定义h（X1，……，Xn）＝min{Z|f（X1，……，Xn，Z）＝0}称h是取极小算子作用n+1元函数f得到的n元取极小值函数。正则函数：函数f（X1，……，Xn，Xn+1）被称为正则的，若对任何一组X1，X2，……，Xn都有Z使得：f（X1，……，Xn，Z）＝0故，对正则函数取极小算子的结果得到一全函数。初始函数：S（X）＝X＋1（后继函数）n（X）＝0（零函数）∪in(X1,…,Xn)=Xi（1≤i≤n）投影函数由初始函数S（X），n（X），∪in(X1,…,Xn)=Xi（1≤i≤n）出发，只用复合和递归算子得到的函数称为原始递归函数。由初始函数S（X），n（X），∪in(X1,…,Xn)=Xi（1≤i≤n）出发，用复合，递归和取极小算子得到的函数称为部分递归函数。由初始函数S（X），n（X），∪in(X1,…,Xn)=Xi（1≤i≤n）出发，用复合，递归和对正则函数取极小算子得到的函数称为递归函数。11、谓词P的特征函数，集合S的特征函数；答：设P（X,…,Xn）是n元谓词，定义函数为真时当～为真时当）＝（P1P0Xn,...,X1称δ为谓词P的特征函数。设S是集合，则定义函数:时）当（时）当（）＝（SSXn,...,X11Xn,...,X10Xn,...,X1称δ为集合S的特征函数。12、原始递归谓词、原始递归集合；可计算谓词、可计算集合；答：谓词P（集合S）是原始递归的，如其特征函数是原始递归的。谓词P（集合S）是可计算的，如其特征函数是可计算的。13、三个定理：若P，Q原始递归，则～P，P∧Q，P∨Q均原始递归；定理1：P（X1,…,Xn）原始递归的～P（X1,…Xn）原始递归的。证明：设δ和δ’分别为P和～P的特征函数只需证明：δ原始递归δ’原始递归由δ及δ’的定义知δ’（X1,…,Xn）＝α(δ（X1,…,Xn)）δ（X1,…,Xn）＝α(δ’（X1,…,Xn)）故得证。定理2：P，Q原始递归，则PQ也是原始递归的。证明：设δ1，δ2，δ3分别是P，Q，PQ的特征函数则有δ3(Z1，…，Zk)＝α(α(δ1(X1，…，Xn）+δ2(Y1,…,Ym)))故δ3是原始递归函数。故得证。定理3：P，Q原始递归，则PQ也是原始递归的。证明：设δ1，δ2，δ3分别是P，Q，PQ的特征函数则δ3（Z1，…，Zk）＝δ1(X1,…,Xn)·δ2(Y1,…,Ym）故得证。定理4：设P是原始递归谓词，g、h是原始递归函数，则如下定义的函数f是原始递归的为真当～），，（为真当），，（）＝，，（PXnX1hPXnX1gXnX1f证明：设δ是P的特征函数，f＝g·α（δ）＋h·δ故得证。定理5：P（Y，X1，……，Xn）是原始递归谓词，则Yt)(P（t，X1，……，Xn）是原始递归谓词。证明：令Q（Y，X1，……，Xn）＝Yt)(P（t，X1，……，Xn）要证明Q是原始递归谓词。令δ是P的特征函数，并令Yt0Xn,...,X1,tXnX1,...,,Y）（）＝（’故δ'是原始递归函数。下面证明δ'是Q的特征函数:如存在一个0≤t0≤Y使P（t0,X1,…,Xn）为真，则δ（t0,X1,…,Xn）＝0，故δ'（Y,X1,…,Xn）＝0即当Q（Y,X1,…,Xn）为真时δ'为0;如对所有0≤t≤Y有P（t，X1，……，Xn）为假，则对所有0≤t≤Y都有δ（t,X1,…,Xn）＝1故δ’（Y,X1,…,Xn）＝1即当Q为假时，δ’（Y,X1,…,Xn）＝1故δ’是Q的特征函数，Q是原始递归谓词。证毕。定理6：若P（t，X1，……，Xn）是原始递归的，则Yt)(P（t，X1，……，Xn）是原始递归的。证明：令δ和δ’分别是P和Yt)(P的特征函数)XnX1tXnX1YY0t）），，，（（（）＝，，，（’＝定理7：设S和R是原始递归集合，则R，S∩R，S∪R是原始递归集合。（R是R的余集）证明：令δ1，δ2分别是S和R的特征函数，δ3是R的特征函数则δ3＝（δ2）故R是原始递归集合。令δ4是S∩R的特征函数，则δ4＝（（δ1＋δ2））故S∩R是原始递归集合。令δ5是S∪R的特征函数，则（Φ代表空元素）δ5（X1，……，Xn）＝δ1（X1，……，Xn）·δ2（X1，……，Xn）·（δ1（Xi1，…，Xim1，Φ，…，Φ）___用Φ凑满n项＋δ2（Xj1，……，Xjm2，Φ，……，Φ））因对X1，……，Xn∈R∪S可能有如下三种情况：1）X1，……，Xn∈R2）X1，……，Xn∈S3）Xi1，……，Xim1∈RXj1，……，Xjm2∈S故得证。14、复合后仍然是原始递归谓词；定理8：设P（z1,z2,…,zn）是原始递归谓词，h1，……，hn是n个k元原始递归函数，（n≥1，k＞0）则P（h1（X1，……，Xk），……，hn（X1，……，Xk））也是原始递归的。证明：令δ’为复合谓词的特征函数，δ为P的特征函数，则有3δ’（X1，X2，……，Xk）＝δ（h1（X1，……，Xk），……，hn（X1，……，Xk））δ，h1，……，hn均为原始递归函数。故δ’亦是。证毕。15、f，g是原始递归函数，f＝g是原始递归谓词；定理9：f，g是原始递归函数，f＝g是原始递归谓词。证明：知X＝Y是原始递归谓词，由定理8知f＝g是原始递归谓词。16、受囿取极小，由谓词到函数的转换。给出了构造递归函数的又一种方式；受囿取极小值设P（t，X1，……，Xn）为谓词，定义函数：否则），，，（）＝，，，（0}XnX1tPYt|min{tXnX1tPminYt17、若P是原始递归谓词，则其受囿取极小函数是原始递归函数；定理10：若P（t，X1，……，Xn）是原始递归谓词，则）