計(jì)算理論與算法分析設(shè)計(jì)：13-TM

CH4圖靈機(jī)

4.1圖靈機(jī)的定義圖靈:計(jì)算通常是一個(gè)人拿著筆在紙上進(jìn)行的.

他根據(jù)

眼睛看到的紙上符號(hào),腦中的若干法則,

指示筆在紙上擦掉或?qū)懮弦恍┓?hào),

再改變他所看到的范圍.

繼續(xù),直到他認(rèn)為計(jì)算結(jié)束.腦:控制器紙:存儲(chǔ)帶眼睛和筆:讀寫頭法則:轉(zhuǎn)移函數(shù)24.1圖靈機(jī)的定義

圖靈機(jī)的基本模型如圖所示。一個(gè)有限狀態(tài)控制器，一個(gè)讀寫頭和一個(gè)輸入帶組成。其中輸入帶具有最左端，但右端可以無限伸長(zhǎng)。帶上的每一格恰好有一個(gè)字符。開始時(shí)，帶上最左邊的n個(gè)格存放著由有限輸入字母表上的字符組成的字符串，第n＋1格及其右邊各格均為空格符。34.1圖靈機(jī)的定義讀寫頭一次可以在帶上讀或?qū)懸粋€(gè)字符，并可根據(jù)指令向左或向右移一格。有限狀態(tài)控制器根據(jù)當(dāng)前的狀態(tài)，讀到輸入字符并發(fā)布指令：指令的內(nèi)容包括狀態(tài)轉(zhuǎn)換，在帶上的一格寫上(更換)字符，以及讀寫頭向左或向右移動(dòng)一格等。4與有限自動(dòng)機(jī)的區(qū)別有限自動(dòng)機(jī):

輸入帶長(zhǎng)度有限只能讀和右移,不能寫和左移讀完輸入停機(jī)54.1圖靈機(jī)的定義圖靈機(jī)TM是一個(gè)五元組M=(K,,δ,s,H)其中，K：是有窮狀態(tài)集；：是字母表

包括空格符_和左端符;不包含代表移動(dòng)的符號(hào)和；s

K：初始狀態(tài)；HK：停機(jī)狀態(tài)集，進(jìn)入任意停機(jī)狀態(tài)，則TM停止δ：轉(zhuǎn)換函數(shù)，從

(K－H)

到K((－{}){,})的函數(shù)，使得:(a)對(duì)所有q(K－H),若(q,)＝(p,b)則b＝(b)對(duì)所有q(K－H)且a,若(q,a)＝(p,b)則b

6TM操作(q,a)=(p,b)：若

b

，代表“將帶上的

a

改寫為

b，其它不變”(q,a)=(p,b)：若b=

，代表“向左移動(dòng)讀寫頭一格，其它不變”定義中，在同一步驟中，TM僅能移動(dòng)讀寫頭一格，或者改寫當(dāng)前位置的字符此規(guī)定不影響TM的表達(dá)能力，因?yàn)榭梢酝ㄟ^引入中間狀態(tài)將任意操作分解為寫操作和移動(dòng)操作兩個(gè)動(dòng)作4.1圖靈機(jī)的定義例4.1.1考慮TM:M=(K,,,

s,{h}),其中

K={q0,q1,h}

={a,,}

s=q0,

:q

(q,

)q0a(q1,)q0(h,

)q0(q0,)q1a(q0,a)q1(q0,)q1(q1,)4.1圖靈機(jī)的定義刪除非空格符例4.1.2TM向左掃描，遇到空格后停機(jī) K={q0,h}

={a,,}

s=q0,

:4.1圖靈機(jī)的定義機(jī)器進(jìn)入無限循環(huán)如果不存在空格TM

(K,,,

s,H)

的格局是成員：

K*(*(－{}){e})格局可表述為

(q,x,y)：4.1圖靈機(jī)的定義格局示例4.1圖靈機(jī)的定義格局示例4.1圖靈機(jī)的定義格局的簡(jiǎn)化描述：4.1圖靈機(jī)的定義定義4.1.3圖靈機(jī)的格局一步產(chǎn)生規(guī)則

13字符替換，位置不變4.1圖靈機(jī)的定義定義4.1.3圖靈機(jī)的格局一步產(chǎn)生規(guī)則

14位置左移，字符不變3.b=andw2=w1a1andeither: u1=a2u2,or u1=u2=e,anda2=4.1圖靈機(jī)的定義定義4.1.3圖靈機(jī)的格局一步產(chǎn)生規(guī)則

位置右移，字符不變4.1圖靈機(jī)的定義例4.1.3:定義4.1.3的舉例16

17例4.1.4:(q1,aaaa)├M

(q0,aaaa)

├M

(q1,aaa)├M

(q0,aaa)├M

(q1,aa)├M

(q0,aa)├M

(q1,a)├M

(q0,a)├M(q1,)├M(q0,)├M

(h,)q

(q,

)q0a(q1,)q0(h,)q0(q0,)q1a(q0,a)q1(q0,)q1(q1,)4.1圖靈機(jī)的定義4.1.1圖靈機(jī)的記號(hào):基本機(jī)器

寫a機(jī):a或者M(jìn)a

左移帶頭機(jī):M縮寫為L(zhǎng)

右移帶頭機(jī):M縮寫為R194.1.1圖靈機(jī)的記號(hào):組合機(jī)器把TM連接起來，組合成更復(fù)雜的TM單個(gè)機(jī)器如同F(xiàn)A前一臺(tái)TM停機(jī)后，從前一臺(tái)TM遷移到后一臺(tái)TM后一臺(tái)TM從初始狀態(tài)和前一臺(tái)機(jī)器留下的帶和帶頭位置上啟動(dòng)20組合機(jī)器的規(guī)則3臺(tái)機(jī)器的組合約定最左邊的機(jī)器總是初始機(jī)器21TM標(biāo)記例4.1.5兩個(gè)基本機(jī)器R的組合4.1.1圖靈機(jī)的記號(hào):組合機(jī)器組合機(jī)器的規(guī)則尋找右邊第一個(gè)空格23向右發(fā)現(xiàn)第一個(gè)非空字符，將此字符復(fù)制到其左方的相鄰方格2425組合機(jī)器的規(guī)則復(fù)制機(jī)內(nèi)部不含空格的字串C:_w_變換成_w_w_26組合機(jī)器的規(guī)則作業(yè)P1244.1.14.1.64.1.74.2用圖靈機(jī)計(jì)算語言判定假設(shè)字符串w不含空格初始格局為(s,w)29

30當(dāng)w包含空格或左端符，無法確保M的行為4.2用圖靈機(jī)計(jì)算例4.2.1圖靈機(jī)判定語言

L={anbncn:n0}31分n個(gè)階段操作每個(gè)階段向右依次把第一個(gè)遇到的a、b、c改為d，然后歸位當(dāng)按順序不能依次找到一套a、b、c時(shí)，進(jìn)入n，拒絕如果把所有匹配的a、b、c都變成了d，進(jìn)入y，接受4.2用圖靈機(jī)計(jì)算計(jì)算函數(shù)TMM處理字串w且停機(jī)后的格局字串稱為輸出M(w)單變量函數(shù)f(w)324.2遞歸函數(shù)多變量數(shù)值函數(shù)f(w1,w2,…,wk)數(shù)字num(w)被轉(zhuǎn)換為二進(jìn)制字串wM接受數(shù)字n1,n2,…,nk的二進(jìn)制字串形式為輸入M最終停機(jī)停機(jī)后，帶上內(nèi)容為f(n1,n2,…,nk)的二進(jìn)制字串334.2遞歸函數(shù)例4.2.3圖靈機(jī)計(jì)算后繼函數(shù)

succ(n)=n+134字串全1，且都被改為了0，此時(shí)溢出；需要整個(gè)右移，并左端填14.2遞歸可枚舉語言定義4.2.4M半判定L

iffL是遞歸可枚舉的半判定不能用來識(shí)別w是否屬于L，因?yàn)楫?dāng)w不屬于L，M不停機(jī)354.2遞歸可枚舉語言例4.2.4半判定舉例L={w{a,b}*:w至少包含一個(gè)a}

36L是遞歸可枚舉，因?yàn)門M半判定若字串包含a，則停機(jī)若字串不包含a，則在輸入后面跟著的空格里永遠(yuǎn)移動(dòng)下去設(shè)計(jì)不停機(jī)的TM在空格里永遠(yuǎn)移動(dòng)下去死循環(huán):

(q,

a)=(q,

a)4.2遞歸可枚舉語言

37各種語言類的包含關(guān)系正則語言上下文無關(guān)語言可判定語言圖靈可識(shí)別語言384.3圖靈機(jī)的擴(kuò)展多帶圖靈機(jī)雙向無窮帶圖靈機(jī)多帶頭圖靈機(jī)二維帶圖靈機(jī)非確定性圖靈機(jī)394.3圖靈機(jī)的擴(kuò)充:多帶圖靈機(jī)(mTM)…C

mTM的轉(zhuǎn)移函數(shù)(k個(gè)帶)

:(K-H)

kK({,})k

初始:輸入放在第1個(gè)帶子上,其它空白.

定理:每個(gè)多帶TM都有等價(jià)的單帶TM.404.3多帶圖靈機(jī)(mTM)例4.3.1利用mTM實(shí)現(xiàn)復(fù)制機(jī)C(1)把帶1的字串w復(fù)制到帶2上(2)帶2的帶頭移到最左端(3)將帶2字串w復(fù)制到帶1上

41(2)(1)(3)24.3多帶圖靈機(jī)(mTM)定理4.3.2

多帶、多帶頭、雙向無窮圖靈機(jī)或者多維帶的圖靈機(jī)，它們判定或半判定的任何語言以及計(jì)算的任何函數(shù)，都分別可用標(biāo)準(zhǔn)圖靈機(jī)判定、半判定或者計(jì)算。424.5非確定型圖靈機(jī)(NTM)43:((K－H))(K((－{}){,})) :(K－H))toK((－{}){,})

444.5非確定型圖靈機(jī)(NTM)NTM舉例 L(M)={a2n}(q1,)(q2,)(q2,a)(q3,)(q2,)(q4,)(q3,a)(q2,)(q3,)(q3,)(q4,)(q4,)(q4,)(h,)4.5非確定型圖靈機(jī)(NTM)NTMMM接受輸入w：如果存在至少一種停機(jī)格局M半判定L：w屬于LiffM接受w464.5非確定型圖靈機(jī)(NTM)474.5非確定型圖靈機(jī)(NTM)4.5非確定型圖靈機(jī)(NTM)例