发布时间 : 星期一 文章可计算性与计算复杂性更新完毕开始阅读
第2页
习 题
用原语言证明下列函数是可计算函数
（显然均为全函数，故只需证明存在n元程序P，使得?P(X1,X2,...,Xn)=f(X1,X2,...,Xn)即可） （1）f(X1,X2)?X1X2 （2）f(X1,X2)=min{X1,X2} Y=Y+1 [B] TO A IF X≠0 2 TO E [A] X=X 22-1 Y=Y·X //宏指令 1 TO B （3）f(X)=α( X 3) X=X-1 X=X-1 X=X-1 TO E IF X≠0 Y=Y+1
（5）f(X)?[X]（[ ]为向下取整） // t2≤X＜(t+1)2 [B] Z1=Z0 Z1=Z1·Z1 //宏指令 Z1=Z1-1 Z1=X Z1 //宏指令 TO A IF Z1≠0 Y=Z0－1 TO E [A] Z0=Z0＋1 TO B
word文档可自由复制编辑
[C] TO A IF X1≠0 TO E [A] TO B IF X2≠0 TO E [B] X1=X1-1 X2=X2-1 Y=Y+1 TO C
（4）f(X)= X1 X2 [C] TO A IF X2≠0 Y= X1 TO E [A] TO B IF X1≠0 Y= X1 TO E [B] X1=X1-1 X2=X2-1 TO C （6）f(X)?[log2(X?1)] // 2t≤X＜2t+1 X=X+1 [B] Z1=Z0 ZZ1=21 //宏指令 Z1=Z1-1 Z1=X Z1 //宏指令 TO A IF Z1≠0 Y=Z0－1 TO E [A] Z0=Z0＋1 TO B 第3页
第三章 递归函数
1、算子
复合算子：设一个函数y=f(z1,z2,...,zm)，和一组函数
z1=g1(x1,x2,...,xn) z2=g2(x1,x2,...,xn) ... zm=gm(x1,x2,...,xn) 称y=f(z1,z2,...,zm)=f(g1(x1,x2,...,xn), g2(x1,x2,...,xn),..., gm(x1,x2,...,xn)) 是复合算子作用于函数f和g1,g2,...,gm的结果。
递归算子：设m(x1,x2,...,xn)和φ(x1,x2,...xn+2)是全函数，定义 h(x1,x2,...,xn,0)= m(x1,x2,...,xn) h(x1,x2,...,xn,t+1)=φ(x1,x2,...xn, h(x1,x2,...,xn,t),t) 称h是递归算子作用于函数m和φ的结果。 （h是全函数）
取极小算子：设f(x1,x2,...,xn,z)是全函数，定义h(x1,x2,...,xn)= min{z|f(x1,x2,...,xn,z)=0}
称h是取极小算子z作用于函数f的结果。
（h不一定是全函数，若f为正则函数，则h为全函数）
2、原始递归函数
原始递归函数：由初始函数S(x)=x+1、n(x)=0、
ni(x1,x2,...,xn)?xi (1≤i≤n)出发，
只用复合和递归算子得到的函数称为原始递归函数。
（它们都是全函数）
原始递归函数 add(x,y) fac(x)=x! |x-y| p(x) p(0)=0 p(x+1)=x mul(x,y) exp(x,y)=xy sub(x,y)=x y 1 ,x＝0 α(x)= 0 ,x≠0 0 ,x=y d(x,y)= 1 ,x≠y
3、原始递归谓词
0 ，当P(x1,x2,...,xn) 特征函数：设谓词P(x1,x2,...,xn)，定义函数δ(x1,x2,...,xn)=
1 ，当～P(x1,x2,...,xn)
称δ为谓词P的特征函数。
0 ，当(x1,x2,...,xn)?S
δ(x1,x2,...,xn)= ， 称δ为集合S的特征函数。
1 ，当(x1,x2,...,xn)?S
word文档可自由复制编辑
第4页
原始递归谓词（集合）：谓词P（集合S）的特征函数是原始递归函数。
可计算谓词（集合）：谓词P（集合S）的特征函数是可计算的。 谓词的受囿全称量词：(?t)?yP(t,x1,x2,...,xn)??P(t,x,x,...,x)?1
12nt?0yy谓词的受囿存在量词：(?t)?yP(t,x1,x2,...,xn)?y?P(t,x,x,...,x)?0
12nt?0定理：f(x1,x2,...,xn,y)是原始递归函数，则
t?0/1?f(x,x,...,t)和?f(x,x,...,t)是原始递归函数。
12y12t?0/1定理：P、Q是原始递归谓词，则～P 、P?Q、P?Q是原始递归谓词。 定理：R、S是原始递归集合，则R、R?S、R?S是原始递归集合。
定理：P是原始递归谓词，g和h是原始递归函数，则 g(x1,x2,...,xn) ，当P(x1,x2,...,xn)
f(x1,x2,...,xn)= 是原始递归函数。 h(x1,x2,...,xn) ，当～P(x1,x2,...,xn)
定理：P(x1,x2,...,xn)是原始递归谓词，h1,h2,…,hn是原始递归函数，则P(h1,h2,...,hn)是原始递归谓词。
定理：f和g是原始递归函数，则f=g是原始递归谓词。
定理：若P(t,x1,x2,...,xn)是原始递归谓词，则
(?t)?yP(t,x1,x2,...,xn)和(?t)?yP(t,x1,x2,...,xn)是原始递归谓词。
4、受囿取极小
受囿取极小：设P(t,x1,x2,...,xn)是一个谓词，定义函数
min{t | P(t,x1,x2,...,xn) =1} ，若(?t)?yP(t,x1,x2,...,xn)
minP(t,x1,x2,...,xn)=
t?y0 ，否则
称min为受囿取极小。
t?y
定理：若P(t,x1,x2,...,xn)是原始递归谓词，则函数f(y,x1,x2,...,xn)=minP(t,x1,x2,...,xn)是原始递归函数。
t?y
原始递归谓词 x=y y|x x＞y GN(x) 在x因式分解中没有0指数 x≤y Prim(x) x是素数 word文档可自由复制编辑
第5页
原始递归函数 [x/y] R(x,y) x除以y的余数 (x)i x因式分解中Pi的指数 Pi 第i个素数 t(x) x因式分解中非0指数的个数 Lt(x) x因式分解中第Lt(x)个以后指数均为0 #(a,x) x因式分解中指数为a的有几个 [a1,a2,...,an]=P1a1P2a2...Pnan 歌德尔数 x*y x=[a1,a2,…,an] y=[b1,b2,…,bm] x*y=[a1,a2,…,an,b1,b1,b2,…,bm] 配对函数
5、递归与可计算性
部分递归函数：由初始函数S(x)=x+1，n(x)=0，和取极小算子得到的函数称为部分递归函数。 递归函数：由初始函数S(x)=x+1，n(x)=0，
nini(x1,x2,...,xn)?xi (1≤i≤n) 出发，用复合、递归
(x1,x2,...,xn)?xi (1≤i≤n) 出发，用复合、递归和对
正则函数取极小算子得到的函数称为递归函数。
原始递归（全函数）?递归（全函数）?部分递归（部分函数）
可计算?递归
部分可计算?部分递归 习 题
1、证明下列函数是原始递归函数
（1）
f(x,y)=xxx?y个x
f(x,y)可递归定义如下： f(x,0)=1 f(x,y+1)=exp(x,f(x,y))
∵exp(x,y)为原始递归函数，∴f(x,y)为原始递归函数。
word文档可自由复制编辑