《计算理论》复习题总结.doc

计算理论复习题总结1、 自动机、可计算性、复杂性内涵及关系；计算理论的三个传统的核心领域：自动机、可计算性和复杂性。通过“计算机的基本能力和局限性是什么？“这一问题将这三个领域联系在一起。可计算理论与复杂性理论是密切相关的，在复杂性理论中，目标是把问题分成容易计算的和难计算的；而在可计算理论中，是把问题分成可解的和不可解。自动机阐述了计算的数学模型的定义和性质，主要包含两种模型：有穷自动机模型；上下文无关文法模型。可计算性理论和复杂性理论需要对计算机给了一个准确的定义。自动机理论允许在介绍与计算机科学的其他非理论领域有关的概念时使用计算的形式化定义。2、 有穷自动机、正则语言、正则表达式、非确定有穷自动机、非正则语言；有穷自动机：描述能力和资源极其有限的计算机模型。是一个5元组（Q，q0,F），其中1）Q是一个有穷集合，称为状态集。2）是一个有穷集合，称为字母表。3）：QQ是转移函数。4）q0Q是起始状态。5）FQ是接受状态集。正则语言：如果一个语言能被有穷自动机识别。正则表达式：用正则运算符构造描述语言的表达式。称R是正则表达式，如果R是：1）a，a是字母表中的一个元素；2）；3）;4）（R1R2）；5）(R1R2)；6）(R1*)非确定有穷自动机：是一个5元组（Q，q0,F），其中1）Q是有穷状态集。2）是有穷字母表。3）：QP（Q）是转移函数。4）q0Q是起始状态。5）FQ是接受状态集。3、 上下文无关语言及上下文无关文法、歧义性、乔姆斯基范式、下推自动机、等价性、非上下文无关语言；上下文无关语言：用上下文无关文法生成的语言。上下文无关文法：是一个4元组（V，R，S）且1）V是一个有穷集合，称为变元集2）是一个与V不相交的有穷集合，称为终结符集3）R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成，4）SV是起始变元歧义性：如果字符串W在上下文无关文法G中有两个或者两上以上不同的最左派生，则称G歧义地产生的字符串W。如果文法G歧义的产生某个字符串则称G是歧义的。乔姆斯基范式：一个上下文无关文法如果它的每一个规则具有如下形式ABC Aa其中a为任意终结符，ABC为任意变元且BC不是起始变元，此外允许规则S其中S是起始变元。下推自动机：是6元组Q，q0,F），这里Q，F都是有穷集合，并且1）Q是状态集 2）是字母表 3）是栈字母表 4）： QP（Q）是转移函数学 5）q0Q是起始状态。6）FQ是接受状态集。4、 各种等价性；每一台非确定型有穷自动机等价于一台确定的有穷自动机；一个语言是正则的当且仅当可以用正则表达式描述；一个语言是上下文无关的则存在一台下推自动机识别它。5、 计算科学；能性问题；Church-Turing论题；计算；可计算；计算科学：系统的研究信息描述和变换的算法，包括其理论、分析、设计、效率、实现和应用。用计算科学涵盖并称谓计算机科学和计算机工程。计算机科学所研究问题的核心是能行问题。能行问题：什么能被（有效的）自动化？什么不能被（有效）的自动化？ChurchTuring论题：可计算性等价于Turing机可计算性。计算：Truing机所进行的工作就是计算。可计算：Turing机能够进行的工作就叫可计算。6、 几个计算模型；各种计算模型的特点；图灵机的特点；计算模型：1、递归函数。Gdel，Church，等人提出并完善了递归函数理论。从数学演算的思想出发，考虑从简单的、直观上可计算的函数出发构复杂的可计算函数。2、Turing机（理论模型）：Turing研究的Turing机计算模型与现代计算机更接近，在Turing机的基础上引进了大量的自动机。 3、Church演算：用来描述计算过程，基本思想主要用于函数式程序语言的研制。4、Post系统（符号变换系统）：Post系统的基础上引进了大量的形式语言。Turing机的特点：存储无穷，时间无限制。Turing机可计算只是理论上可计算，并不是现实可计算。现实可计算：研究计算复杂性。但如果Turing机不可计算 则现实更不可计算。7、 原语言，指令系统，输入输出规定；原语言：变元、标号（语句标号）、指令：XX1；XX1；To A IF X0；To A；YX输入变元用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）Zmgm（X1，Xn）则n元函数Yh（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，t1）（X1，Xn，h（X1，Xn，t），t）称h是递归算子作用于函数m和得到的n+1元递归函数，且是全函数。取极小：设f（X1，X2，Xn，Z）为全函数，定义h（X1，Xn）minZ |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）X1（后继函数）n（X）0（零函数） in(X1, Xn)= Xi （1in）投影函数由初始函数S（X），n（X），in(X1, Xn)= Xi（1in）出发，只用复合和递归算子得到的函数称为原始递归函数。由初始函数S（X），n（X），in(X1, Xn)= Xi（1in）出发，用复合，递归和取极小算子得到的函数称为部分递归函数。由初始函数S（X），n（X），in(X1, Xn)= Xi（1in）出发，用复合，递归和对正则函数取极小算子得到的函数称为递归函数。11、 谓词P的特征函数，集合S的特征函数；答：设P（X,Xn）是n元谓词，定义函数称为谓词P的特征函数。设S是集合，则定义函数:称为集合S的特征函数。12、 原始递归谓词、原始递归集合；可计算谓词、可计算集合；答：谓词P（集合S）是原始递归的，如其特征函数是原始递归的。谓词P（集合S）是可计算的，如其特征函数是可计算的。13、 三个定理：若P，Q原始递归，则P，PQ，PQ均原始递归；定理1：P（X1,Xn）原始递归的P（X1,Xn）原始递归的。证明：设和分别为P和P的特征函数只需证明： 原始递归 原始递归由及的定义知 （X1,Xn）(（X1,Xn)）（X1,Xn）(（X1,Xn)）故得证。定理2：P，Q原始递归，则PQ也是原始递归的。证明：设1，2，3分别是P，Q，PQ的特征函数则有3(Z1，Zk)(1(X1，Xn）+2(Y1,Ym)故3是原始递归函数。故得证。定理3：P，Q原始递归，则PQ也是原始递归的。证明：设1，2，3分别是P，Q，PQ的特征函数则3（Z1，Zk）1(X1,Xn)2(Y1,Ym）故得证。定理4：设P是原始递归谓词，g、h是原始递归函数，则如下定义的函数f是原始递归的证明：设是P的特征函数，fg（）h故得证。定理5：P（Y，X1，Xn）是原始递归谓词，则P（t，X1，Xn）是原始递归谓词。证明：令Q（Y，X1，Xn）P（t，X1，Xn）要证明Q是原始递归谓词。令是P的特征函数，并令故是原始递归函数。下面证明是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）是原始递归的，则P（t，X1，Xn）是原始递归的。证明：令和分别是P和P的特征函数定理7：设S和R是原始递归集合，则，SR，SR是原始递归集合。（是R的余集）证明：令1，2分别是S和R的特征函数，3是的特征函数 则3（2） 故是原始递归集合。令4是SR 的特征函数，则4（12）故SR是原始递归集合。令5是SR的特征函数，则 （代表空元素）5（X1，Xn）1（X1，Xn）2（X1，Xn）（1（X i1，Xim1，）_用凑满n项2（Xj1，Xjm2，）因对X1，XnRS 可能有如下三种情况：1）X1，XnR 2）X1，XnS 3）Xi1，Xim1R Xj1，Xjm2S故得证。14、 复合后仍然是原始递归谓词；定理8：设P（z1,z2,zn）是原始递归谓词，h1，hn是n个k元原始递归函数，（n1，k0）则P（h1（X1，Xk），hn（X1，Xk）也是原始递归的。证明：令为复合谓词的特征函数，为P的特征函数，则有 （X1，X2，Xk）（h1（X1，Xk），hn（X1，Xk），h1，hn均为原始递归函数。故亦是。 证毕。15、 f，g是原始递归函数，fg是原始递归谓词；定理9：f，g是原始递归函数，fg是原始递归谓词。证明：知XY是原始递归谓词，由定理8知fg是原始递归谓词。16、 受囿取极小，由谓词到函数的转换。给出了构造递归函数的又一种方式；受囿取极小值设P（t，X1，Xn）为谓词，定义函数：17、 若P是原始递归谓词，则其受囿取极小函数是原始递归函数；定理10：若P（t，X1，Xn）是原始递归谓词，则是原始递归函数。证明：用表示X1，Xn，设：即t0是第一个使P（t，）取真值的t值。设是P（t，）的特征函数。考虑函数： , 不难验证： 亦不难验证：而t0是使P（t，）为真时最小的t值，故有因P(t,)是原始递归（P是原始递归）。令是其特征函数，则有：18、 第i个素数、Gdel数、配对函数；Pi是P（i）的简写（P不是前驱函数）Pi的值是第i个素数的值。（约定 P00是第0个素数；P12是第1个素数；P23是第2个素数；P35是第3个素数）证明：必须证明在PitPi！1中有素数即Pi+1 Pi！1若Pi！1是素数，则自然有Pi+1Pi！1，证毕。现假设Pi！1不是素数，则它一定有素数因子：1）此因子不会是0，因0不是任何数的因子2）P1，P2，Pi也不可能是因子因Pi！11234Pi1故用P1，P2，Pi去除均应余1。所以，Pi！1的素数因子大于Pi，小于等于Pi！1，证毕。哥德尔数【a1,an】表示即【a1,an】任取正整数X都有其对应的一组哥德尔数 求Cantor对角线上元素的序号(x+y)+y1/2（XY）（XY1）Y19、 递归函数是可计算的；部分递归函数是部分可计算的。定理11每个递归函数是可计算的定理12每个部分递归函数是部分可计算的。证明上述二定理需从以下三个方面证明：A每个初始函数是可计算的。B复合，递归和正则函数的取极小运算保持可计算性。C可计算函数取极小算子，结果为一部分可计算函数。具体证明由以下6个引理组成：引理1初始函数S（X），n（X），是可计算的。引理2复合保持（部分）可计算性。引理3可计算函数经取极小算子后，得一部分可计算函数。引理4正则函数取极小算子，保持可计算性。引理5可计算函数用递归算子作用后，仍保持可计算性。引理6多元函数用递归算子作用后仍保持可计算性。20、 Post_ Turing机：数据、符号、指令、带上数的表示、输入输出；PT（部分）可计算；PostTuring程序1）数据存于带上，带有一个指针，两端无穷长，永远有空白位，无穷多个格，每个格可写一个字符。2）符号B 1 B代表空白符。3）指令6条。 RIGHT 指针右移一格 LEFT 指针左移一格 WRITE 1 将指针所指的带上的当前格改写为1 WRITE B 将指针所指的带上的当前格改写为B TO A IF 1 若当前格为1，则转到以A为标号的指令 TO A IF B 若当前格为B, 则转到以A为标号的指令4）带上数若N 为一个数，则在带上把它表示成N +1个1。用表示X的带上表示。输入：若用一个 PT程序计算出数f(X1,Xn)，则输入Xi的值按下述方法写在带上11 11 B 11 11BB 11 11 X1+1 X2+1 Xn+1 输出：计算的结果是程序结果的带上1的个数减1如：11BB11BBB111 结果是6定义1.称函数f是PT部分可计算的，有一个PT程序计算它。定义2.称函数f为PT可计算的，如果它是PT部分可计算的并且是全函数。21、 广义Post_ Turing机：字母表、指令；其它同Post_ Turing机；字母表：S0,S1,S2,Sk.（每个表示一个符号）约定 S0=B, S1=1指令：RIGHT LEFT WRITE Si (i=0,1,2,k) TO A IF Si (i=0,1,2,k)22、 每个（部分）可计算函数是PT（部分）可计算函数；PT（部分）可计算函数是广义PT（部分）可计算函数；广义PT（部分）可计算函数是（部分）可计算函数；定理1.每个（部分）可计算函数是PT（部分）可计算函数证明：任何一个（部分）可计算函数的程序P均可模拟为等价的PT程序。（如前面的原语言程序）一般程序的操作对象是变元，而PT程序操作对象是带定理2PT（部分）可计算的函数是广义PT（部分）可计算函数定理3 广义PT（部分）可计算函数是（部分）可计算的。23、 Turing机：带、读写头、控制器、程序；四元组和五元组；停机规定；Turing机是什么？Turing 机：三部分：一条带，一个读写头一个控制器（控制器内存有程序）一个字母表 =S0, S1, S2, , Sk 一个状态集 Q=q1, q2, , qn1带和读写头（指针）： 带是无穷长的，两端伸向无穷，带上划成格子，每个格子中可写一个符号。符号均属于字母表：=S0, S1, S2, , Sk读写头对准一个格子，它可以读写带上的符号，可以擦去或改写，读写头可以向左移动一格，向右移动一格，或保持不动；左，右移或不动分别记为l, r, h。2控制器：控制器在每个时刻处于一定的状态，称为机器的内部状态。状态集 Q=q1,q2,qn，状态集中有一个特殊状态称初始状态。3程序：控制器内存有一个程序，程序指令用四元组或五元组表示。四元组有三类指令：(每个四元组完成一个基本动作并转入下一个状态)1. qi SjSk ql：当前状态是qi，读写头对准Sj，把Sk写在当前格内，并转入状态ql；2. qi SjLql ：当前状态是qi，若当前格为Sj，左移指针一格，并转入状态ql；3. qi SjRql ：当前状态是qi，若当前格为Sj，左移指针一格，并转入状态ql；五元组指令形式：qi aj av q其中aj, a，qi, qQ, vl, r, h此指令含义：当机器内部状态为qi时，若读写头读进的符号是aj，则做如下动作：1读写头把带上当前格的符号改写为a；2根据v的值不读写头左、右移或不动；3机器内部状态改为q。Turing机是四(五)元组的有穷集，其中没有两个四(五)元组的头两个字符qi sj(或qiaj)是相同的。Turing机停机规定：（有其它规定，例如规定终止状态）如果当前状态qi和当前字符sj (aj)的对偶qisj (qiaj)不出现于Turing机的任何四(五)元组中，则Turing机停机。24、 Turing（部分）可计算；PT可计算Turing可计算；四元组Turing机可计算五元组；Turing机可计算；五元组Turing机可计算PT可计算；函数f（x1,xn）是Turing部分可计算的。若有一个Turing机计算它（而不是程序）。函数f（x1,xn）是Turing 可计算的。若它是Turing部分可计算的，且是全函数。 定理4 每个PT（部分）可计算函数都被具有相同字母表的Turing机所计算。证明：因Turing机的初始数据和结果数据在带上的表示形式与Post_Turing机完全相同。故只要把PT程序的每条语句模拟为PT机的四元组形式即可。定理5 四元组Turing机和五元组Turing机可彼此模拟。证明：四元组到五元组转换： qi sj sk ql qi sj sk h ql qi sj R(L) ql qi sj sj r(l) ql 五元组到四元组转换： qi sj sk h ql qi sj sk ql qi sj sk l(r)ql qi sj sk ql ql sk L(R) ql定理6 五元组Turing机可被具有相同字母表的P-T程序模拟。证明：设Turing机的状态为： q1,q2,qn. 使每个状态对应一个PT程序的标号，记为 A1, A2, A3, , An. 再令每个对偶qi sj对应标号Bij。则 在标号Ai处有；Ai TO Bi0 IF S0 TO Bik IF Sk而在标号Bij处有qi sj为头的五元组的动作。qi sj sk R(L) ql Bij WRITE Sk RIGHT(LEFT) TO Alqi sj sk h qlBij WRITE Sk TO Al若无qi sj为头的五元组则Bij TO E模拟后的PT程序结构如下：A1 TO B10 IF S0 TO B1k IF SkAn TO Bn0 IF S0 TO Bnk IF SkB10 Bnk 由上述证明有下列结论25、 PT程序的数字编码（利用配对函数、Gdel数）；Post-Turing程序的数字编号PT程序是二符号字母表=1,B上的程序。数字编码的构造方法：设PT程序P的指令序列为：R1, R2, , Rn令指令Ri的编码为ri，则程序P的编码定义为（r1,rn）的哥德尔数：r1,r2,rn=2r13r25r3Pnrn。而指令亦可带标号，若带标号则一指令可用对偶如（Ai, i）表示，其中Ai为标号，i为指令（无标号语句）。则取Ai的编码为i，若i前无标号，视为（A0, i）故（Ai，i）的编码= _配对函数无标号指令i的编码如下：RIGHT 1LEFT 2WRITE 1 3WRITE B 4TO Ai IF 1 2i+4TO Ai IF B 2i+3如给出下面程序：A2 RIGHTTO A1 IF BTO A2 IF 1A1 WRITE 1RIGHTWRITE 1标号代码200100无标号指令代码158313指令代码=7=20=44=13=2=9于是整个程序P的编码为：7,20,44,13,2,9=2732054471311213926、 任给的PT程序则一定对应一个唯一的Gdel数，反之那？定义 由PT程序编码得到的数称为PT程序的哥德尔数问题：任意给定PT程序，则一定对应一个唯一的哥德尔数。反之，任意给定一个整数是否都有相应的PT程序与之对应呢？答案是否定的设n为一个PT程序的哥德尔数，则n的素数分解中的指数是配对函数的值，其中i0，j0 又因在程序中不能有相同标号，故在上述指数中不能有两个相同的非零左分量。即对任意两个上述分解中的指数，都有若i10且i20则i1i2且j1，j2不为0。如果任取一个数其素因子分解都满足上述条件，则它必是某PT程序的哥德尔数。27、 通用程序的思想；枚举定理，计步谓词，计步定理，迭代定理；通用程序思想：若z是一个代表某PT程序的哥德尔数。通用程序的功能就是将整数z所代表的PT程序的功能，用原语言编写的程序实现，且对同一个输入x，其计算结果与z所代表的PT程序一致。即把一个数转换成一个程序执行。定义：若z是某PT程序P的哥德尔数，并且程序P计算部分函数g（X1，Xn）则定义n+1元函数：= g（X1，Xn）若Z不是任何P-T程序的哥德尔数或g对给定的时，对Z，X1，Xn无定义枚举定理:对每个n，部分函数是部分可计算函数。计步谓词定义如下：PROG（Z）并且编码为Z的PT程序对于输入在M步内停机。（这里的一步是PT程序的一条指令的一次执行）计步定理：对任意n，谓词是可计算的。证明：（函数值：若为真 Y=0，为假 Y=1（对于其特征函数）检查Z是否某PT程序的哥德尔数，若不是Y=1模拟初始带建立一个步计数器j，每执行一条指令j+1。若jM。Y=1。若M步内停止，Y自动取0，Y=0。 程序如下： （主要利用通用程序）TO G IF PROG（Z）X=J=0V=1I=1A J=J+1 TO G IF JM TO E IF (I=0)(ILT(Z)TO R IF S V=V+1TO DG Y=1 得证。迭代定理：对一切n，有原始递归函数使得对于一切=（迭代定理给出了n取不同值时之间的关系。）28、 半可计算性（主要对谓词和集合），可判定可计算，半可判定半可计算；集合：常用递归（可计算）和递归可枚举（半可计算性）；谓词：常用到可判定（可计算）和半可判定（半可计算性）集合S是递归的：如果存在一个算法A。使得对任何的。在有限步内回答是否，即 ：（表示（）集合S是递归可枚举的：如果存在一个算法A，使得对任何的，若则在有限步内回答“是”，若，则算法不能给出回答，不终止，即：谓词P（）是可判定的：如果存在一个算法A使得对任给的，能够在有限步内回答P（）是“真”，还是“假”，即有：谓词P（）是半可判定的：如果有一个算法A使得对任给的，若P（）为真，则在有限步内回答“是”，否则算法不终止（即不能给出答案），即：29、 f(X1,Xn) 和f(X1,Xn)：表示函数对于有定义；：表示函数对于无定义；可视为谓词=（）|表示函数f的定义域。定义1. 谓词称为半可计算的。如果存在一部分可计算函数使得下式成立：这实际上是用部分可计算函数的定义域来定义了谓词的半可计算性。就是说，一个谓词是半可计算性的，当且仅当它的真值域等于某部分可计算函数的定义域。等价定义：谓词是半可判定的。当且仅当存在一个程序，使得：对于停机。定义2. 集合S是半可计算的，如果存在一部分可计算函数，使得：等价定义：S是半可计算的当且仅当它的特征谓词是半可计算的。30、 半可计算的封闭性，对运算符和及和受囿全称量词封闭，对和封闭；不封闭于全称量词和非运算；定理1.整数集H是半可计算的当且仅当存在某部分可计算函数使得H=|定理2. 若P（）和Q（）是半可计算的，则P Q（）亦为半可计算谓词定理3. 若P（）和Q（）是半可计算谓词，则P Q（）亦是半可计算谓词。定理4.如果和是半可计算集。则和亦是半可计算集。定理5.谓词是半可计算的当且仅当存在一个可计算谓词使得：（Y）证明： （）设（Y） （是可计算的）（必要性）要证明 是半可计算的。即要找一个程序使得 程序对于停机。程序如下： A U=TO E IF U=0Y=Y+1TO A 若有一个Y使为真，则可找到Y则停机。否则程序永远不停机。故是半可计算的。（）设是半可计算谓词。证明存在一个可计算谓词，使得（Y）因为是半可计算的，必有部分可计算函数使得由枚举定理有，使得：因此有，表示程序（Gdel数），对于在M步内停机，即有（M）。因是可计算的。令其为=， 故定理成立。定理6. 设是半可计算谓词，则（V）亦是半可计算的。即半可计算性封闭于运算。证明：令，找一个程序使得（V）程序对停机。程序如下：A FOR VK FOR MK U= TO E IF U=0 NEXT M NEXT V K=K+1 TO A 证毕。定理7. 是半可计算，则是半可计算的。（半可计算对全称量词不封闭，但封闭于受囿全称量词）。证明：因是半可计算谓词，故有部分可计算函数 使得：要证明有部分可计算函数使得计算的程序是：A U= TO E IF V=Z V=V+1 TO A 程序对Z，停机程序对，V=0，1，,Z停机。对，V=0，1，,Z取真值。为故是半可计算的。31、 半可计算与可计算，P可计算当且仅当P和P半可计算；定理8：若P()是可计算的，则它是半可计算的。证明：证P()半可计算，则要找一部分可计算函数h(),使P()h()也就是构造一个程序Q(计算h() )使P()Q对停机。定理9：若P()是可计算的，则P()半可计算。定理10：P（）是可计算的，当且仅当P（）和P（）是半可计算的。（Post）证明： 由定理8，定理9证得。 设P（）和P（）是半可计算的，则有部分可计算函数f（），g（）使P() f() P() g()0 当P（）为真时1 当P（）为真时以下证明存在一个程序Q，使得它计算函数h h（） 显然h是P的特征函数。若有程序计算h（），则P（）是可计算的。程序如下：M1A U1STP（, ，M） U2STP（，M） To E IF 0 To C IF 0 MM1 To AC Y1其中，分别是计算f()，g()程序的Gdel数,证毕。32、 K（X）是半可计算但不是可计算的；K（X）不是可计算的也不是半可计算的；定义3：谓词K（X）（一元谓词）定义为：K（X）(1)（X，X）这表示K（X）为真，当且仅当Gdel数为X的PT程序对输入X停机。定理11：谓词K（X）是半可计算的，但不是可计算的。推论1：K（x）不是半可计算的。定理12：（图形定理）函数f（， ，）部分可计算谓词Vf（， ，）是半可计算的。证明：即设f（， ，）部分可计算，令f（， ，）（， ，）令 (,V） 0 若Vf（， ，）发散(,V）发散 否则故只需证明是部分可计算的，程序如下：A U （，,M）To B IF U0W f（， ，）To E IF WVB M M1To A 设Vf（,）是半可计算谓词，则有一可计算谓词C（V，,，Z）使得：Vf（,）（）C（V,Z）用计算C的程序构造计算f的程序： A For Y KFor Z K UC（Y, , Z）To E IF U0NEXT ZNEXT YKK1To A Y即是f（,）的值，证毕。33、 Wz的定义，半可计算集之集是可数的；整数集之集是不可数的；定义4：定义集合为X |（Z，X）集合表示程序Z（Gdel数）的定义域，即,使Gdel数为Z的PT程序停机的所有X的集合，半可计算集。定理13：半可计算集之集是可数（可枚举）的。证明：即证明可把半可计算集排成如下序列： H1，H2，H3，它们是集合H1,H2,Hn的元素）事实上，下面序列即是我们所要的排列：W0, W1, W2, W3,其中每个Wi 是定义4中所定义的集合。只需证明任取一个半可计算集H，必是某个Wk。设H是一半可计算集，则必有Z使得： XH（Z，X） ，即HWz 证毕。定理14：整数集之集是不可数的。（不可枚举的）证 明：即证不能将整数集之集中元素排成如下序列： S0, S1, S2, S3,其中Si是整数集。用Cantor对角线法构造集合S，使之不含于上述诸Si中 Sn |n (即对每个集合Si取一个不在其中的元素，一定能取到所有的n，因为S0, S1, S2, S3,包含了所有整数集之集，则可以命不含n的集合为Sn)以下证明对任何i 有SSi：反证：若不然，设有i0使SS i0 于是有 nS i0 n (对任意n)若令ni0，则i0S i0 i0S i0,故矛盾，得证。由上述对角线法可证明K（X）不是半可计算的。事实上，我们有：K(X)XWx (由K(X)= (1)（X ，X）知)K(X) XWx 即：K(X) X Wx K(X)半可计算 X | XWx 半可计算由定理14证明知： X | XWx 不在序列Wo, W1, W2, ,之中。而上述序列是半可计算集的枚举，故 X | X Wx不是半可计算集。故K(X)不是半可计算谓词。另可证明半可计算不封闭于全称量词，不封闭于非运算。因K(X)半可计算，故有一可计算谓词C(X,Y)使得：K(X) (Y)C(X,Y) K(X) (Y)C(X,Y)K(X) (Y)C(X,Y)因C可计算，故C亦可计算。故C半可计算。若半可计算封闭于全称量词，则(Y)C（X，Y）半可计算，则推出K（X）半可计算矛盾。因K（X）半可计算，而K（X）不是半可计算的，故半可计算不封闭于。34、 半图厄、图厄和正则系统的定义；特点：字母表、产生式集、初始字；公理和定理；文法：一个短语结构文法（Chomsky）G由下述四部分组成：l 变元集V：V是非空有穷集合，它的元素称变元或非终极符；l 终极符集T：T是有穷集合，它的元素称作终极符；l 且VT；l VT上的产生式的有穷集合；l 起始符S，S。记作G（V，T，S）又称无限制文法，简称文法。文法G实际上就是一个半图厄系统。文法G（V，T，S）的生成语言是：L（G）u |uT* 且S (T*表示T上的字)。半图厄系统（Semi-Thue）每个半图厄系统都定义在某字母表上 Da1, a2,，an.D上的字是指字母表中符号的有穷序列。定义1：字母表D上的半图厄处理是形如下面的产生式集合：（i1，2，m）其中和是D上的字。如： 产生式集 1.ab aa 给出了符号串的推导方法， 2.ba bb 3.bb ab 则组成一个半图厄处理。定义2：若有半W1，W2，Wn（n1）使得： W1W2W3Wn则记为：W1Wn对任意的W，我们定义：WW(假设每个半图厄处理中有)定义3：设半图厄处理，若产生式在中，则产生式也定在中，那么称为图厄处理。下面是一个图厄处理：（图厄处理会将任何推导复原）abaababbaaabbbba定义4：（半）图厄系统是（半）图厄处理加上一个字A（称为该系统的公理或初始字），（半）图厄系统可记做：（P，A）其中P是（半）图厄处理，A是公理。由公理A可推出的符号W称为定理。因有AA 因此公理是一个定理。定义5：说半图厄系统是单演的，若对系统产生的每个字W最多有一个字U使得WU .（当然可以没有U）35、 用半图厄系统模拟Turing机；半图厄系统与图灵机。考虑Turing的四元组形式，知有三种不同的指令：123以下用半图厄系统模拟给定图灵机M，即对给定的图灵机M构造与M密切相关的半图厄系统。的字母表是：1.图灵机M的字母表S0, S1,Sk.2.图灵机M的状态表q1,q2,qn.再加三个新字符h,q,q若设Turing机M有一状态： S2 S3 S0 S1 S3 S2 S1 带上字符 指针指向S1 q4 状态为q4则可把它表示成如下的一个字：h S2 S3 S0 q4 S1 S3 S2 S1 h这种字称为Post字。图灵机的工作过程也就是状态的变化过程，也就是Post字的变化过程。于是可以用半图厄系统来模拟这个过程。我们将用(M)表示所要构造的半图厄系统的半图厄处理（即产生式表）。具体方法如下：（m=0,1,k）(k+1条) （其中So是空字符）（m0，1，,k）(k+1条)非法的z在（M）中加上如下2*k+3个产生式:Qsi q(i=0,1,k)擦去q右边的所有符号，h除外。q h qhsi qq(i=0,1,k)擦去q左边的所有符号，h除外则(M)最后将导出hqh字,这时再也不能用产生式推导了。对任意的POST字W，（M）中最多有一个产生式可用于W，于是（M）是单演的。Turing机的初始带若为： 1 1 1 1 1 1 它对应的Post字为： h 1 1 1 1 1 1 h hh.36、 (M)、(M)、(M)、T()、N()；(M)表示所要构造的半图厄系统的半图厄处理（即产生式表）。由（M）产生式的逆组成的半图厄处理为(M)。M和（M）及(M)之间有如下的关系：引理1 M对X停机 hhhqhM对X停机 hqh hh设M为任一图灵机，则用(M)表示使M停机的所有X的集合。设（，A）为一半图厄系统，则用T（）表示的所有定理的集合。用N（）表示半图厄系统产生的所对应的整数x的集合，即N（）x|T()37、 半图厄系统与正则系统的关系（相关字）；令是半图厄系统，它的字母表是a1,an，公理是A，它的产生式是PQPQ（ i=1,2,m）。，是字母表上的字。我们构造一个正则系统 （）如下：字母表：a1,an, a1,an公理：的公理A约定：若W是上的一个任意字，则W ，并且约定AA产生式：1）PP i=1,2,n2）PP i=1,2,n3) PP i=1,2,n如果（）上的两个字能够仅用上面1）和2）的产生式彼此产生，则称它们为相关的字。相关字：（）上与字相关的字有2n个： （）上的一个字称作正则的，如果它能写成PQ或PQ，其中P和Q均是中字母表上的字。（P，Q可空）半图厄系统是一种代换系统，把一个字的一部分用另一个符号行代替。但正则系统不是代换系统。它的变换规则都是从一个字的左端去掉，再在右端加上字。证明对于上一个字，如果是的一个定理，当且仅当它是（）的一个定理。引理2：如果w是（）的定理，且v是w的一个相关字，则v是（）的定理。引理3：如果w是的定理，则w是（）的定理。引理4：（）的每个定理都是正则的，且都是的定理的相关字。定理3：令是半图厄系统，它的字母表为a1,an，则存在一个正则系统（），它的字母表是a1,an,a1,an,使得的定理恰是（）中全部不带上标“”的字母构成的定理。判定问题判定问题可归结为谓词的可计算问题, 下述谓词描述判定问题定义12：设给定一个“是/否”的判定问题，则定义一谓词，使得取真值，当且仅当问题的回答是“是”，称为特征谓词。定义13：称一判定问题是可判定，若其特征谓词是可计算的。定义14：称一判定问题是半可判定的，若其特征谓词是半可计算的。典型的不可判定问题：Turing机的停机问题I：对任给的Turing机M和任一输入X，判定Turing机M是否停机。（其算法的结果要与M，X有关，即两变元的判定谓词）Turing机的停机问题II：对已给的Turing机M，判定对输入X，Turing机M是否停机。（其算法与M有关，但其判定谓词只有一个变元X）半图厄系统的字问题：对已给定的半图厄系统，判定对任给的两个字1和2是否有12半图厄系统的判定问题：对已给的半图厄系统，判定任给的一字是不