可計(jì)算性與計(jì)算復(fù)雜性

1、可計(jì)算性與計(jì)算復(fù)雜性calculability & complexity目 錄i第二章第二章 可計(jì)算函數(shù)可計(jì)算函數(shù).11 1、原語(yǔ)言、原語(yǔ)言.12 2、可計(jì)算函數(shù)、可計(jì)算函數(shù).1第三章第三章 遞歸函數(shù)遞歸函數(shù).31 1、算子、算子.32 2、原始遞歸函數(shù)、原始遞歸函數(shù).33 3、原始遞歸謂詞、原始遞歸謂詞.34 4、受囿取極小、受囿取極小.45 5、遞歸與可計(jì)算性、遞歸與可計(jì)算性.5習(xí)習(xí) 題題 .6第四章第四章 post-turingpost-turing 程序和程序和 turingturing 機(jī)機(jī).81 1、p-tp-t 程序程序.82 2、turingturing 機(jī)機(jī).93 3

2、、p-tp-t 程序編碼程序編碼.104 4、一些定理、一些定理.10習(xí)習(xí) 題題 .11目 錄ii第五章第五章 半可計(jì)算性半可計(jì)算性.16習(xí)習(xí) 題題 .17第六章第六章 半圖厄系統(tǒng)半圖厄系統(tǒng).181 1、半圖厄系統(tǒng)、半圖厄系統(tǒng).182 2、半圖厄系統(tǒng)與圖靈機(jī)、半可計(jì)算集、半圖厄系統(tǒng)與圖靈機(jī)、半可計(jì)算集.183 3、不可判定問(wèn)題、不可判定問(wèn)題.18習(xí)習(xí) 題題 .19第七章第七章 圖靈機(jī)圖靈機(jī).26習(xí)習(xí) 題題 .26第八章第八章 計(jì)算復(fù)雜性理論計(jì)算復(fù)雜性理論 .27習(xí)習(xí) 題題 .28歷歷 年年 真真 題題 .29 第 1 頁(yè)第二章 可計(jì)算函數(shù)1、原語(yǔ)言本書所有變?cè)獮榉秦?fù)整數(shù)五條基本指令： x=x+

3、1 x=x-1 (x=0，結(jié)果仍為 0） to a if x0 to a y=x宏指令：y=x1+x2 y=x1x2 2、可計(jì)算函數(shù)部分可計(jì)算函數(shù)：若有一程序 p，使得(x1,x2,.,xn)=f(x1,x2,.,xn)，則稱 f(x1,x2,.,xn)為部分可計(jì)p算函數(shù)。這里“=”表示：或者兩邊都無(wú)定義，或者兩邊都有定義并且值相同?？捎?jì)算函數(shù)：若 f(x1,x2,.,xn)是部分可計(jì)算的而且是全函數(shù)，則稱 f(x1,x2,.,xn)為可計(jì)算函數(shù)。兩個(gè)常用函數(shù) x1x2 ，x1x2 x1x2 ，x1x2x1 x2 = x1 x2 = 無(wú)定義 ，x1x2 0 ，x1x2b to a if x20

4、 to ea x2=x2-1 y=yx1 to b約定： 輸入變?cè)簒0,x1, 臨時(shí)變?cè)簔0,z1, 輸出變?cè)簓 初始時(shí)，一切變?cè)獮?0（輸入變?cè)猓?轉(zhuǎn)向無(wú)定義標(biāo)號(hào)或執(zhí)行了最后一條指令時(shí)，停機(jī)y= x1b to a if x20 to ea x2=x2-1 y=y1 to b 第 2 頁(yè)習(xí) 題用原語(yǔ)言證明下列函數(shù)是可計(jì)算函數(shù)（顯然均為全函數(shù)，故只需證明存在 n 元程序 p，使得(x1,x2,.,xn)=f(x1,x2,.,xn)即可）p（1） （2）f(x1,x2)=minx1,x22121(,)xf xxx（3）f(x)=( x 3) （4）f(x)= x1 x2（5）（ 為向下取

5、整） （6）()f xx2()log (1)f xxy=y+1b to a if x20 to ea x2=x2-1 y=yx1 /宏指令 to bx=x-1x=x-1x=x-1to e if x0y=y+1c to a if x20 y= x1to ea to b if x10 y= x1 to eb x1=x1-1 x2=x2-1 to c/ t2x(t+1)2 b z1=z0 z1=z1z1 /宏指令 z1=z1-1 z1=x z1 /宏指令 to a if z10 y=z01 to ea z0=z01 to b/ 2tx2t+1 x=x+1b z1=z0 /宏指令1z1z =2 z1=

6、z1-1 z1=x z1 /宏指令 to a if z10 y=z01 to ea z0=z01 to bc to a if x10 to ea to b if x20 to eb x1=x1-1 x2=x2-1 y=y+1 to c 第 3 頁(yè)第三章 遞歸函數(shù)1、算子復(fù)合算子：設(shè)一個(gè)函數(shù) y=f(z1,z2,.,zm)，和一組函數(shù)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ù)合算子作用于函數(shù)

7、 f 和 g1,g2,.,gm的結(jié)果。遞歸算子：設(shè) m(x1,x2,.,xn)和 (x1,x2,.xn+2)是全函數(shù)，定義 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 是遞歸算子作用于函數(shù) m 和 的結(jié)果。 （h 是全函數(shù)）取極小算子：設(shè) f(x1,x2,.,xn,z)是全函數(shù)，定義 h(x1,x2,.,xn)= minz|f(x1,x2,.,xn,z)=0稱 h 是取極小算子 z 作用于函數(shù) f 的結(jié)果。 （h 不一定是全函數(shù)，若 f 為正則函數(shù)，則 h 為全函數(shù)）2、原

8、始遞歸函數(shù)原始遞歸函數(shù)：由初始函數(shù) s(x)=x+1、n(x)=0、 (1in)出發(fā)，12( ,.,)ninix xxx只用復(fù)合和遞歸算子得到的函數(shù)稱為原始遞歸函數(shù)。（它們都是全函數(shù)）原始遞歸函數(shù)add(x,y)mul(x,y)fac(x)=x!exp(x,y)=xy|x-y|sub(x,y)=x yp(x)p(0)=0p(x+1)=x 1 ,x0(x)= 0 ,x0 0 ,x=y d(x,y)=1 ,xy3、原始遞歸謂詞 0 ，當(dāng) p(x1,x2,.,xn)特征函數(shù)：設(shè)謂詞 p(x1,x2,.,xn)，定義函數(shù) (x1,x2,.,xn)= 1 ，當(dāng)p(x1,x2,.,xn)稱 為謂詞 p 的

9、特征函數(shù)。 0 ，當(dāng)(x1,x2,.,xn)s(x1,x2,.,xn)= ， 稱 為集合 s 的特征函數(shù)。 1，當(dāng)(x1,x2,.,xn)s 第 4 頁(yè)原始遞歸謂詞（集合）：謂詞 p（集合 s）的特征函數(shù)是原始遞歸函數(shù)?？捎?jì)算謂詞（集合）：謂詞 p（集合 s）的特征函數(shù)是可計(jì)算的。謂詞的受囿全稱量詞：12120()( ,.,)( ,.,)1yynnttp t x xxp t x xx謂詞的受囿存在量詞：12120()( ,.,)( ,.,)0yynnttp t x xxp t x xx定理：f(x1,x2,.,xn,y)是原始遞歸函數(shù)，則和是原始遞歸函數(shù)。120/1( ,., )ytf x x

10、t120/1( ,., )ytf x xt定理：p、q 是原始遞歸謂詞，則p 、是原始遞歸謂詞。pqpq定理：r、s 是原始遞歸集合，則、是原始遞歸集合。rrsrs定理：p 是原始遞歸謂詞，g 和 h 是原始遞歸函數(shù)，則 g(x1,x2,.,xn) ，當(dāng) p(x1,x2,.,xn)f(x1,x2,.,xn)= 是原始遞歸函數(shù)。 h(x1,x2,.,xn) ，當(dāng)p(x1,x2,.,xn)定理：p(x1,x2,.,xn)是原始遞歸謂詞，h1,h2,hn是原始遞歸函數(shù)，則 p(h1,h2,.,hn)是原始遞歸謂詞。定理：f 和 g 是原始遞歸函數(shù)，則 f=g 是原始遞歸謂詞。定理：若 p(t,x1,

11、x2,.,xn)是原始遞歸謂詞，則和是原始遞歸謂詞。12n()p(t,x ,x ,.,x )yt12n()p(t,x ,x ,.,x )yt4、受囿取極小受囿取極?。涸O(shè) p(t,x1,x2,.,xn)是一個(gè)謂詞，定義函數(shù)mint | p(t,x1,x2,.,xn) =1 ，若12n()p(t,x ,x ,.,x )yt =12min( ,.,)nt yp t x xx0 ，否則 稱為受囿取極小。mint y定理：若 p(t,x1,x2,.,xn)是原始遞歸謂詞，則函數(shù) f(y,x1,x2,.,xn)=是原始遞歸函12min( ,.,)nt yp t x xx數(shù)。原始遞歸謂詞x=yxyxy 第

12、5 頁(yè)y|xgn(x) 在 x 因式分解中沒(méi)有 0 指數(shù)prim(x) x 是素?cái)?shù)原始遞歸函數(shù)x/ypi 第 i 個(gè)素?cái)?shù)r(x,y) x 除以 y 的余數(shù)t(x) x 因式分解中非 0 指數(shù)的個(gè)數(shù)(x)i x 因式分解中 pi的指數(shù)lt(x) x 因式分解中第 lt(x)個(gè)以后指數(shù)均為 0 歌德爾數(shù)12naaa12n12na ,a ,.,a =pp. p x*yx=a1,a2,an y=b1,b2,bm x*y=a1,a2,an,b1,b1,b2,bm#(a,x) x 因式分解中指數(shù)為 a 的有幾個(gè)配對(duì)函數(shù)=(x+y)(x+y+1)+y ，l(z) ,r(z)12l()=x r()=y =z

13、l(z),r(z)z5、遞歸與可計(jì)算性 部分遞歸函數(shù)：由初始函數(shù) s(x)=x+1，n(x)=0， (1in) 出發(fā)，用復(fù)合、遞歸12( ,.,)ninix xxx和取極小算子得到的函數(shù)稱為部分遞歸函數(shù)。遞歸函數(shù)：由初始函數(shù) s(x)=x+1，n(x)=0， (1in) 出發(fā)，用復(fù)合、遞歸和對(duì)12( ,.,)ninix xxx正則函數(shù)取極小算子得到的函數(shù)稱為遞歸函數(shù)。原始遞歸（全函數(shù)）遞歸（全函數(shù)）部分遞歸（部分函數(shù)）可計(jì)算遞歸部分可計(jì)算部分遞歸習(xí) 題1、證明下列函數(shù)是原始遞歸函數(shù)（1）y 個(gè) xxf(x,y)=xxf(x,y)可遞歸定義如下： f(x,0)=1 f(x,y+1)=exp(x,

14、f(x,y) 第 6 頁(yè)exp(x,y)為原始遞歸函數(shù)，f(x,y)為原始遞歸函數(shù)。（2）yf(x,y)= x設(shè)=t，則 tyx(t+1)y y x=(t+1)yxy xmint xxy是原始遞歸函數(shù)，xy 是原始遞歸謂詞，(t+1)yx 是原始遞歸謂詞，f(x,y)是原始遞歸函數(shù)。（3）2( )logf xx設(shè)=t，則 2tx2t+1 2logx =2t+1x2logxmint xf(x)是原始遞歸函數(shù)。（4）f(x)表示 x 各位數(shù)字之和設(shè) x 為 n 位數(shù)，n=+12logx110( ) ( ,10)( ,10 ) 10niiiif xr xr xf(x)是原始遞歸函數(shù)。（5）設(shè) an=

15、f(n), bn=g(n)都是遞增的原始遞歸函數(shù)，將 an，bn（n0，1，2，）混合在一起，再?gòu)男〉酱笈帕械玫胶瘮?shù) cn=(n)，證明 (n)是原始遞歸函數(shù)。(n)遞歸定義如下：(0)=mina0,b0(n+1)= max,min() ()() ()( )nnninjta bitajtbtn 0000000000mina ,b = a(sub(a ,b ) + b(sub(b ,a ) d(a ,b )nnnnnnnnnnmaxa ,b = b(sub(a ,b ) + a(sub(b ,a ) d(a ,b )mina0,b0，maxan,bn是原始遞歸函數(shù)，(n)是原始遞歸函數(shù)。（6）將

16、任意兩個(gè)素?cái)?shù)乘積按從小到大排成一個(gè)序列，令這個(gè)序列通項(xiàng)即第 n 項(xiàng)為 f(n)，證明 f(n)是原始遞歸函數(shù)。f(n)可遞歸定義如下：f(1)=4 ;2*2 f(n+1)= 2min() () ()( )nnnijt pijtp ptf n f(n)是原始遞歸函數(shù)。 第 7 頁(yè)（7）稱三邊均為整數(shù)的直角三角形的斜邊為勾股數(shù)，將它們從小到大排列，第 n 個(gè)勾股數(shù)記作 r(n)，證明 r(n)是原始遞歸函數(shù)。r(n)可遞歸定義如下：r(1)=5 r(n+1)=222222( )( )( )min ()()()( )rnrnt rnijijttr nr(n)是原始遞歸函數(shù)。2、計(jì)算 3*2？3=20

17、310,1，2211，3*20,1,1203151153、用原語(yǔ)言程序（限用五條基本指令）計(jì)算謂詞“x1=x2”的特征函數(shù)。 0 ，x1=x2(x1,x2)= 1，x1x24、用原語(yǔ)言程序證明每個(gè)原始遞歸函數(shù)都是可計(jì)算函數(shù)。a、證明初始函數(shù)是可計(jì)算的 s（x）=x+1 n(x)=0(1,2,)= c to a if x10 to d if x20 to ed y=y+1 to ea to b if x20 to db x1=x1-1 x2=x2-1 to cx=x+1 x=x+1y=x y=0 1= 1+ 1 2= 2+ 1 1= 1+ 1 = + 1= + 1= + 1 第 8 頁(yè)第四章 p

18、ost-turing 程序和 turing 機(jī)1、p-t 程序雙向無(wú)窮帶 符號(hào)：b 和 1指令：right left write 1 write b to a if b to a if 1 （不改變指針位置）數(shù) x 在帶上的表示： （，）x0111131111f(x1,x2,.,xn)的初值在帶上的表示： （2，0，3）111b1b111112.nx bx b bx結(jié)果：帶上 1 的個(gè)數(shù)減 1x 2 （x1） f(x)= x+2 （x1） p-t 部分可計(jì)算：若有一個(gè) p-t 程序計(jì)算函數(shù) f，則稱 f 是 p-t 部分可計(jì)算的。p-t 可計(jì)算：若函數(shù) f 是 p-t 部分可計(jì)算的而且是全函數(shù)

19、，則稱 f 是 p-t 可計(jì)算的。廣義 p-t 機(jī)字母表：s0,s1,.,sk 約定 s0b,s1=1指令：right left write si i=0,1,.,kto a if si （不改變指針位置）字母表編碼：s01，s12，.，skk+1帶上符號(hào)串編碼：s2s3s0s1s23,4,1,2,3=23345172113tape(x)=2,2,.,2=，的歌德爾數(shù)編碼。121()xiipxtapen(x1,x2,.,xn)=tape(x1)*2*tape(x2)*2*.*2*tape(xn)，的歌德爾數(shù)編碼。12.nx bx b bx right to e if ba right to a

20、 if 1 left write b /消去最后一個(gè) 1right right to a if 1 write 1 right write 1 to e if 1a left write b left write b /消去最左邊兩個(gè) 1(部分)可計(jì)算p-t(部分)可計(jì)算廣義 p-t(部分)可計(jì)算 第 9 頁(yè)2、turing 機(jī)字母表=s0,s1,.,sk 狀態(tài)集 q=q1(初始),q2,.,qn四元組：qi sj sk ql 當(dāng)前狀態(tài) qi，當(dāng)前指針指向 sj，把 sk寫入當(dāng)前格，轉(zhuǎn)入狀態(tài) ql qi sj l ql 當(dāng)前狀態(tài) qi，當(dāng)前指針指向 sj，指針左移一格，轉(zhuǎn)入狀態(tài) ql qi s

21、j r ql 當(dāng)前狀態(tài) qi，當(dāng)前指針指向 sj，指針右移一格，轉(zhuǎn)入狀態(tài) qlf(x)=2x字母表=1,b,a,b狀態(tài)集 q=q1,q2,q3,q4,q5,q6,q7,q8,qx3 為例：q1 1 a q2 q2 a r q2 q2 1 r q2 q2 b b q3 q2 b r q2 q3 b l q3 q3 1 l q4 q3 a l q5 q4 1 l q4 q4 a r q1 q5 a l q5 q5 b r q6 q6 a 1 q7 q6 b 1 q7 q6 b l q8 q7 1 r q6 q8 1 b q 五元組：qi sj sk l ql 當(dāng)前狀態(tài) qi，當(dāng)前指針指向 sj，把

22、 sk寫入當(dāng)前格，左移指針一格，轉(zhuǎn)入狀態(tài) ql qi sj sk r ql 當(dāng)前狀態(tài) qi，當(dāng)前指針指向 sj，把 sk寫入當(dāng)前格，右移指針一格，轉(zhuǎn)入狀態(tài) qlturing 部分可計(jì)算：若有一個(gè) turing 機(jī)計(jì)算函數(shù) f，則稱 f 為 turing 部分可計(jì)算的。turing 可計(jì)算：若函數(shù) f 是 turing 部分可計(jì)算的而且是全函數(shù)，則稱 f 為 turing 可計(jì)算的。相同字母表，四元組 turing 可計(jì)算五元組 turing 可計(jì)算p-t 可計(jì)算a111bbbbaa11bbbbaaa1bbbbaaaabbbba111bbbbaa11bbbbaaa1bbbbaaaabbbb111

23、111111111111b算法：原來(lái)的 1 用 a 表示，復(fù)制的 1 用 b 表示 最后統(tǒng)一改為 1 再消去一個(gè) 1q1：把 1 改寫為 aq2：改寫 a 后，右移至尾，寫 bq3：寫 b 后，左移至遇到 1 或 aq4：遇到 1 后，左移至遇到 aq5：遇到 a 后，左移至頭q6：把 a、b 改寫為 1q7：改寫 1 后，右移q8：消去一個(gè) 1q：終止 第 10 頁(yè)3、p-t 程序編碼指令編碼rightleftwrite 1write bto ai if 1to ai if b12342i42i3指令標(biāo)號(hào)代碼無(wú)標(biāo)號(hào)指令代碼指令代碼a2 rightto a1 if bto a2 if 1a1

24、write 1rightwrite 1200100158313=7=20=44=13=2=9程序的編碼7,20,44,13,2,9=27320544713112139任意 p-t 程序?qū)?yīng)一正整數(shù)，任意正整數(shù)不能對(duì)應(yīng) p-t 程序。4、一些定理通用程序：用原語(yǔ)言寫的一個(gè)特殊程序，它有兩個(gè)輸入變?cè)?z、x。p 是編碼為 z 的 p-t 程序，p 對(duì)帶上的停機(jī)，當(dāng)且僅當(dāng)通用程序?qū)?z 和 x 停機(jī)，同時(shí)計(jì)算結(jié)果一致。x：( )12( ,.,)nnz xxx若 z 是某 p-t 程序 p 的歌德爾數(shù)，并且程序 p 計(jì)算部分函數(shù) g(x1,x2,.,xn)，則 = g(x1,x2,.,xn);( )1

25、2( ,.,)nnz xxx若 z 不是任何 p-t 程序的歌德爾數(shù)，或者 g 對(duì) x1,x2,.,xn無(wú)定義，則 對(duì) z, x1,x2,.,xn無(wú)定義。( )12( ,.,)nnz xxx枚舉定理：對(duì)每個(gè) n，部分函數(shù)是部分可計(jì)算函數(shù)。( )12( ,.,)nnz xxx 對(duì)任何部分可計(jì)算函數(shù) g(x1,.xn)，都有 z 使其等于。( )12( ,.,)nnz xxx計(jì)步謂詞：prog(z)，并且編碼為 z 的 p-t 程序?qū)τ谳斎?x1,x2,.,xn( )12( ,.,)nnstpz xxx在m 步內(nèi)停機(jī)。 prog(x)：x 是某 p-t 程序的歌德爾數(shù)，取 1；否則取 0。計(jì)步定理

26、：對(duì)于任意 n，謂詞 是可計(jì)算的。( )12( ,.,)nnstpz xxx迭代定理：對(duì)于一切 n，有原始遞歸函數(shù)使得對(duì)一切 m，( )12( ,.,)nnsz xxx()121( ,.,.,)n mnmz xxx vv()( )121( ,.,),.,)mnnmsz xxxvv習(xí) 題 第 11 頁(yè)用四元組 turing 機(jī)計(jì)算（先寫算法）（1）f(x)=x+x/2字母表=1,b,a,b 狀態(tài)集 q=q1,q2,q3,q4,q5,q6,q7,q算法： 消去一個(gè) 1 從第一個(gè) 1 開始，第奇數(shù)個(gè) 1 不變，第偶數(shù)個(gè) 1 改寫為 a，同時(shí)在尾部寫上一個(gè) b，直到掃描一遍 將 a 和 b 改寫為 1

27、，再加上一個(gè) 1q1 1 b q1q1 b r q2 消去一個(gè) 1q2 1 r q3 第奇數(shù)個(gè) 1 不變q3 1 a q3 第偶數(shù)個(gè) 1 改寫為 aq3 a r q4 q4 1 r q4 指針右移過(guò)程q4 b r q4 q4 b b q5 尾部寫上一個(gè) bq5 b l q5 q5 1 l q5 指針左移過(guò)程q5 a r q2 q2 b l q6q3 b l q6q6 1 l q6 掃描完畢，指針移到最左端q6 a l q6q6 b r q7q7 1 r q7q7 a 1 q7q7 b 1 q7 將 a 和 b 改寫為 1，再加上一個(gè) 1q7 b 1 qq2 b 1 q x=0 情況q3 b 1

28、 q x=1 情況（2）x=0 變化情況：b 1 bb b bb b 1x=1 變化情況：b 1 1 bb b 1 bb b 1 1 bx=4 變化情況：b 1 1 1 1 1 bb b 1 1 1 1 bb b 1 a 1 a b b bb b 1 1 1 1 1 1 1 bx=5 變化情況：b 1 1 1 1 1 1 bb b 1 1 1 1 1 bb b 1 a 1 a 1 b b bb b 1 1 1 1 1 1 1 1 b 第 12 頁(yè)字母表=1,b,b 狀態(tài)集 q=q0,q0,q0,q1,q2,q2,q3,q4,q5,q6,q算法： x 段加 1，x 與 y 之間的 b 改為 b

29、把 x 段最左端 1 改成 b，同時(shí)把 y 最左端 1 改成 b，轉(zhuǎn) 重復(fù)，直到出現(xiàn)下面的情況如果 y 中的 1 全被改成 b，則 xy，將全部 b 改為 b，x 段剩下的 1 為所求結(jié)果 如果 x 中的 1 全被改成 b，則 xy，不停機(jī)q0 1 l q0 q0 b 1 q0 x 段加 1q0 1 r q0 q0 b b q1 x 與 y 之間的 b 改為 bq1 b l q1q1 1 l q1 指針左移過(guò)程q1 b r q2 q2 1 b q3 x 段最左端 1 改成 bq2 b r q2q2 b l q2 x 中的 1 全被改成 b，不停機(jī)q3 b r q3q3 1 r q3q3 b r

30、 q4 指針右移過(guò)程q4 b r q4q4 1 b q1 把 y 最左端 1 改成 bq4 b l q5 y 中的 1 全被改成 bq5 b b q6q6 b l q5 將全部 b 改為 b，停機(jī)q5 1 r q（3）f(x)= x/y字母表=1,b,a,b,c,d 狀態(tài)集 q=q0,q0,q0, q0*,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q算法： 帶上 y 在左，x 在右，去掉 y 段第一個(gè) 1 和 x 段最后一個(gè) 1，并把 x、y 分界改為 b 第 13 頁(yè) 在最左端寫一個(gè) c，把 y 段的 1 逐一改為 a，同時(shí)把 x 段的 1 逐一改為 d

31、如果 y 掃描完畢，把 a 全部改為 1，轉(zhuǎn)如果 x 掃描完畢，轉(zhuǎn) 把帶上 a、1、b、d 改為 b，c 改為 1q0 1 b q0 去掉 y 段第一個(gè) 1q0 b r q0 q0 1 r q1 q0 b l q0* q0* b r q0 y=0，不停機(jī)q1 1 r q1q1 b b q2 x、y 分界改為 bq2 b r q2 q2 1 r q2q2 b l q3q3 1 b q4 去掉 x 段最后一個(gè) 1q4 b l q5q5 1 l q5q5 b l q5q5 b c q6 在最左端寫一個(gè) cq6 c r q6 q6 1 a q7 把 y 段的 1 改為 aq7 a r q7q7 1 r

32、 q7q7 b r q8 指針右移過(guò)程q8 d r q8 把 y 段的 1 逐一改為 a，同時(shí)把 x 段的 1 逐一改為 d q8 1 d q9 把 x 段的 1 改為 dq9 d l q9q9 b l q9q9 1 l q9 指針左移過(guò)程q9 a r q6q6 b l q5q5 a 1 q5 y 掃描完畢，把 a 全部改為 1q5 c l q5 q8 b l q10q10 d b q11q10 b b q11q10 1 b q11q10 a b q11 x 掃描完畢，把帶上 a、1、b、d 改為 b，c 改為 1q11 b l q10q10 c 1 q12q12 1 l q10q10 b r

33、 q（4）f(x)= log2x字母表=1,b,a,b,c 狀態(tài)集 q=q1,q2,q3,q4,q4,q5,q6,q7,q 第 14 頁(yè)算法：十進(jìn)制數(shù) x 的二進(jìn)制位數(shù)為log2x+1用 a、b 分別表示二進(jìn)制的 0 和 1，在左端從 0 開始，做加 1 的二進(jìn)制加法，高位在右，低位在左每做一次二進(jìn)制加法，就用一個(gè) c 替換一個(gè) 1當(dāng)所有 1 被 c 替換時(shí)，帶上 a 和 b 的總數(shù)就是log2x+1，最后把 c 改為 b，把 a 和 b 改為 1q1 1 a q4 寫 a，開始右移q4 a r q4q4 b r q4 q4 c r q4 右移至 1 改為 c，開始左移q4 1 c q2 q4

34、 b l q4q4 a r q4 x=0，不停機(jī)q2 c l q2 q2 b l q2q2 a l q2 左移至最左端q2 b r q3q3 a b q4 最低位為 0，則改為 1q3 b a q5 最低位為 1，則向右進(jìn)位q5 a r q3q3 c b q4 q4 b l q6q6 c b q7q7 b l q6q6 b 1 q6 c 改為 b，a 和 b 改為 1 q6 a 1 q6q6 1 l q6q6 b r q（5）f(x)= log3(1+x)字母表=1,b,a,b,c,d 狀態(tài)集 q=q0,q1,q2,q3,q3,q4,q5,q6,q7,q8,q9,q 第 15 頁(yè)算法：類似（4

35、） ，用 a、b、c 分別表示三進(jìn)制的 0、1 和 2q0 1 l q1q1 b 1 q2 加 1，寫 a，開始右移 q2 1 a q3 q3 a r q3q3 b r q3q3 c r q3 右移至 1 改為 d，開始左移 q3 d r q3 q3 1 d q4 q3 b l q3q3 a r q3 x=0，不停機(jī)q4 d l q4 q4 c l q4q4 b l q4 左移至最左端q4 a l q4q4 b r q5q5 a b q3 最低位為 0，則改為 1q5 b c q3 最低位為 1，則改為 2q5 c a q6 最低位為 2，則向右進(jìn)位q6 a r q5 q5 d b q3q3

36、b l q8q8 d b q9q9 b l q8q8 c 1 q8 d 改為 b，a、b、c 改為 1 q8 b 1 q8q8 a 1 q8q8 1 l q8q8 b r q3、用五元組 turing 機(jī)計(jì)算謂詞 p(x, y)(3x=2y)的特征函數(shù)。 0 ，x/2=y/3(x,y)= 1 ，否則算法： 把 x 前的 b 改為 a，y 后的 b 改為 b 從 x 和 y 中間的 b 開始掃描，每當(dāng) x 減去兩個(gè) 1，y 減去三個(gè) 1，轉(zhuǎn) 重復(fù)，直到下面情況 如果某次掃描 x 后遇到 a 且掃描 y 后遇到 b，在帶上寫一個(gè) 1；否則，在帶上寫兩個(gè) 1 第 16 頁(yè)第五章 半可計(jì)算性f(x1,

37、x2,.,xn)：f 對(duì)(x1,x2,.,xn)有定義。 f(x1,x2,.,xn)：f 對(duì)(x1,x2,.,xn)無(wú)定義。半可計(jì)算謂詞：對(duì)于謂詞 p (x1,x2,.,xn)，如果存在一個(gè)部分可計(jì)算函數(shù) g (x1,x2,.,xn)，使得p(x1,x2,.,xn)g (x1,x2,.,xn)，則稱 p 為半可計(jì)算謂詞。半可計(jì)算集合：對(duì)于集合 s，如果存在一個(gè)部分可計(jì)算函數(shù) g (x1,x2,.,xn)，使得(x1,x2,.,xn)sg (x1,x2,.,xn)，則稱 s 為半可計(jì)算集合。 = x1,x2,.,xnx可判定謂詞：對(duì)于謂詞 p()，如果存在一個(gè)算法 a，使得對(duì)任給xx 能在有限步

38、內(nèi)回答 p(x)是否為真，則稱 p 為可判定謂詞。半可判定謂詞：對(duì)于謂詞 p()，如果存在一個(gè)算法 a，使得對(duì)任給xx 如果 p()為真，則在有限步內(nèi)回答是，否則不能給出回答，則稱 p 為半可判定謂詞。x遞歸集合：對(duì)于集合 s，如果存在一個(gè)算法 a，使得對(duì)任給x 能在有限步內(nèi)回答是否s，則稱 s 為遞歸集合。x遞歸可枚舉集合：對(duì)于集合 s，如果存在一個(gè)算法 a，使得對(duì)任給x如果s，則在有限步內(nèi)回答是，否則不能給出回答，則稱 s 為遞歸可枚舉集合。x謂詞的可計(jì)算性可判定性，半可計(jì)算性半可判定性集合的可計(jì)算性遞歸性，半可計(jì)算性遞歸可枚舉性定理：若謂詞 p 和 q 是半可計(jì)算的，則、是半可計(jì)算的。p

39、qpq 若集合 s1和 s2是半可計(jì)算的，則、是半可計(jì)算的。12ss12ss 若謂詞 h(v,)是半可計(jì)算的，則、是半可計(jì)算的。x()( ,)v h v x()( ,)zvh v x范式定理：h()是半可計(jì)算謂詞，當(dāng)且僅當(dāng)存在可計(jì)算謂詞 c(y,)，使 h()(y)c(y,)。xxx xpost 定理：p()是可計(jì)算的，當(dāng)且僅當(dāng) p()和p()半可計(jì)算的。xxx一元謂詞 k(x)：k(x)。表示：k(x)為真，當(dāng)且僅當(dāng)歌德爾數(shù)為 x 的 p-t 程序?qū)?1)(,)x x入 x 停機(jī)。定理：k(x)是半可計(jì)算的，但不是可計(jì)算的。 推論：k(x)不是半可計(jì)算的。非半可計(jì)算半可計(jì)算可計(jì)算k(x)k

40、(x) 第 17 頁(yè)圖形定理：函數(shù) f(x1,x2,.,xn)部分可計(jì)算謂詞 v=f(x1,x2,.,xn)是半可計(jì)算的。集合 wz：使得歌德爾數(shù)為 z 的 p-t 程序停機(jī)的所有那些 x 的集合。習(xí) 題1. 舉出一種運(yùn)算，可計(jì)算謂詞對(duì)這個(gè)運(yùn)算是不封閉的（說(shuō)明理由）半可計(jì)算謂詞對(duì)這個(gè)運(yùn)算是封閉的（不必說(shuō)明理由） 。存在量詞運(yùn)算，對(duì)可計(jì)算謂詞不是封閉的。設(shè) c(y,)為可計(jì)算謂詞，對(duì)于(y)c(y,)逐次對(duì) y=0,1,2,.驗(yàn)證 c(y,)是否為真，xxx若存在 y，則過(guò)程可終止，否則不終止。故(y)c(y,)是半可計(jì)算的。x存在量詞運(yùn)算，對(duì)半可計(jì)算謂詞是封閉的。有定理：若謂詞 h(v,)是半

41、可計(jì)算的，則是半可計(jì)算的。x()( ,)v h v x2. 舉出一個(gè)不可計(jì)算的全函數(shù)。 1 ，若 k(x)f(x)= 其中一元謂詞 k(x)(1)(,)x x 0 ，若k(x) 第 18 頁(yè)第六章 半圖厄系統(tǒng)1、半圖厄系統(tǒng)字母表 d=a,b產(chǎn)生式集 abaaababba 半圖厄處理 .abaaaaa 一步推導(dǎo)abaabbaaaaba 多步推導(dǎo)，記 abaaaaba、abaaaaba* 是半圖厄處理，若 ab 在 中，則 ba 在 中，稱 為圖厄處理。（半）圖厄系統(tǒng)：（半）圖厄處理加上一個(gè)公理或初始字，記 =(p,a)。公理 a 可推出的符號(hào) w 稱為定理。2、半圖厄系統(tǒng)與圖靈機(jī)、半可計(jì)算集po

42、st 字：圖靈機(jī)帶上字符為 s1s2s3s4，指針指向 s3且狀態(tài)為 q，則稱 hs1s2qs3s4h 為波斯特字。(m)：半圖厄處理，(m)：(m)的逆m 對(duì) x 停機(jī)，當(dāng)且僅當(dāng) hq1hhqh。 m 對(duì) x 停機(jī)，當(dāng)且僅當(dāng) hqhhq1h。x*()m*()mx(m)：使 m 停機(jī)的所有 x 的集合。t()：=(p,a)所有定理的集合。n()=x| t()半圖厄系統(tǒng) 產(chǎn)生的整數(shù) x 的集合。xx定理：對(duì)任意圖靈機(jī) m，都有一個(gè)半圖厄系統(tǒng) ，使得 x(m) t()。x定理：對(duì)任意半可計(jì)算集 s，都有一個(gè)半圖厄系統(tǒng) ，使得 s= n()。3、不可判定問(wèn)題(1)turing 機(jī)停機(jī)問(wèn)題 i：對(duì)任給

43、的 turing 機(jī) m 和任給的輸入 x，判定 turing 機(jī) m 是否停機(jī)。(2)turing 機(jī)停機(jī)問(wèn)題 ii：對(duì)已給的 turing 機(jī) m 和任給的輸入 x，判定 turing 機(jī) m 是否停機(jī)。(3)半圖厄系統(tǒng)的字問(wèn)題：對(duì)已給的半圖厄系統(tǒng) ，判定對(duì)任給的兩個(gè)字 1和 2，是否有12。*(4)半圖厄系統(tǒng)的判定問(wèn)題：對(duì)已給的半圖厄系統(tǒng) ，判定對(duì)任給的一個(gè)字 是不是 的定理，即是否有 a。* (5)post 對(duì)應(yīng)問(wèn)題：對(duì)給定的對(duì)偶序列,判定是否存在序列1122(,),(,),.,(,)nn i1,i2,.,ip使，其中 1i1,i2,.,ipn。1212.ppiiiiii 第 19 頁(yè)

44、習(xí) 題1、給出半圖厄系統(tǒng) （先寫算法）(1)( ) |()(2 )nnxn x設(shè)公理為 a，半圖厄處理 p 為：aaa 用 n 次a1h aa.a1h (n 個(gè) a)a111a 11.1aa.ah (2n個(gè) 1,n 個(gè) a)ahh 消去 ah1 11.1 (2n+1 個(gè) 1)(2)3( ) |()(2 )nnxn x設(shè)公理為 a，半圖厄處理 p 為：a111 n=0aaa 用 n 次，n1abch aa.abch (n 個(gè) a)abbbba bb.baa.ach (3n個(gè) b,n 個(gè) a)ac1aa11a bb.b1aa.ah (3n個(gè) b,n 個(gè) a)b111b 11.1bb.baa.ah

45、(個(gè) 1,3n個(gè) b,n 個(gè) a)32nahh 消去 abhh 消去 bh1 11.1 (+1 個(gè) 1)32n(3)( ) |()(2 )nnxn xn設(shè)公理為 ah，半圖厄處理 p 為：ah1 n=0aaa1aa1 aa.a11.1h (n 個(gè) a, n 個(gè) 1)a111a 11.1aa.ah (n2n個(gè) 1,n 個(gè) a)ahh 消去 ah1 11.1 (n2n+1 個(gè) 1) 第 20 頁(yè)(4) ( ) |()(2)nnxn xn令=m，則 m2n(m+1)2=m2+2m+1，類似(3)構(gòu)造 c.c1.1（m 個(gè) c，n 個(gè) 1）n設(shè)公理為 hah，半圖厄處理 p 為：hah1 m=0aaa

46、baab ha.ab.bh（m 個(gè) a，m 個(gè) b，m1）acddccd hc.cd.db.bh（m 個(gè) c，m 個(gè) d，m 個(gè) b）dbb1dd11d dhh hc.cb.b1.1h（m 個(gè) c，m 個(gè) b，m2個(gè) 1）hcchhb11hhb1hhbhh11hhhh c.c1.1h（m 個(gè) c，n 個(gè) 1，m2nm2+2m）c111cchhch1(5)( ) |()()()nxnm xnm設(shè)公理為 hah，半圖厄處理 p 為：a1 n=0 或 m=0aabhahaa n 次，ha.abh(n 個(gè) a，1 個(gè) b)bhbbh m 次，ha.ab.bh（n 個(gè) a，m 個(gè) b）abb1a a11

47、a hb.b1.1a.ah（m 個(gè) b，nm 個(gè) 1，n 個(gè) a）hbhahhh11hhh1 第 21 頁(yè) (6) 4( ) |()(2)nnxn xn令=m，則 4mn4(m+1)=4m+4，設(shè)公理為 hach，半圖厄處理 p 為：4nhach1 m=0aaabaab ha.ab.bch（m 個(gè) a，m 個(gè) b，m1）haahhb1111hhc1hhc11hhc111hhch hhh a.a1.1h（m 個(gè) a，n 個(gè) 1，4mn4m+3）a111aahhah1(7)2( ) |()(log)nxn xnn令log2n=m，則 2mn2m+1=22m，類似(5)構(gòu)造 c.cb.b（n 個(gè) c

48、，m 個(gè) b）設(shè)公理為 hah，半圖厄處理 p 為：hah1 m=0aabcababb hab.bch（m 個(gè) b）bcccb hac.cb.bh（2m個(gè) c，m 個(gè) b）acccacaccccacacbcb hc.cb.bh（n 個(gè) c，m 個(gè) b，2mn22m-1）cbb1cc11c hb.b1.1c.ch（m 個(gè) b，nm 個(gè) 1，n 個(gè) c）hbhchhh11hhh1 第 22 頁(yè)(8) ( ) |()()()mnxnm xn設(shè)公理為 ha1a2ch，半圖厄處理 p 為：ha1a2ch1 （n=0，m=0 或 1）ha1a2ch11 （n=1，m=0 或 1）a1aa1a1a （n2，

49、m2）11.mnnha ab bc cha2ba2ca2bc abbdaacca 211.mnnnha ab bd d c chahhdbbddcceddeed 21(1).mnnn nha ab bc c e e hdhhcecc .221.mnnha ab bc ch1.mnnhb bc chhbhhc1hhh1 第 23 頁(yè)(9) ( ) |()( 2)2nnnxn x令=m，則 m2n(m+1)2=m2+2m+1n m22m 2n22m12設(shè)公理為 hach，半圖厄處理 p 為：aaab .mmha ab bchaab abbda 2.mmmhb bd d a achaddadde22

50、.mmmhb be ea achdaaacceacc 生成 0m 個(gè) e，2.mnhb bce eheccebcccbbeeb 22.mnhc ce ehbhhcee1cc11chehchhh11hhh1 第 24 頁(yè)2、設(shè) s 是所有能被 3 整除的二進(jìn)制數(shù)組成的集合，給出半圖厄系統(tǒng) ，使得。*( )0,1ts設(shè) x 為十進(jìn)制數(shù)，為其二進(jìn)制表示，并引入三個(gè)字符 a0,a1,a2x約定：字符串“a0”表示：x 被 3 整除x字符串“a1”表示：x 被 3 除，余 1x字符串“a2”表示：x 被 3 除，余 2x因?yàn)?2x，12x+1，所以有xx若a0，則0a0，1a1xxx若a1，則0a2，1

51、a0 xxx若a2，則0a1，1a2xxx設(shè)公理為 a，半圖厄處理 p 為：a0a0a1a1a00a0a01a1a10a2a11a0a20a1a21a20a00 /保證以 a0結(jié)尾，被 3 整除的偶數(shù)1a01 /保證以 a0結(jié)尾，被 3 整除的奇數(shù)改造 1：若 s 是所有能被 3 整除，并且是奇(偶)數(shù)的二進(jìn)制數(shù)組成的集合，去掉最后兩行相應(yīng)的某行。改造 2：若 s 是所有能被 3 整除，但不能被 4 整除的二進(jìn)制數(shù)組成的集合，最后兩位不能為 00，最后兩行改為1a01 /保留奇數(shù) 10a010 /保留以 10 結(jié)尾的改造 3：若要求其公理和所有產(chǎn)生式左端的字長(zhǎng)都為 1最后兩行改為 a00 /6

52、na11 /6n+3 第一行改為 a0十進(jìn)制二進(jìn)制03691215182124011110100111001111100101010111000 第 25 頁(yè)3、l=w|wa,b*，且 w 的任何字頭中的 0(a 的數(shù)目b 的數(shù)目)3 算法：用 ai(i=0,1,2,3)表示 ai左側(cè)字符中 a 的數(shù)目b 的數(shù)目設(shè)公理為 a0，半圖厄處理 p 為：a0aa1a1aa2a1ba0a2aa3a2ba1a3ba2a0aa1aa1ba2aa2ba3b 第 26 頁(yè)第七章 圖靈機(jī)0 , , , , ,mqq b f q：有窮狀態(tài)集：不含 b 的輸入符號(hào)集：帶上允許的有窮符號(hào)集， ：次動(dòng)作函數(shù)， , qq

53、l r q0：初始狀態(tài)，q0qb：空白符，bf：終結(jié)狀態(tài)集，fq語(yǔ)言 l 被 m 接受：l 放在 m 帶的左端，m 的帶頭(即指針)在最左單元上，l 使 m 進(jìn)入一個(gè)終結(jié)狀態(tài)。類型：?jiǎn)蜗驘o(wú)限單帶雙向無(wú)限單帶多帶：雙向無(wú)限多帶離線：多帶，輸入帶只讀.$定理：l 被雙向無(wú)限單帶 tm 接受l 被單向無(wú)限單帶 tm 接受l 被多帶 tm 接受l 被單帶 tm 接受習(xí) 題1、設(shè)語(yǔ)言，給出接受 l 的多帶 tm。r*l=wcw cw|w0,1 2、給出計(jì)算函數(shù) f(x)=log2log2x的多帶 tm。3、用多帶 tm 計(jì)算 xx。4、給出計(jì)算謂詞 7|x 特征函數(shù)的離線 tm。這里輸入帶上不是，而是

54、x 的二進(jìn)制表示，并且要求xm 的空間復(fù)雜度的階最小。（說(shuō)明：若，則稱 s1(n)的階小于 s2(n)的階，如上述極限為常數(shù)則階相等）12( )lim0( )ns ns n5、用多帶 tm（允許指針不動(dòng)） ，求 x1, x2的最大公約數(shù)。 （指出結(jié)果所在的帶）6、以作為輸入，在一條帶上（要指明哪條）給出結(jié)果，用多帶 tm 計(jì)算下面函數(shù)xy。2log xy=x-27、給出計(jì)算 x1, x2的最小公倍數(shù)的多帶 tm。8、用離線 tm 計(jì)算謂詞 prime(x)的特征函數(shù)，并使其空間復(fù)雜度最小，并計(jì)算出其空間復(fù)雜度。9、用多帶 tm 計(jì)算級(jí)數(shù) 1，2，4，7，11，的前 n 項(xiàng)和，并計(jì)算其時(shí)間復(fù)(1

55、)12n n 第 27 頁(yè)雜度。 第 28 頁(yè)第八章 計(jì)算復(fù)雜性理論空間復(fù)雜度：考慮離線 tm，有一條有端記號(hào)的只讀輸入帶和 k 條半無(wú)窮存貯帶。如果對(duì)于每個(gè)長(zhǎng)度為 n 的輸入字，m 在任意一條存貯帶上掃視，都不超過(guò) s(n)個(gè)單元，那么稱 m 為 s(n)空間有界圖靈機(jī)，或稱 m 具有空間復(fù)雜度 s(n)。稱被 m 識(shí)別的語(yǔ)言具有空間復(fù)雜度 s(n)。時(shí)間復(fù)雜度：考慮多帶 tm，有 k 條雙向無(wú)窮存貯帶。如果對(duì)于每個(gè)長(zhǎng)度為 n 的輸入字，m 在停機(jī)前最多做 t(n)個(gè)動(dòng)作，那么稱 m 為 t(n)時(shí)間有界圖靈機(jī)，或稱 m 具有時(shí)間復(fù)雜度 t(n)。稱被 m 識(shí)別的語(yǔ)言具有時(shí)間復(fù)雜度 t(n)

56、。復(fù)雜性類dspace(s(n)：具有空間復(fù)雜度 s(n)的語(yǔ)言族nspace(s(n)：具有非確定空間復(fù)雜度 s(n)的語(yǔ)言族dtime(t(n)：具有時(shí)間復(fù)雜度 t(n)的語(yǔ)言族ntime(t(n)：具有非確定時(shí)間復(fù)雜度 t(n)的語(yǔ)言族空間可構(gòu)造函數(shù)：如果有某個(gè)圖靈機(jī) m 是 s(n)空間有界的，且對(duì)每個(gè) n，都存在某個(gè)長(zhǎng)度為 n 的輸入，對(duì)于這個(gè)輸入，m 實(shí)際使用了 s(n)個(gè)單元，則稱 s(n)為空間可構(gòu)造函數(shù)。如果對(duì)于一切 n，m 對(duì)長(zhǎng)度為 n 的任何一個(gè)輸入，都實(shí)際使用了恰好 s(n)個(gè)單元，則稱 s(n) 為完全空間可構(gòu)造函數(shù)?？臻g譜系定理：如果 s2(n)是一個(gè)完全空間可構(gòu)造

57、函數(shù)，且，s1(n)和 s2(n)都至少是12( )0( )limns ns nlog2n，那么有一個(gè)語(yǔ)言，它在 dspace(s2(n)中，但不在 dspace(s1(n)中。時(shí)間可構(gòu)造函數(shù)：如果存在一個(gè) t(n)時(shí)間有界多帶圖靈機(jī) m，使得對(duì)于每個(gè) n，都存在某個(gè)輸入，對(duì)于這個(gè)輸入，m 實(shí)際做了 t(n)個(gè)動(dòng)作，則稱 t(n)為時(shí)間可構(gòu)造函數(shù)。如果對(duì)于一切長(zhǎng)度為 n 的輸入，都使用時(shí)間 t(n)，則稱 t(n)為完全時(shí)間可構(gòu)造函數(shù)。時(shí)間譜系定理：如果 t2(n)是一個(gè)完全時(shí)間可構(gòu)造函數(shù)，且，112( )log( )0( )limnt nt nt n那么有一個(gè)語(yǔ)言，它在 dtime(t2(n

58、)中，但不在 dtime(t1(n)中。復(fù)雜性量度關(guān)系(a)如果 l 在 dtime(f(n)中，那么 l 在 dspace(f(n)中。(b)如果 l 在 dspace(f(n)中，且 f(n)log2n，那么有某常數(shù) c(它依賴于 l)，使得 l 在 dtime(cf(n)中。(c)如果 l 在 ntime(f(n)中，那么有某常數(shù) c(它依賴于 l)，使得 l 在 dtime(cf(n)中。savitch 定理：如果 l 在 nspace(s(n)中，那么 l 在 dspace(s2(n)中。這里假定 s(n)是完全空間可構(gòu)造的，且 s(n)log2n。轉(zhuǎn)換引理：設(shè) s1(n)、s2(n

59、)和 f(n)是完全空間可構(gòu)造的，且 s2(n)n，f(n)n，那么 由 nspace(s1(n)nspace(s2(n)，可以推出 nspace(s1(f(n)nspace(s2(f(n) 第 29 頁(yè)習(xí) 題1、證明完全時(shí)間可構(gòu)造（1）2n（2）nlog2n（3）n2（4）(n+1)2 2、證明空間可構(gòu)造（1）n（2）（用離線圖靈機(jī)證明，只有一條存貯帶 輸入帶與存貯帶都是單道的 帶上的符3n 號(hào)除空格 b 外只有一個(gè)符號(hào)“1” ）3、證明是完全空間可構(gòu)造的。1x 4、證明，其中 k 為一常數(shù)。(2 )( 2 )knkndtimedtime n5、證明，其中 e 為大于零的任何實(shí)數(shù)（不必證明函

60、數(shù)的完全可構(gòu)1( )()edtime ndtime n造性） 。6、利用已知的復(fù)雜性度量間的關(guān)系，給出 nspace 和 ntime 之間的關(guān)系。 （給出關(guān)系并寫明條件，不必證明） 第 30 頁(yè)歷 年 真 題可計(jì)算性與計(jì)算復(fù)雜性（一）一、 （20 分）回答下列定義、定理1、部分可計(jì)算函數(shù)2、半可計(jì)算謂詞3、空間復(fù)雜度4、通用程序5、時(shí)間譜系定理二、 （10 分）寫出計(jì)算函數(shù) f(x)=log2(x+1)的原語(yǔ)言程序（可以使用學(xué)過(guò)的宏指令） 。三、 （10 分）證明函數(shù)22222.x個(gè)2是原始遞歸函數(shù)。四、 （20 分）設(shè)語(yǔ)言。給出接受 l 的多帶 tm。r*l=wcw cw|w0,1 五、 （20 分