CH4圖靈機

4.1圖靈機的定義圖靈:計算通常是一個人拿著筆在紙上進行的.

他根據

眼睛看到的紙上符號,腦中的若干法則,

指示筆在紙上擦掉或寫上一些符號,

再改變他所看到的范圍.

繼續,直到他認為計算結束.腦:控制器紙:存儲帶眼睛和筆:讀寫頭法則:轉移函數24.1圖靈機的定義

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

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

包括空格符_和左端符;不包含代表移動的符號和；s

K：初始狀態；HK：停機狀態集，進入任意停機狀態，則TM停止δ：轉換函數，從

(K－H)

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

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

b

，代表“將帶上的

a

改寫為

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

，代表“向左移動讀寫頭一格，其它不變”定義中，在同一步驟中，TM僅能移動讀寫頭一格，或者改寫當前位置的字符此規定不影響TM的表達能力，因為可以通過引入中間狀態將任意操作分解為寫操作和移動操作兩個動作4.1圖靈機的定義例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圖靈機的定義刪除非空格符例4.1.2TM向左掃描，遇到空格后停機 K={q0,h}

={a,,}

s=q0,

:4.1圖靈機的定義機器進入無限循環如果不存在空格TM

(K,,,

s,H)

的格局是成員：

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

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

13字符替換，位置不變4.1圖靈機的定義定義4.1.3圖靈機的格局一步產生規則

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

位置右移，字符不變4.1圖靈機的定義例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圖靈機的定義4.1.1圖靈機的記號:基本機器

寫a機:a或者Ma

左移帶頭機:M縮寫為L

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

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

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

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

iffL是遞歸可枚舉的半判定不能用來識別w是否屬于L，因為當w不屬于L，M不停機354.2遞歸可枚舉語言例4.2.4半判定舉例L={w{a,b}*:w至少包含一個a}

36L是遞歸可枚舉，因為TM半判定若字串包含a，則停機若字串不包含a，則在輸入后面跟著的空格里永遠移動下去設計不停機的TM在空格里永遠移動下去死循環:

(q,

a)=(q,

a)4.2遞歸可枚舉語言

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

mTM的轉移函數(k個帶)

:(K-H)

kK({,})k

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

定理:每個多帶TM都有等價的單帶TM.404.3多帶圖靈機(mTM)例4.3.1利用mTM實現復制機C(1)把帶1的字串w復制到帶2上(2)帶2的帶頭移到最左端(3)將帶2字串w復制到帶1上

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

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

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