可计算性与计算复杂性

可计算性与计算复杂性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机 (9)3、P-T程序编码 (10)4、一些定理 (10)习题 (11)第五章半可计算性 (16)习题 (17)第六章半图厄系统 (18)1、半图厄系统 (18)2、半图厄系统与图灵机、半可计算集 (18)3、不可判定问题 (18)习题 (19)第七章图灵机 (26)习题 (26)第八章计算复杂性理论 (27)习题 (28)历年真题 (29)第二章可计算函数1、原语言本书所有变元为非负整数五条基本指令：①X=X+1②X=X-1 (X=0，结果仍为0）③TO A IF X≠0④TO A⑤Y=X宏指令：·X2、可计算函数部分可计算函数：若有一程序P，使得P(X1,X2,...,X n)=f(X1,X2,...,X n)，则称f(X1,X2,...,X n)为部分可计算函数。

这里“=”表示：或者两边都无定义，或者两边都有定义并且值相同。

可计算函数：若f(X1,X2,...,X n)是部分可计算的而且是全函数，则称f(X1,X2,...,X n)为可计算函数。

两个常用函数X1－X2，X1≥X2X1－X2，X1≥X2X1X2 = X12 =无定义，X1＜X20 ，X1＜X2约定：①输入变元：X0,X1,……②临时变元：Z0,Z1,……③输出变元：Y④初始时，一切变元为0（输入变元除外）⑤转向无定义标号或执行了最后一条指令时，停机习 题用原语言证明下列函数是可计算函数（显然均为全函数，故只需证明存在n 元程序P ，使得P ϕ(X 1,X 2,...,X n )=f(X 1,X 2,...,X n )即可） （1）2121(,)X f X X X =（6）2()[log (1)]f X X =+第三章 递归函数1、算子复合算子：设一个函数y=f(z 1,z 2,...,z m )，和一组函数z 1=g 1(x 1,x 2,...,x n ) z 2=g 2(x 1,x 2,...,x n ) ... z m =g m (x 1,x 2,...,x n ) 称y=f(z 1,z 2,...,z m )=f(g 1(x 1,x 2,...,x n ), g 2(x 1,x 2,...,x n ),..., g m (x 1,x 2,...,x n )) 是复合算子作用于函数f 和g 1,g 2,...,g m 的结果。

（h 是全函数）取极小算子：设f(x 1,x 2,...,x n ,z)是全函数，定义h(x 1,x 2,...,x n )= min{z|f(x 1,x 2,...,x n ,z)=0}称h 是取极小算子z 作用于函数f 的结果。

（h 不一定是全函数，若f 为正则函数，则h 为全函数）2、原始递归函数原始递归函数：由初始函数S(x)=x+1、n(x)=0、12(,,...,)n in i x x x x = (1≤i ≤n)出发，只用复合和递归算子得到的函数称为原始递归函数。

（它们都是全函数）原始递归函数3、原始递归谓词0 ，当P (x 1,x 2,...,x n ) 特征函数：设谓词P (x 1,x 2,...,x n )，定义函数δ(x 1,x 2,...,x n )=1 ，当～P (x 1,x 2,...,x n )称δ为谓词P 的特征函数。

0 ，当(x 1,x 2,...,x n )∈Sδ(x 1,x 2,...,x n )= ， 称δ为集合S 的特征函数。

1 ，当(x 1,x 2,...,x n )∉S原始递归谓词（集合）：谓词P （集合S ）的特征函数是原始递归函数。

可计算谓词（集合）：谓词P （集合S ）的特征函数是可计算的。

谓词的受囿全称量词：12120()(,,,...,)(,,,...,)1yy n nt t P t x x x P t x x x ≤=∀⇔=∏谓词的受囿存在量词：1212()(,,,...,)(,,,...,)0yy n nt t P t x x x P t x x x ≤=∃⇔≠∑f(x 1,x 2,...,x n ,y)是原始递归函数，则120/1(,,...,)yt f x x t =∑和120/1(,,...,)yt f x x t =∏是原始递归函数。

P 、Q 是原始递归谓词，则～P 、P Q ∨、P Q ∧是原始递归谓词。

R 、S 是原始递归集合，则R 、R S ⋃、R S ⋂是原始递归集合。

P 是原始递归谓词，g 和h 是原始递归函数，则 g (x 1,x 2,...,x n ) ，当P(x 1,x 2,...,x n )f (x 1,x 2,...,x n )= 是原始递归函数。

h (x 1,x 2,...,x n ) ，当～P(x 1,x 2,...,x n )P (x 1,x 2,...,x n )是原始递归谓词，h 1,h 2,…,h n 是原始递归函数，则P (h 1,h 2,...,h n )是原始递归谓词。

f 和g 是原始递归函数，则f=g 是原始递归谓词。

P (t,x 1,x 2,...,x n )是原始递归谓词，则12n ()P(t,x ,x ,...,x )y t ≤∀和12n ()P(t,x ,x ,...,x )y t ≤∃是原始递归谓词。

4、受囿取极小受囿取极小：设P(t,x 1,x 2,...,x n )是一个谓词，定义函数min{t | P(t,x 1,x 2,...,x n ) =1} ，若12n ()P(t,x ,x ,...,x )y t ≤∃12min (,,,...,)n t yP t x x x ≤=0 ，否则称min t y≤为受囿取极小。

若P(t,x 1,x 2,...,x n )是原始递归谓词，则函数f (y,x 1,x 2,...,x n )=12min (,,,...,)n t yP t x x x ≤是原始递归函数。

原始递归函数 2n P ...P 歌德尔数] y=[b 1,b 2,…,b m ] ,b1,b ,b ,…,b ]5、递归与可计算性部分递归函数：由初始函数S(x)=x+1，n(x)=0，12(,,...,)n in i x x x x = (1≤i ≤n) 出发，用复合、递归和取极小算子得到的函数称为部分递归函数。

递归函数：由初始函数S(x)=x+1，n(x)=0，12(,,...,)n in i x x x x = (1≤i ≤n) 出发，用复合、递归和对正则函数取极小算子得到的函数称为递归函数。

原始递归（全函数）⊂递归（全函数）⊂部分递归（部分函数）可计算⇔递归部分可计算⇔部分递归 习 题1、证明下列函数是原始递归函数（1）}xf(x,y)=xxy 个xf(x,y)可递归定义如下： f(x,0)=1f(x,y+1)=exp(x,f(x,y))∵exp(x,y)为原始递归函数，∴f(x,y)为原始递归函数。

（2设=t ，则t y ≤x ＜(t+1)y∴=min t x≤(t+1)y ＞x∵x y 是原始递归函数，x ＞y 是原始递归谓词，∴(t+1)y ＞x 是原始递归谓词，∴f(x,y)是原始递归函数。

（3）2()[log ]f x x =设2[log ]x =t ，则2t ≤x ＜2t+1 ∴ 2[log ]x =min t x≤2t+1＞x∴f(x)是原始递归函数。

（4）f(x)表示x 各位数字之和 设x 为n 位数，n=2[log ]x +1110()[(,10)(,10)]10n i i i i f x R x R x -+-==-⋅∑∴f(x)是原始递归函数。

（5）设a n =f(n), b n =g(n)都是递增的原始递归函数，将a n ，b n （n ＝0，1，2，……）混合在一起，再从小到大排列得到函数c n =φ(n)，证明φ(n)是原始递归函数。

φ(n)递归定义如下： φ(0)=min{a0,b 0} φ(n+1)=max{,}min {(()()()())(())}n n n i n j t a b i t a j t b t n φ≤≤≤∃=∨∃=∧>∵0000000000min{a ,b }= a (sub(a ,b )) + b (sub(b ,a ))d(a ,b )αα⋅⋅⋅n n n n n n n n n n max{a ,b }= b (sub(a ,b )) + a (sub(b ,a ))d(a ,b )αα⋅⋅⋅∴min{a 0,b 0}，max{a n ,b n }是原始递归函数，∴φ(n)是原始递归函数。

（6）将任意两个素数乘积按从小到大排成一个序列，令这个序列通项即第n 项为f(n)，证明f(n)是原始递归函数。

f(n)可递归定义如下：f(1)=4 ;2*2f(n+1)= 2min{()()()()}nn n i j t P i j t P P t f n ≤≤≤∃∃=⋅∧> ∴f(n)是原始递归函数。

（7）称三边均为整数的直角三角形的斜边为勾股数，将它们从小到大排列，第n 个勾股数记作R(n)，证明R(n)是原始递归函数。

R(n)可递归定义如下： R(1)=5R(n+1)=222222()()()min {()()()(())}R n R n t R n i j i j t t R n ≤≤≤∃∃+=∧> ∴R(n)是原始递归函数。

2、计算3*2＝？3=20×31＝[0,1]，2＝21＝[1]，3*2＝[0,1,1]＝20×31×51＝153、用原语言程序（限用五条基本指令）计算谓词“x 1=x 2”的特征函数。

0 ，x 1=x 2 δ(x 1,x 2)=1 ，x 1≠x 24、用原语言程序证明每个原始递归函数都是可计算函数。

A 、证明初始函数是可计算的 S （X ）=X+1n(X)=0…………第四章 Post-Turing 程序和Turing 机1、P-T 程序（不改变指针位置） 数x 在带上的表示：x （01=，111=，31111=）f(x 1,x 2,...,x n )的初值在带上的表示：12...n x Bx B Bx （2，0，3）＝111B1B1111 结果：带上1的个数减1f(x)=P-T 部分可计算：若有一个P-T 程序计算函数f ，则称f 是P-T 部分可计算的。