计算理论复习题总结

Church-Turing论题：可计算性等价于Turing机可计算性。

《计算理论》复习题总结12、计算：Truing机所进行的工作就是计算。

13、可计算：Turing机能够进行的工作就叫可计算。

14、几个计算模型；各种计算模型的特点；图灵机的

1、自动机、可计算性、复杂性内涵及关系；

特点；

2、计算理论的三个传统的核心领域：自动机、可计算性和复杂

计算模型：1.递归函数。Godel,Church,等人提出并完善了递归

性。通过“计算机的基本能力和局限性是什么？“这一问题

函数理论。从数学演算的思想出发，考虑从简单的、直观上可计算

将这三个领域联系在一起。可计算理论与复杂性理论是密切相

的函数出发构复杂的可计算函数。2.Turing机(理论模型)：Turing

关的，在梵杂性理论中，目标是把问题分成容易计算的和难

研究的Turing机计算模型与现代计算机更接近，在Turing机的基

计算的：而在可计算理论中，是把问题分成可解的和不可解。

础上引进了大量的自动机。3.Church一人演算：用来描述计算过

自动机阐述了计算的数学模型的定义和性质，主要包含两种

程，基本思想主要用于函数式程序语言的研制。4.Post系统(符

模型：有穷自动机模型：上下文无关文法模型。可计算性理论

号变换系统)：Post系统的基础上引进了大量的形式语言。

和复杂性理论需要对ii算机给r个准确的定义。自动机理论

Turing机的特点：存储无穷，时间无限制。Turing机可计算只是

允许在介绍与计算机科学的其他非理论领域有关的概念时使

理论上可计算，并不是现实可计算。现实可计算：研究计算复杂

用计算的形式化定义。

性。但如果Turing机不可计算则现实更不可计算。

3、有穷自动机、正则语言、正则表达式、非确定有穷自

原语言，指令系统，输入输出规定；

动机、非正则语言；

15、原语言：变元、标号(语句标号)、指令：X=X+1；X

有穷自动机：描述能力和资源极其有限的计算机模型。是一个5元=X-1；ToAIFXWO；ToA；Y=X输入变元用x表示x,

组(Q,E,6,qO.F),其中DQ是一个有穷集合，称为状态集。xl,x2,x3,...输出变元用y表示，函数只输出一个

值。

2)X是一个有穷集合，称为字母表。3)6：QXE-Q是转移函

16、对程序做如下两点规定：1、当程序开始执行时自动认

数。4)qOQ是起始状态。5)FQ是接受状态集。为一切变元的值为0(输入变元除外)2、当程序出现下列两

止则语言：如果一个语言能被有力自动机识别。种情形之一时，自动认为停机。a、转向无定义的标号b、执

行程序的最后一条指令。

4、正则表达式：用正则运算符构造描述语言的表达式。称R是正

则表达式，如果R是：Da,a是字母表中的一个元素；2)17、n元程序对应的n元函数的定义；

:3);4)(RIR2)；5)(RIR2)：6)(R1*)若程序P恰有n个输入变元XI,X2,……,Xn,而没有其它X变元，

5、非确定有穷自动机：是一个5元组(Q,£,6,qO,F),其则称P为n元程序。

中DQ是有穷状态集。2)E是有穷字母表。3)6：QXE

n元程序》对应的函数甲p(XI,X2,……，Kn)定义如下：

-P(Q)是转移函数。4)qOQ是起始状态。5)FQ是接受

状态氯,若程序P对于输入值al,•・…・，an停机且Y=b

6、上下文无关语言及上下文无关文法、歧义性、乔姆1Pp(al,a2,...,an)=1

斯基范式、下推自动机、等价性、非上下文无关语言；l无定义若程序P#输入值al,•“…,an不停机

上下文无关语言：用上下文无关文法生成的语言。

部分可计算，全函数，可计算函数：

上下义无关义法：是一个4元组(V,E,R,5)且1)V是一个行

穷集合，称为变元集2)£是一个与V不相交的右.穷集合，称为终答：函数f(XI,X2,……，Xn)被称为部分可计算的，若有一程

结符集3)R是一个布.穷规则集，每条规则由一个变元和一个由变序P使得中p(Xl,X2,……,Xn)=f(XI,X2,……,Xn),“="

元及终结符组成的字符串构成，4)SV是起始变元

表示：或者两边都无定义，或者两边都有定义并且其值相同。

7、歧义性：如果字符串W在上下文无关文法G中有两个或者两上

以上不同的最左派生，则称G歧义地产生的字符串W。如果文18、函数f(XI,X2,……,Xn)被称为全函数，若它对一

法G歧义的产生某个字符串则称G是歧义的。切XLX2,……，Xn的值都有定义。

8、乔姆斯基范式：一个上下文无关文法如果它的每一个规则具有

函数f(〉：1,X2,……,Xn)被称为可计算函数，若它是部分可计

如下形式A-BCA-a其中a为任意终结符，ABC为任意变元

算的且是全函数。

且BC不是起始变元，此外允许规则S-其中S是起始变元。

9、下推自动机：是6元组Q,£,,6,qO,F),这里Q,E,复合、递归、取极小，正则；初始函数，原始递

,F都是有穷集合，并且1)Q是状态集2)£是字母表3)归函数

是栈字母表4)6：QXEX-P(QX)是转移

答：复合:设有函数Y=f(Zl,Z2……，Zm)

函数学5)qOQ是起始状态。6)FQ是接受状态集。

10、各种等价性；和函数Zl=gl(XI,……,Xn)……Zm=gm(XI,……,Xn)

每一台非确定型有穷自动机等价于一台确定救有穷自动机：一个语则n元函数Y=h(Xl,...,Xn)

言是正则的当且仅当可以用正则表达式描述：一个语言是上下文无

=f(gl(XI,...,Xn),……，gm(XI,……,Xn))

关的则存在一台下推自动机识别它。

11、计算科学；能性问题；Church-Turing论题；计被称为函数f和gl,g2,……,gm的复合函数。

算.递归：设m(XI,X2,...,Xn)和。(XI,X2,....,Xn,Xn+1,

可计算’；

Xn+2)是全函数，定义

计算科学：系统的研究信息描述和变换的算法，包括其理论、分h(XI,X2,...,Xn,o)=m(XI,...,Xn)

析、设计、效率、实现和应用。用计算科学涵盖并称谓计算机科学h(XI,X2,...,Xn,1+1)=4>(XI,...,Xn,h(XI,...,

和计算机二程。计算机科学所研究问题的核心是能行问题。能行问Xn,t),t)称h是递归算子作用于函数m和6得到的n+1元递归

题：什么能被(有效的)自动化？什么不能被(有效)的自动函数，且是全函数。

化？

取极小：设f(XI,X2,……，Xn,Z)为全函数，定义h(Xl,……，证明：令Q(Y,XI,……,Xn)=P(t,XI,……,Xn)

Xn)=min{Z|f(XI,……，Xn,Z)=0}称卜是取极小算子作用要证明Q是原始递归谓词。令6是P的特征函数，并令

n+1元函数f得到的n元取极小值函数.匚

1(Y,X1,…,Xn)=Yl3(t,X1,...,Xn)

正则函数：函数f(XI,……,Xn,Xn+1)被称为正则的，若对任1=0

何一组XI,X2,……,Xn都有Z使得：f(XI,……，Xn,Z)=0故6’是原始递归函数。

故，对正则函数取极小算子的结果得到一全函数。下面证明6,是Q的特征函数：

初始函数：S(X)=X+1(后继函数)n(X)=0(零函数)如存在一个0WtoWY使P(to,xi,-,Xn)为真，则

UNX1,…，Xn)=Xi(IWiWn)投影函数8(t0,Xl,-,Xn)=0,故6'(Y,Xl,-,Xn)=0

由初始函数S(X),n(X),Uin(Xl,Xn)=Xi(iWiWn)出

即当Q(Y,Xb-,X(1)为真时V为0；

发，只用第合和递归算子得到的函数称为原始递归函数。如对所有0WIWY有P(t,XI,……，Xn)为假，

19、由初始函数S(X).n(X),UinfXl,-.Xn)=Xi(1则时所有OWlWY都有8(l,X„-,X)=1

WiWn)出发，用复合，递归和取极小算子得到的函数称为部n

分递归函数。故6'(Y,X„-,X„)=1

由初始函数S(X),n(X),Uin(Xl,-,Xn)=Xi(IWiWn)出即当Q为假时，6'(Y,Xl,-,Xn)=1

发，用复合，递归和对正则函数取极小算子得到的函数称为递归故3'是Q的特征函数，Q是原始递归谓词。证毕。

函数。定理6:若P(t,XI,……，Xn)是原始递归的，

谓词P的特征函数，集合S的特征函数；则P(t,XI,……，Xn)是原始递归的。

答：没P(X,…,Xn)是n元谓词，定义函数证明：令6和6'分别是P和P的特征函数

、、[0当P为真时定理7:设S和R是原始递归集合，则，SCR,SUR是

b(XI,…,Xn)=<,,.

[1当〜P为真时L原始递归集合。(是R的余集)

称6为谓词P的特征函数，证明：令61,62分别是S和R的特征的数，63是的特征函数

设S措集合，则定义函数：则63=(62)故是原始递归集合。令64是SCIR的特征函

“XIXQ=J0当(Xl,...Xn)eS时数，则64=((61+62))故SCR是原始递归集合。

[1当SHJ-令55是SUR的特征函数，则(①代表空元素)

称6为集合S的特征函数，85(XI,••••••,Xn)=61(XI,••••••,Xn)•82(XI,••••••,Xn)•

20、原始递归谓词、原始递归集合；可计算谓词、可21、(61(Xil,•­•,Ximl,①，…，①)用中凑满n

计算集合；项+62(Xjl,.......,Xjm2,①，.......，①))因对幻，...，

答：谓词P(集合S)是原始递归的，如其特征函数是原始递归的。XnERUS可能有如下三种情况：1)XI,……，XnCR2)

谓词P(集合S)是可计算的，如其特征函数是可计算的。XI,……，Xnes

三个定理:若P,Q原始递归，则〜P,PAQ,P

22、3)Xil,.......,XimieRXjl,……,Xjm2WS故得证。

VQ均原始递归；

23、复合后仍然是原始递归谓词；

定理1:P(XI,…,Xn)原始递归的〜P(XI，…Xn)原始递归的。

定理8:设P(zl,z2,•••»zn)是原始递归谓词，hl,.......,hn是n

证明：设6和6'分别为P和〜P的特征函数

个k元原始递归函数，(n2l,k>0)则P(hl(XI,.......,

只需证明：5原始递归5'原始递归

Xk),……,

由6及3'的定义知6'(X“…，XJ=a(5(X„X..))

hn(XI,……，Xk))也是原始递归的。

6(X„…,[)=a(5'(Xi,…,X„))故得证。

证明：令6'为复合谓词的特征函数，6为P的特征函数，则有

定理2:P,Q原始递归，则PQ也是原始递归的。

6'(XI,X2,……，Xk)

证明：设61,82,63分别是P,Q,PQ的特征函数则有

=6(hl(XI,.......,Xk),........,hn(XI,.......,Xk))

«3(21,…,Zk)=a(a(S1(X1,…，Xn)+S2(Y1,—,Ym)))

3,hl,……,hn均为原始递归函数。故6'亦是。证毕。

故63是原始递归函数。故得证。

f,g是原始递归函数，f=g是原始递归谓词；

定理3:P,Q原始递归，则PQ也是原始递归的。

24、定理9：f,g是原始递归函数，f=g是原始递归谓词。

证明：设61,52,63分别是P,Q,PQ的特征函数则

证明:知X=Y是原始递归谓词，由定理8知f=g是原始递归谓词。

63(Z1,…，Zk)=61(X1,…,Xn)・62(Y1,Ym)故得证。受囿取极小，由谓词到函数的转换。给出了构造

定理4：设P是原始递归谓词，g、h是原始递归函数，递归函数的又一种方式；

则如下定义的函数f是原始递归的受囿取极小值

设P<t,XI,……,Xn)为谓词，定义函数：

f“IXn)[g(XI,……，Xn)当P为真

h(XI,……，Xn)当〜P为真min(t|t5YAP(t.XI........Xn))

咽PGXL……，Xn)=

证明：设6是P的特征函数，f=g・a(6)+h-6故得证。0否则

定理5:P(Y,XI,……，Xn)是原始递归谓词，则

P(t,Xl,……,Xn)是原始递归谓词。若P是原始递归谓词，则其受囿取极小函数是原

始递归函数；C.可计算函数取极小算子，结果为一部分可计算函数。

定理10:若P（t,XI,……,Xn）是原始递归谓词，则具体证明由以下6个引理组成:

f（Y,XI,....Xn）=minP（3XI,……，Xn）引理1.初始函数S（X）,n（X）,是可计算的.

14Y是引理2.复合保持（部分）可计算性。

原始递归函数。引理3.可计算函数经取极小算子后，得一部分可计算函数。

证明：用表示XI,...,Xn,设：引理4.正则函数取极小算子，保持可计算性。

即10是第一个使P（t,）取真值的t值。28、引理5.可计算函数用递归算子作用后，仍保持可计算

设是P（t,）的特征函数。性。

引理6.多元函数用递归算子作用后仍保持可计算性。

考虑函数：，不难验证：

Post_Turing机：数据、符号、指令、带上数

亦不难验证：的表示、输入输出；P-T（部分）可计算；

而t0是使P（t,）为其时最小的t值，故有Post—Turing程序

1）数据一一存于带上.带有一个指针.两端无穷长.永远有空白

£j卜5（t,X）当（3t）sYP（t.X）为真

U=0r=0位，无穷多个格，每个格可写一个字符。

2）符号一一B1B代表空白符。

f（Y.XI........Xn）=3

)

0否则①指令---6条。

②RiGiir指针右移一格

③LEFT指针左移一格

因X）是原始递归（］）是原始递归）。④WRITE1将指针所指的带上的当前格改写为1

⑤WRITEB将指针所指的带上的当前格改写为B

TO4IF1若当前格为1,则转到以A为标号的指令

25、令是其特征函数，则有：⑥

TO4IFB若当前格为B,则转到以A为标号的指令

26、第i个素数、Godel数、配对函数；4

)带上数一若N为一个数，则在带上把它表示成N+1个1。

Pi是P（i）的简写（P不是前驱函数）

用X表示X的带上表示.

Pi的值是第i个素数的值.（约定P0=0是第0个素数：Pl=2是输入：若用一个P—T程疗计算出数f（Xl,…,Xn）,则输入Xi的值

第1个素数；P2=3是第2个素数；P3=5是第3个素数）按卜述方法写在带上

11-11B11…11B-B11…11

户。=。X.+lX2+lXa+1

-输出：计算的结果是程序结果的带上1的个数减1如:

11BB11BBB111结果是6

TTlin（PrimCt）/x（t>Pi）>

-t^<Pi!+1）定义L称函数f是P—T部分可计算的，有一个P—T程序计算它。

定义2.称函数f为P—T可计算的，如果它是P—T部分可计算的

证明：必须证明在PiVtWPi!+1中有素数即Pi+1W

并且是全函数。

Pi!+1广义Post_Turing机：字母表、指令；其它同

若Pi!+1是素数，则自然有Pi+lWPi!+1,证毕。Post_Turing机；

字母叠so,si,S2,sk.（每个表示一个符号）

现假设Pi!+1不是素数，则它一定有素数因子：

约定S0=B,Sl=l

1）此因子不会是0,因0不是任何数的因子

指令：RIGHT

2）P1,P2,...,Pi也不可能是因子因Pi!+1=1祝可・1“甲iLEFT

+1故用Pl,P2,……,Pi去除均应余1。WRITESi（i=0,1,2,k）

TOAIFSi（i=0,1,2,k）

所以，Pi!+1的素数因子大于Pi,小于等于Pi!+1,证毕。

29、每个（部分）可计算函数是P—T（部分）可计

算函数；P-T（部分）可计算函数是广义P-T（部分）

哥德尔数,c可计算函数；广义P-T（部分）可计算函数是（部分）

C】表示P「・P；2.……・P；n

可计算函数；

定理1.每个（部分）可计算函数是P-T（部分）可计算函数

即（al,-,anJ=口证明：任何一个（部分）可il•克函数的程序P均可模拟为等价的P

—T程序<（如前面的原语言程序）

/=!

一般程序的操作对象是变元，而P—T程序操作对象是带

任取正整数X都有其对应的一组哥德尔数定理2P—T（部分）可计算的函数是广义P-T（部分）可计算函数

定理3广义P-T（部分）可计算函数是（部分）可计算的。

<X,Y>-----求Cantor对角线上元素的序号

Turing机：带、读写头、控制器、程序；四元

<X,Y>=E（x+y）+y=l/2（X+Y）•（X+Y+l•+Y

组和五元组；停机规定；Turing机是什么？

27、递归函数是可计算的；部分递归函数是部分Turing机：

可计算的。三部分：一条带，一个读写头一个控制器（控制器内

定理11.每个递归函数是可计算的存有程序）

一个字母表S={SO,SI,S2,…，Sk）

定理12.绿个部分递归函数是部分可计算的。

一个状态集Q={ql,q2,•••,qn）

证明卜•述一定理需从以下三个方面证明：1.带和读写头（指针）：

A.每个初始函数是可计算的。带是无穷长的，两端伸向无穷，带上划成格子，每个格子中"I写

一个符号。符号均属于字母表：E={S0,si,S2,…，Sk}

B.复合，递归和正则函数的取极小运算保持可计算性。

读写头对准一个格子，它可以读写带上的符号，可以擦去或改写,

或g对给定的时，对Z,X1,……,Xn无定义定义1.谓词称为半可计算的。如果存在一部分可计

枚举定理:对每个n,部分函数是部分可计算函数。算函数使得下式成立：

这实际上是用部分可计算函数的定义域来定义了谓词的半可计算

计步谓词定义如下：

性。就是说，一个谓词是半可计算性的，当且仅当它的真

值域等于某部分可计算函数的定义域，

SW"）（Z,X”X2，...,X”,M）opR⑵并且编码为z的p

0G等价定义：谓词是半可判定的。当且仅当存在一个程序，使

得：对于停机。

-T程序疝于输入X"在步内停机。（这里的一步是P-T定义2.集合S是半可计算的，如果存在一部分可计算函数

，使得：

程序的•芸指令的一次执行）等价定义：S是半可计算的当且仅当它的特征谓词是半可计算的。

计步定理：对任意n,谓词是可计算的。半可计算的封闭性，对运算符八和V及三和受囿

证明：（函数值：若为真Y=0,为假Y=1（对于其特征函数））全称量词封闭，对n和u封闭；不封闭于全称量词和非运

①检查Z是否某P-T程序的哥德尔数，若不是Y=1算；

②模拟初始带定理1.整数集H是半可计算的当且仅当存在某部分可计算函数

③建立一人步计数器j,每执行一条指令j+L若jXLY=R

/（X，…,X“）使得H=｛/（x丁.,X”/（5,...，

若M步内停止，Y自动取0,Y=0.

定理2.若P（）和Q（）是半可计算的，

程序如下：（主要利用通用程序）

TOGIFPROG（Z）则1＞（文）人Q（X）亦为半可计算谓词

定理3.若P（）和Q（）是半可计算谓词，则

X=STP”"…,Xn）

P（X）vQ（天）亦是半可计算谓词。

J=0

V=1定理4.如果加和&是半可计算集。则&DS?和&cS:亦是半

1=1可计算集。

AJ=J+1定理5.谓词是半可计算的当且仅当存在一个可计算谓词使得:

TOGIFJ>M（Y）

证明：（）设（Y）

TOEIF(1=0)7(i>LT(Z))

1c（N,y）是可计算的）（必要性）

TORIFK(Z)z)=l

要证明〃（又）是半可计算的。即要找一个程序〃（手）使得

SV=V+1程序对于停机。程序如者：

TOD

G7=1得证。[A]u=＜5（x,y）

迭代定理：对一切n,有原始递归函数便

TOEIF

得对于•切U=0

Y=Y+1

①…(Z,X]，…，X“，K，...K）=O）TOA___________________________

（5是C的特征函数）

（S〃（Z,X"..,X“），K，.・・,以）若宥一个Y使为其,则可找到Y则停机。

否则程序永远不停机。故”（又）是半可计算的。

（迭代定理给出了n取不同值时（D（"）（Z,X],…，X〃）之间

（=＞）设"（又）是半可计算谓词。

的关系。）证明存在一个可计算谓词，使得

半可计算性（主要对谓词和集合），可判定=可

H（X）＜＞（3Y）c（x,r）

计算，半可判定=半可计算；=

集合：常月递归（可计算）和递归可枚举（半可计算性）：因为是半可计算的，必有部分可计算函数使得

谓词：常月到可判定（可计算）和半可判定（半可计算性）由枚举定理有，使得：

集合S是递归的：如果存在一个算法A。使得对任何的。因此有，表示程序（GGdel数），对于在M步内停机,

在有限步内回答是否，即：（表示（））即有

集合S是递归可枚举的：如果存在一个算法A,使得对任何的，H（X）0＜3M＞STIXZO,又，M）.

若则在有限步内回答“是"，若，则算法不能给出回

答，不终iz,即：因STnZo,又，M）是可计算的。

谓词P（）是可判定的：如果存在一个算法A使得对任给的令其为=,故定理成立。

定理6.设是半可计算谓词，则（V）亦是

能够在有限步内回答P（）是“真"，还是"假"，即有:半可计算的。即半可计算性封闭于三运算。

-「'是"P（X）为真证明：令，

A（P,X）=].

“否"P（X）为假找一个程序4（又）使得

谓词P（）是半可判定的：如果有一个算法A使得对任给的，（3v）H（V,X）U＞程序"（又）对X停机。

若P（）为真，则在有限步内回答“是"，否则算法不终止（即

35、不能给出答案），即：

36、f（Xl,-,Xn）t和f（XI,…，Xn）I

：表示函数对于有定义；

：表示函数对于无定义；可视为谓词

Df=｛（X,X”"｝表示函数f的定义域。

程序如下：证毕。程序如下：

[A]FORV<KM=1

FORMWK[A]Ul-STP（f,M）

U=STP（Zo，V,文，M）U2=STP（9,M）

TOEIFU=0ToEIF「°

NEXTM

ToCIF[J=o

NEXTV2

K=K+1M=M+1

TOAToA

[C]Y=1

定理7.是半可计算，则是半可计算的。(半可计算对全称量

词不封闭，但封闭于受囿全称量词)。