07879離散數(shù)學(xué)-屈婉玲(形式語言與自動機(jī))114

1、111.4 圖靈機(jī)圖靈機(jī)n圖靈機(jī)的基本模型圖靈機(jī)的基本模型n圖靈機(jī)接受的語言圖靈機(jī)接受的語言 遞歸可枚舉語言遞歸可枚舉語言n用圖靈機(jī)計(jì)算函數(shù)用圖靈機(jī)計(jì)算函數(shù) 部分可計(jì)算函數(shù)與可計(jì)算函數(shù)部分可計(jì)算函數(shù)與可計(jì)算函數(shù) 2問題的提出問題的提出1900年年 D. Hilbert 在巴黎第二屆數(shù)學(xué)家大會上提出在巴黎第二屆數(shù)學(xué)家大會上提出著名的著名的23個(gè)問題個(gè)問題.第第10個(gè)問題個(gè)問題:如何判定整系數(shù)多項(xiàng)式是否有整數(shù)根如何判定整系數(shù)多項(xiàng)式是否有整數(shù)根? 要求使用要求使用“有限次運(yùn)算的過程有限次運(yùn)算的過程”1970 年證明不存在這樣的判定算法年證明不存在這樣的判定算法, 即這個(gè)問題是即這個(gè)問題是不可判定的不

2、可判定的, 或不可計(jì)算的或不可計(jì)算的.3計(jì)算模型計(jì)算模型從從20世紀(jì)世紀(jì)30年代先后提出年代先后提出圖靈機(jī)圖靈機(jī) A.M.Turing, 1936年年轉(zhuǎn)換演算轉(zhuǎn)換演算 A.Church, 1935年年遞歸函數(shù)遞歸函數(shù) K.Gdel, 1936年年正規(guī)算法正規(guī)算法 A.A.Markov, 1951年年無限寄存器機(jī)器無限寄存器機(jī)器 J.C.Shepherdson, 1963年年 4Church-Turing論題論題已經(jīng)證明這些模型都是等價(jià)的已經(jīng)證明這些模型都是等價(jià)的, 即它們計(jì)算即它們計(jì)算的函數(shù)類的函數(shù)類 (識別的語言類識別的語言類) 是相同的是相同的.Church-Turing論題論題: 直觀可

3、計(jì)算的函數(shù)類直觀可計(jì)算的函數(shù)類就是圖靈機(jī)以及任何與圖靈機(jī)等價(jià)的計(jì)算模就是圖靈機(jī)以及任何與圖靈機(jī)等價(jià)的計(jì)算模型可計(jì)算型可計(jì)算 (可定義可定義) 的函數(shù)類的函數(shù)類5圖靈機(jī)的基本模型圖靈機(jī)的基本模型定義定義 圖靈機(jī)圖靈機(jī)(TM) M= Q,q0,B,A , 其中其中 (1) 狀態(tài)集合狀態(tài)集合Q: 非空有窮集合非空有窮集合; (2) 輸入字母表輸入字母表: 非空有窮集合非空有窮集合; (3) 帶字母表帶字母表: 非空有窮集合且非空有窮集合且 ; (4) 初始狀態(tài)初始狀態(tài) q0 Q;控制器控制器6圖靈機(jī)的基本模型圖靈機(jī)的基本模型(續(xù)續(xù)) (5) 空白符空白符B -; (6) 接受狀態(tài)集接受狀態(tài)集A Q;

4、 (7) 動作函數(shù)動作函數(shù)是是Q 到到 L,R Q的部分函數(shù)的部分函數(shù), 即即dom Q .(q,s)=(s ,R,q )的含義的含義: 當(dāng)處于狀態(tài)當(dāng)處于狀態(tài)q, 讀寫頭掃視讀寫頭掃視符號符號s時(shí)時(shí), M的下一步把狀態(tài)轉(zhuǎn)移到的下一步把狀態(tài)轉(zhuǎn)移到q , 讀寫頭把這讀寫頭把這個(gè)個(gè)s改寫成改寫成s , 并向右移一格并向右移一格; (q,s)=(s ,L,q )的含義類似的含義類似, 只是讀寫頭向左移一只是讀寫頭向左移一格格; 若若(q,s)沒有定義沒有定義, 則則M停機(jī)停機(jī).7一個(gè)一個(gè)TM M的的實(shí)例實(shí)例（例（例1） 0 1 B q0 q1 q2*q3 (0,R,q0) (1,R,q0) (B,L,

5、q1) (B,L,q2) (1,R,q0) (B,R,q0) (B,L,q3) 8格局格局: 帶的內(nèi)容帶的內(nèi)容, 當(dāng)前的狀態(tài)和讀寫頭掃視的方格當(dāng)前的狀態(tài)和讀寫頭掃視的方格 = q, 其中其中 , *, q Q初始格局初始格局0= q0w, 其中其中w *是輸入字符串是輸入字符串接受格局接受格局 = q : q A停機(jī)格局停機(jī)格局 = qs : (q,s)沒有定義沒有定義1 2: 從從1經(jīng)過一步能夠到達(dá)經(jīng)過一步能夠到達(dá)2, 稱稱2是是1的的后繼后繼 1 2: 從從1經(jīng)過若干步能夠到達(dá)經(jīng)過若干步能夠到達(dá) 2圖靈機(jī)的計(jì)算圖靈機(jī)的計(jì)算9圖靈機(jī)的計(jì)算圖靈機(jī)的計(jì)算(續(xù)續(xù))計(jì)算計(jì)算: 一個(gè)有窮的或無窮的格局

6、序列一個(gè)有窮的或無窮的格局序列, 序列中的每一序列中的每一個(gè)格局都是前一個(gè)格局的后繼個(gè)格局都是前一個(gè)格局的后繼. w *, M從從0= q0w開始的計(jì)算有開始的計(jì)算有3種可能種可能:(1) 停機(jī)在接受格局停機(jī)在接受格局, 即計(jì)算為即計(jì)算為0,1, ,n, 其中其中n是是接受的停機(jī)格局接受的停機(jī)格局;(2) 停機(jī)在非接受格局停機(jī)在非接受格局, 即計(jì)算為即計(jì)算為0,1, ,n, 其中其中n是非接受的停機(jī)格局是非接受的停機(jī)格局;(3) 永不停機(jī)永不停機(jī), 即計(jì)算為即計(jì)算為0,1, ,n, 10圖靈機(jī)接受的語言圖靈機(jī)接受的語言定義定義 w *, 如果如果M從從0= q0w開始的計(jì)算停機(jī)在開始的計(jì)算停機(jī)

7、在接受格局接受格局, 則稱則稱M接受輸入串接受輸入串w. M接受的語言接受的語言L(M)是是M接受的所有輸入串接受的所有輸入串, 即即L(M)=w * | M接受接受w.例例1 (續(xù)續(xù)) M關(guān)于輸入關(guān)于輸入w=10100的計(jì)算的計(jì)算: q010100B 1q00100B 10q0100B 101q000B 1010q00B 10100q0B 1010q10B 101q20BB 101Bq3BB由于停機(jī)在接受格局由于停機(jī)在接受格局, 故故M接受接受10100. L(M)=w00 | w 0,1*11圖靈機(jī)圖靈機(jī)接受的語言接受的語言(續(xù)續(xù))定義定義 能被圖靈機(jī)接受的語言稱作能被圖靈機(jī)接受的語言稱作

8、遞歸可枚舉的遞歸可枚舉的, 記作記作r.e.定理定理 語言語言L是是r.e.當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) L是是 0 型語言型語言. 圖靈機(jī)與圖靈機(jī)與 0 型文法是等價(jià)的型文法是等價(jià)的12用圖靈機(jī)計(jì)算函數(shù)用圖靈機(jī)計(jì)算函數(shù)上的上的m元部分字函數(shù)元部分字函數(shù): (*)m的的某個(gè)子集到某個(gè)子集到*的部分函數(shù)的部分函數(shù)TM M計(jì)算的計(jì)算的m元部分字函數(shù)元部分字函數(shù)f : 設(shè)輸入字母表為設(shè)輸入字母表為, x1,xm *, 如果如果M從初始格局從初始格局0= q0 x1B xmB開始的計(jì)開始的計(jì)算停機(jī)算停機(jī)(不管是否停機(jī)在接受狀態(tài)不管是否停機(jī)在接受狀態(tài)), 從停機(jī)時(shí)帶的內(nèi)容中刪從停機(jī)時(shí)帶的內(nèi)容中刪去去以外的字符以外的

9、字符, 得到字符串得到字符串y, 則則 f(x1,x2,xm)=y; 如果如果M從從初始格局初始格局0開始的計(jì)算永不停機(jī)開始的計(jì)算永不停機(jī), 則則f(x1,x2,xm)沒有定義沒有定義,記作記作 f(x1, x2, , xm) . 否則否則若若若若,10, 100,)(wxwwxwxf例例1(續(xù)續(xù)) M計(jì)算函數(shù)計(jì)算函數(shù): x 0,1*,13數(shù)論函數(shù)數(shù)論函數(shù)數(shù)論函數(shù)數(shù)論函數(shù): 自然數(shù)集合自然數(shù)集合N上的函數(shù)上的函數(shù)N上的上的m元部分函數(shù)元部分函數(shù)N上的上的m元全函數(shù)元全函數(shù): 在在Nm的每一點(diǎn)都有定義的每一點(diǎn)都有定義 例如例如 x+y是全函數(shù)是全函數(shù), x-y是部分函數(shù)是部分函數(shù), 當(dāng)當(dāng)xy時(shí)時(shí)

10、, x-y 一進(jìn)制表示一進(jìn)制表示: 用用1x表示自然數(shù)表示自然數(shù)x 例如例如 111表示表示3, 空串空串表示表示0數(shù)論函數(shù)的一進(jìn)制表示數(shù)論函數(shù)的一進(jìn)制表示:字母表字母表1上的字函數(shù)上的字函數(shù), 用一進(jìn)制表示用一進(jìn)制表示自然數(shù)自然數(shù) 例如例如 x+y 可表成可表成 f(1x,1y)=1x+y14遞歸函數(shù)遞歸函數(shù)定義定義 設(shè)設(shè)f 是是N上的上的m元部分函數(shù)元部分函數(shù), 如果圖靈機(jī)如果圖靈機(jī)M計(jì)算計(jì)算f 的的一進(jìn)制表示一進(jìn)制表示, 即即M的輸入字母表為的輸入字母表為1, x1,xm N, 從初始格局從初始格局 0= 開始開始, 若若f(x1,xm) =y, 則則M的計(jì)算停機(jī)的計(jì)算停機(jī), 且停機(jī)時(shí)帶的內(nèi)容且停機(jī)時(shí)帶的內(nèi)容(不計(jì)不計(jì)1以以外的字符外的字符)為為1y; 若若f(x1, xm) , 則則M永不停機(jī)永不停機(jī), 那么那么稱稱M以一進(jìn)制方式計(jì)算以一進(jìn)制方式計(jì)算f.定義定義 圖靈機(jī)圖靈機(jī)M以一進(jìn)制方式計(jì)算的以一進(jìn)制方式計(jì)算的N上的上的m元部分函元部分函數(shù)稱作數(shù)稱作部分遞歸函數(shù)部分遞歸函數(shù), 或或部分可計(jì)算函數(shù)部分可計(jì)算函數(shù); 部分遞