圖靈機講課資料

§5.3圖靈機為將算法形式化，必須確定一計算模型。我們使用的是確定型單帶圖靈機(簡稱DTM)。1一個確定型單帶圖靈機由以下三個部分組成(見下頁圖)：·狀態(tài)控制器·讀寫頭·無限長的帶子，帶子劃成小格，格子標記 …,－3，－2，－1，0，1，2,3，…2

…－2－10123…狀態(tài)控制器讀寫頭3更形式地說，DTM由七個元素組成：1.有限集合Γ，由出現(xiàn)在帶上的符號組成2．∑，為Γ的子集，由輸入符號組成3．特殊符號?

，表示空白，?

∈(Γ-∑)4．有限集合Q，由DTM的狀態(tài)組成5．起始狀態(tài)qo

∈Q6．兩個終止狀態(tài)qY及qN，均屬于Q7．狀態(tài)轉換函數(shù)

δ:(Q-{qY,qN})×Γ

→Q×?！羬-1，+1}4令

δ(q，s)＝(q′，s′，Δ)則讀寫頭于正對著的格子上用字符s′替代s(字符s不復存在)，如Δ＝-1，讀寫頭左移一格，如Δ＝1，則讀寫頭右移一格，而后DTM進入狀態(tài)q′．6這樣DTM運行的一步就完成了。DTM就這樣一步步地運行，直至DTM進入狀態(tài)qY或qN．qY表示運行的解答為“是”，qN表示運行的解答為“否”。7由以上敘述可以看出狀態(tài)轉換函數(shù)的重要作用，函數(shù)δ的值將決定DTM要進入的新狀態(tài)，被掃描的格子應用什么符號更新讀寫頭應左移還是右移。801?q0(q0,0,+1)(q0,1,+1)(q1,?,-1)q1(q2,?,-1)(q3,?,-1)(qN,?,-1)q2

(qY,?,-1)(qN,?,-1)(qN,?,-1)q3

(qN,?,-1)(qN,?,-1)(qN,?,-1)例有確定型單帶圖靈機如下

Γ＝{0，1，?}

∑＝{0，1}

Q＝{qo,

q1,

q2,

q3,

qY,qN}9如輸入字符串x＝100100，DTM經(jīng)九步操作后，進入終止狀態(tài)qY即該確定型單帶圖靈機對輸入串x的解答為“是”。如下圖所示,→表示讀寫頭的位置.10→1001001→0010010→0100100→1001001→0010010→010010010010→01001→0?100→1??qo

qo

qo

qo

qo

qo

qo

q1

q2

qY

11如DTM的輸入x∈∑*，且DTM的運行停止在狀態(tài)qY，則稱DTM接受x．確定型單帶圖靈機M接受的所有字符串組成M的語言LM定義為 LM＝{x∈∑*|M接受x}12例中的確定型單帶圖靈機的語言為以‘00’結尾的字符串的集合。此例的DTM對任何輸入串都會停止，并給出“是”或“否”的結果。13“識別語言”與“解決‘是否’問題”之間的關系是很明顯的，如圖靈機M對所有的輸入串都會終止運算，且 LM＝L(Π，e)則稱M解決了“是否”問題Π.14例四整除問題實例：正整數(shù)N問：N能否被4整除如將N表示為二進制數(shù)，則N被4整除的充要條件為：N的二進制表示形式為以‘00’結尾的字符串。因此前例的圖靈機解決了本例的“四整除問題”。15應當指出，圖靈機也可用于計算函數(shù)值。如圖靈機M對任何輸入x∈∑*的運行都能停止，則M表示函數(shù) fM：∑*→Γ*即M將輸入字符串x映射為Γ上的一個字符串。M對串x運行終止時，帶上的字符串(第一格以右止于第一個空白之間的字符串)為函數(shù)fM(x)的值。16例中的圖靈機將輸入串的最后兩個字符刪除如|x|<2，則結果為空串。如其輸入值為N,則計算的函數(shù)為N/417盡管確定型單帶圖靈機的每一步只執(zhí)行非常有限的操作但是DTM可以執(zhí)行任何計算機可以執(zhí)行的運算只是可能慢些。18DTM對輸入串x∈∑*運行所需時間為DTM進入終止狀態(tài)qY或qN所需之步數(shù)。圖靈機M的時間復雜度函數(shù) TM：Z十

→Z十

TM(n)等于所有長度為n的輸入字符串所需時間之最大者。19如存在多項式p，使TM(n)≤p(n)，(n≧1)則稱M為多項式時間確定型單帶圖靈機。20集合P是語言集合，P＝{L|存在多項式時間圖靈機M，且L＝LM}由于問題與語言之間的對應關系,也可將P看成問題集合。如L(Π,e)∈P，則有 Π∈P，

即存在多項式時間確定型單帶圖靈機，該圖靈機能解決問題Π.多項式時間算法與多項式時間確定型單帶圖靈機是等同的。21我們知道，至今還沒有多項式時間算法可以解決巡回售貨員問題。但是如果給我們一條閉合回路，我們檢查該回路是否滿足條件:“包含所有城市且長度不大于B”所需的檢驗算法顯然是多項式時間的。22子圖同構問題，如給我們子集V'

?Vl和E'?

El及一對一映射 fl：V'

→V2

則只須檢驗下述三條件|V'|=|V2||E'|=|E2|(u，v)∈

E'，≡(f(u),f(v))∈E2同樣，所需的檢驗算法也是多項式時間的。23需要指出的是多項式時間檢驗并不意味多項式時間解決問題因為在檢驗之前要猜可能解。對一個可能解檢驗結果為“否”，并不意味著此實例的解為“否”，還要猜另一個可能解，而可能解的總數(shù)為指數(shù)函數(shù)。24不確定算法。不確定算法包含兩個階段：猜測階段和檢測階段。對于一個實例。第一階段猜一可能解S；第二階段則檢測以確定S是不是實例的解。關于一不確定算法以及問題Π，如下列兩點對所有實例I∈DΠ成立，則稱該不確定算法解決問題Π：1．如I∈YΠ，則必存在某可能解S，對S檢測的結果為“是”。2．如I?

YΠ，則不存在任何可能解，其檢測結果為“是”。25對巡回售貨員問題,可構造不確定算法,其第一階段猜城市的一個序列，第二階段檢測這個序列對應的閉合回路長度是否小于或等于B．顯然，一個實例有一條滿足條件的閉合回路的充要條件為:存在一個可能解S,對S檢測的結果為“是”.從而，巡回售貨員問題被該不確定算法解決。26多項式時間不確定算法解決問題Π是指:存在n的多項式P，每一個屬于YΠ，長度為n的實例有可能解S，該可能解檢測結果為“是”且檢測所需時間不大于P(n)．這要求S的長度也是多項式的,不然所需時間上限必不是多項式函數(shù)。27確定型單帶圖靈機(DTM)加上一個猜測器及一個只寫頭,就得到了不確定型單帶圖靈機(簡稱NTM)28-3–2–10123狀態(tài)控制器猜測器讀寫頭只寫頭29猜測器和只寫頭的功能為猜一個可能解，并將之寫到帶子第0格子的左側(第0格為空白?)NTM的運行分成兩個階段。運行開始時問題實例的輸入串已在帶上，讀寫頭正對第一格，這與DTM情況一樣。只寫頭正對標記為－l的格子。第一階段為猜測階段，只寫頭將可能解諸符號(屬集合Γ)寫到格子中，然后左移一格或停止不動。如只寫頭停止移動，則表示第一階段結束，第一階段在帶上寫什么樣的字符串完全是任意的第二階段隨即開始，其后的運行與DTM一樣。30第一階段猜測的串(即可能解)在第二階段被檢測當圖靈機進入qY或qN時，運行結束。只有當圖靈機終止在狀態(tài)qY，表示問題實例解為“是”。其它情況(終止在狀態(tài)qN，或永不終止)都不表示解為“是”。不確定型單帶圖靈機可能有多次運行。如果至少有一次運行結果為“是”，則稱該圖靈機接受字符串x．不確定型單帶圖靈機M的語言LM定義為LM={x∈∑*|M接受x}31NTM接受x∈LM所需的時間是所有接受x的運行所需步數(shù)(為兩個階段的步數(shù)之和)的最小者時間復雜度函數(shù) TM：Z十

→

Z十

定義為，TM(n)等于所有長度為n的輸入串x∈LM所需時間的最大者。如存在多項式P，且TM(n)≤P(n)(n≧1)則稱M為多項式時間不確定型圖靈機。32集合NP的形式化定義如下所述NP＝{L|存在多項式時間不確定型 圖靈機M，且LM=L}同樣地，如L(Π,e)∈NP，則我們說Π∈NP．33集合P與集合NP的關系還不清楚，但是顯然有 P?NP(證)只須證明如問題Π∈P，則Π∈NP．令A是Π的一個多項式時間算法，只要將A充作檢測部分，略去猜測器，(猜測器不運作)我們就得到了一個不確定型圖靈機，這是一個多項式時間不確定型圖靈機，并且它解決問題Π，因此 Π∈NP．34命題1如Π∈NP，則Π能被復雜度為O(2P(n))的算法解決(其中P為多項式)。(證)因為Π∈NP，則能被多項式時間不確定型圖靈機解決，也就是說Π能為多項式時間不確定算法A解決。A的時間復雜度的上限為多項式q(n)，即檢測部分所需步數(shù)的上限為q(n),可能解長度的上限是多項式,也記為q(n)．35又可能解的總數(shù)不超過Kq(n)(其中K＝|Γ|)．因此，使