可计算性与计算复杂性（吉林大学教材-李占山）.doc-资料库

第1页 / 共41页

第2页 / 共41页

第3页 / 共41页

第4页 / 共41页

第5页 / 共41页

第6页 / 共41页

第7页 / 共41页

第8页 / 共41页

可计算性与计算复杂性 Calculability & Complexity

目录第二章可计算函数........................................................................................................ 1 1、原语言....................................................................................................................................................................1 2、可计算函数 ............................................................................................................................................................1 第三章递归函数............................................................................................................ 3 1、算子 ........................................................................................................................................................................3 2、原始递归函数 ........................................................................................................................................................3 3、原始递归谓词 ........................................................................................................................................................3 4、受囿取极小 ............................................................................................................................................................4 5、递归与可计算性....................................................................................................................................................5 习题............................................................................................................................................................................5 第四章 POST-TURING 程序和 TURING 机...........................................................................8 1、P-T 程序.................................................................................................................................................................8 2、Turing 机...............................................................................................................................................................8 3、P-T 程序编码.........................................................................................................................................................9 4、一些定理..............................................................................................................................................................10 习题..........................................................................................................................................................................10 第五章半可计算性.......................................................................................................16 习题..........................................................................................................................................................................17 第六章半图厄系统.......................................................................................................18 1、半图厄系统 ..........................................................................................................................................................18 2、半图厄系统与图灵机、半可计算集 ..................................................................................................................18 3、不可判定问题 ......................................................................................................................................................18 习题..........................................................................................................................................................................18 I

第七章图灵机..............................................................................................................26 目录习题..........................................................................................................................................................................26 第八章计算复杂性理论............................................................................................... 27 习题..........................................................................................................................................................................27 历年真题 ................................................................................................................. 29 II

第二章可计算函数第 1页约定： ① 输入变元：X0,X1,…… ② 临时变元：Z0,Z1,…… ③ 输出变元：Y ④ 初始时，一切变元为 0（输入变元除外） ⑤ 转向无定义标号或执行了最后一条指令时，停机 Y=X1·X2 [B] TO A IF X2≠0 TO E [A] X2=X2-1 Y=Y＋X1 TO B 1、原语言本书所有变元为非负整数五条基本指令： ① X=X+1 ② X=X-1 ③ TO A IF X≠0 ④ TO A ⑤ Y=X (X=0，结果仍为 0）宏指令： Y=X1+X2 Y= X1 [B] TO A IF X2≠0 TO E [A] X2=X2-1 Y=Y＋1 TO B 2、可计算函数部分可计算函数：若有一程序 P，使得 P (X1,X2,...,Xn)=f(X1,X2,...,Xn)，则称 f(X1,X2,...,Xn)为部分可计算函数。这里“=”表示：或者两边都无定义，或者两边都有定义并且值相同。可计算函数：若 f(X1,X2,...,Xn)是部分可计算的而且是全函数，则称 f(X1,X2,...,Xn)为可计算函数。两个常用函数 X1 X2 = X1－X2 ，X1≥X2 X1－X2 ，X1≥X2 X1 X2 = 无定义，X1＜X2 0 ，X1＜X2 习题用原语言证明下列函数是可计算函数（显然均为全函数，故只需证明存在 n 元程序 P，使得 P (X1,X2,...,Xn)=f(X1,X2,...,Xn)即可）（1） ( f X X , 1 ) X 1 2 X 2 （2）f(X1,X2)=min{X1,X2} Y=Y+1 [B] TO A IF X2≠0 TO E [A] X2=X2-1 Y=Y·X1 TO B //宏指令 [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

第 2页（3）f(X)=α( X 3) X=X-1 X=X-1 X=X-1 TO E IF X≠0 Y=Y+1 （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 （5） ( f X )  [ X ] （[ ]为向下取整）（6） ( f X )  [log ( 2 X  1)] // t2≤X＜(t+1)2 [B] Z1=Z0 //宏指令 //宏指令 Z1 Z1=Z1·Z1 Z1=Z1-1 Z1=X TO A IF Z1≠0 Y=Z0－1 TO E [A] Z0=Z0＋1 TO B // 2t≤X＜2t+1 X=X+1 [B] Z1=Z0 //宏指令 //宏指令 1Z 1Z =2 Z1=Z1-1 Z1=X TO A IF Z1≠0 Y=Z0－1 TO E Z1 [A] Z0=Z0＋1 TO B

第三章递归函数第 3页 1、算子复合算子：设一个函数 y=f(z1,z2,...,zm)，和一组函数 ... z2=g2(x1,x2,...,xn) z1=g1(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 的结果。 zm=gm(x1,x2,...,xn) 递归算子：设 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、  n i ( , x x 1 2 ,..., x n ) x i (1≤i≤n)出发，只用复合和递归算子得到的函数称为原始递归函数。（它们都是全函数）原始递归函数 add(x,y) fac(x)=x! |x-y| p(x) p(0)=0 p(x+1)=x 0 ,x=y d(x,y)= 1 ,x≠y 3、原始递归谓词 mul(x,y) exp(x,y)=xy sub(x,y)=x y α(x)= 1 0 ,x＝0 ,x≠0 特征函数：设谓词 P(x1,x2,...,xn)，定义函数δ(x1,x2,...,xn)= 0 ，当 P(x1,x2,...,xn) 1 ，当～P(x1,x2,...,xn) 称δ为谓词 P 的特征函数。 δ(x1,x2,...,xn)= 0 ，当(x1,x2,...,xn)S 1 ，当(x1,x2,...,xn)S ，称δ为集合 S 的特征函数。原始递归谓词（集合）：谓词 P（集合 S）的特征函数是原始递归函数。可计算谓词（集合）：谓词 P（集合 S）的特征函数是可计算的。

谓词的受囿全称量词： ( t  ) ( , , P t x x 1 2 ,..., x n )   y 谓词的受囿存在量词： (  t ) ( , , P t x x 1 2 ,..., x n )   y 第 4页 ( , , P t x x 1 2 ,..., x n ) 1  y  t  0 y  t  0 ( , , P t x x 1 2 ,..., x n )  0 定理：f(x1,x2,...,xn,y)是原始递归函数，则 y  t  0/1 , ( f x x 1 2 ,..., ) t 和 y  t  0/1 ( , f x x 1 2 ,..., ) t 是原始递归函数。定理：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  ) P(t,x ,x ,...,x ) n 1 2 y 和 ( t  ) P(t,x ,x ,...,x ) n 1 2 y 是原始递归谓词。 4、受囿取极小受囿取极小：设 P(t,x1,x2,...,xn)是一个谓词，定义函数 min{t | P(t,x1,x2,...,xn) =1} ，若 ( t  ) P(t,x ,x ,...,x ) n 1 2 y min ( , t y  , P t x x 1 ,..., x )n 2 = 0 ，否则称 min t y 为受囿取极小。定理：若 P(t,x1,x2,...,xn)是原始递归谓词，则函数 f(y,x1,x2,...,xn)= min ( , t y  , P t x x 1 ,..., x )n 2 是原始递归函数。原始递归谓词 x=y y|x 原始递归函数 [x/y] x＞y x≤y GN(x) 在 x 因式分解中没有 0 指数 Prim(x) x 是素数 Pi 第 i 个素数 R(x,y) x 除以 y 的余数 t(x) x 因式分解中非 0 指数的个数

(x)i x 因式分解中 Pi 的指数第 5页 x 因式分解中第 Lt(x)个以后指数均为 0 Lt(x) a [a ,a ,...,a ]=P P ... P  n a 1 1 a 2  2  1 2 n n 歌德尔数 #(a,x) x 因式分解中指数为 a 的有几个 x*y y=[b1,b2,…,bm] x=[a1,a2,…,an] x*y=[a1,a2,…,an,b1,b1,b2,…,bm] 配对函数= l()=x 1 2 r()=y (x+y)(x+y+1)+y ，l(z) ,r(z) =z l(z),r(z)≤z 5、递归与可计算性部分递归函数：由初始函数 S(x)=x+1，n(x)=0，  n i ( , x x 1 2 ,..., x n ) x i (1≤i≤n) 出发，用复合、递归和取极小算子得到的函数称为部分递归函数。递归函数：由初始函数 S(x)=x+1，n(x)=0，  n i ( , x x 1 2 ,..., x n ) x i (1≤i≤n) 出发，用复合、递归和对正则函数取极小算子得到的函数称为递归函数。原始递归（全函数）  递归（全函数）  部分递归（部分函数）可计算  递归部分可计算  部分递归习题 1、证明下列函数是原始递归函数 f(x,y)= x （1） x x y 个 x f(x,y)可递归定义如下： f(x,0)=1 f(x,y+1)=exp(x,f(x,y)) ∵exp(x,y)为原始递归函数，∴f(x,y)为原始递归函数。 f(x,y)=[ x] y （2）设 y[ x]=t，则 ty≤x＜(t+1)y ∴ y[ x]= min t x (t+1)y＞x ∵xy 是原始递归函数，x＞y 是原始递归谓词，∴(t+1)y＞x 是原始递归谓词，∴f(x,y)是原始递归函数。（3） ( ) f x  [log x ] 2

资料库

可计算性与计算复杂性（吉林大学教材-李占山）.doc

相关推荐

课程资源

热门标签

最新资料