交替式圖靈機

交替式圖靈機計算機科學(xué)術(shù)語01定義圖靈機示例目錄0302基本信息圖靈機在理論上能夠模擬現(xiàn)代數(shù)字計算機的一切運算，可視為現(xiàn)代數(shù)字計算機的數(shù)學(xué)模型，是一種抽象的計算模型。交替式圖靈機（AlternatingTuringMachine，ATM）是計算復(fù)雜度理論中定義的一種非確定型圖靈機（NTM）。與一般非確定型圖靈機不同，交替式圖靈機將接受語言的規(guī)則一般化到NP和反NP。交替式圖靈機的概念由Chandra和Stockmeye于1976年提出。定義直觀描述形式化描述k次交替圖靈機資源上界定義直觀描述NP的定義中使用了語言的存在形式，亦即如果存在一個選擇都能夠使得圖靈機達到接受狀態(tài)，那么整個語言就能夠被接受。與此對應(yīng)，反NP的定義中使用了語言的全稱形式，亦即整個語言被接受，當(dāng)且僅當(dāng)每一個選擇都達到一個接受狀態(tài)。結(jié)合這兩個定義，可以給出一個語言被交替式圖靈機接受的定義。對一臺交替式圖靈機而言，狀態(tài)集被劃分為兩部分：存在狀態(tài)（existentialstate）和全稱狀態(tài)（universalstate）。存在狀態(tài)的接受條件為如果該狀態(tài)存在一種轉(zhuǎn)移序列到達接受狀態(tài)，而全稱狀態(tài)的接受條件為對該狀態(tài)而言，任何一種轉(zhuǎn)移序列都能夠到達接受狀態(tài)。（因而，一個不包含任何轉(zhuǎn)移的全稱狀態(tài)無條件接受，而一個不包含任何轉(zhuǎn)移的存在狀態(tài)無條件拒絕。）交互式圖靈機接受此語言，當(dāng)且僅當(dāng)初始狀態(tài)得到接受。形式化描述形式地，一臺（單帶）交替式圖靈機是一個5元組，其中：是一個有限大小的狀態(tài)集；是一個有限大小的字母表；被稱為轉(zhuǎn)移函數(shù)（代表帶頭左移，}代表帶頭右移）；圖靈機狀態(tài)可以轉(zhuǎn)移到狀態(tài)是初始狀態(tài)，開始時控制就在這一狀態(tài)上；定義每個狀態(tài)的類型（接受狀態(tài)或拒絕狀態(tài)），其中代表全稱狀態(tài)，代表存在狀態(tài)。，其中表示讀寫頭是向左移還是向右移,-表示不移動，不同狀態(tài)可以隨著字符轉(zhuǎn)換。如果的格局在狀態(tài)中，且，那么，格局為接受格局。如果格局滿足，那么，格局為拒絕格局。對于格局滿足，該格局接受當(dāng)且僅當(dāng)所有一步之內(nèi)能夠到達的格局是接受格局。反之，如果這些格局中存在一個格局拒絕，那么拒絕。對于格局滿足，該格局接受當(dāng)且僅當(dāng)存在一個一步之內(nèi)能夠到達的格局是接受格局。反之，如果所有一步之內(nèi)可達的格局拒絕，那么拒絕。接受輸入串，如果的初始格局（即的狀態(tài)為，帶頭在帶的最左端，帶中包含）被接受。否則，拒絕。k次交替圖靈機k次交替圖靈機是一種將存在狀態(tài)和全稱狀態(tài)互相轉(zhuǎn)移次數(shù)限定在次的交替式圖靈機。亦即，定義狀態(tài)集，其中，狀態(tài)集為存在狀態(tài)，狀態(tài)集為全稱狀態(tài)（或者相反）。并且，不存在從到的狀態(tài)轉(zhuǎn)移滿足。例如，考慮以下電路最小化問題：給定一個能夠計算布爾函數(shù)的電路和一個整數(shù)，確定是否存在一個最多包含個門的電路可以計算。一臺2次交替圖靈機從一個存在狀態(tài)出發(fā)可以在多項式時間內(nèi)解決這個問題（在存在狀態(tài)通過猜測電路的個門，此后進入全稱狀態(tài)，猜測輸入并檢查輸出是否和相同）。一臺從存在狀態(tài)（或者全稱狀態(tài)）出發(fā)的次交替圖靈機可以在多項式時間內(nèi)解決（或者）的問題。資源上界在利用上面的定義確定一臺交替式圖靈機是否接受或拒絕某一格局時，并不需要檢查當(dāng)前格局可以到達的所有格局。具體來說，對于存在格局，如果某一將來格局被接受即可標(biāo)記為接受。對全稱格局，如果某一將來格局被拒絕，則可被標(biāo)記為拒絕。對于運行時間，規(guī)定一臺ATM在時間內(nèi)判定一個形式語言，如果對于任意長度為的輸入，通過步檢查（必要的）格局即可接受或拒絕初始格局。對于運行空間，規(guī)定一臺ATM在空間內(nèi)判定一個形式語言，如果至多修改圖靈機帶上從左端起位即可完成對必要格局的檢查。示例示例也許交替式圖靈機解決的最簡單的問題是量詞布爾公式問題。這一問題是布爾可滿足性問題的擴充，即每個變量可以被一個全稱量詞或存在量詞所約束。交替式圖靈機依照約束的次序?qū)γ恳粋€存在量詞尋找一個可能的賦值，對每一個全稱量詞尋找所有的賦值。在對所有約束變量確定值之后，交替式圖靈機根據(jù)剩余的布爾公式確定接受還是拒絕。因此，接受一個存在量詞意味著存在一個賦值，使得賦值后的量詞布爾公式可滿足。類似地，接受一個全稱量詞意味著對任何一個賦值，賦值后的量詞布爾公式可滿足。在ATM中，解決量詞布爾公式問題需要時間和空間。布爾可滿足性問題可被視為量詞布爾公式問題將所有變量約束為存在量詞的特例。從而普通的非確定型圖靈機可以有效地解決這一問題。圖靈機圖靈機圖靈機由圖靈（AlanTuring）于1936年提出，當(dāng)時的主要目的是為了理解計算問題的邊界，即什么是可計算的。后來發(fā)現(xiàn)它是一種精確的計算機模型，可以模擬現(xiàn)實計算機的所有計算行為

。一切“可計算”函數(shù)都等價于圖靈機可計算函數(shù)，而圖靈機可計算函數(shù)類又等價于一般遞歸函數(shù)類。圖靈機能表示算法、程序和符號行的變換，因而可作為電子計算器的數(shù)學(xué)模型，也可用作控制算法的數(shù)學(xué)模型，在形式語言理論中還可用來研究短語結(jié)構(gòu)語言。非確定型圖靈機和確定型圖靈機的不同之處在于，在計算的每一時刻，根據(jù)當(dāng)前狀態(tài)和讀寫頭所讀的符號，機器存在多種狀態(tài)轉(zhuǎn)移方案，機器將任意地選擇其中一種方案繼續(xù)運作，直到最后停機為止。具體而言，其狀態(tài)轉(zhuǎn)移函數(shù)為其中是狀態(tài)集合（包含初始狀態(tài)、接受狀態(tài)、拒絕狀態(tài)和終止?fàn)顟B(tài)），是帶字母表，分別表示讀寫頭向左和向右移動；符號表示集合的冪集，即開始的時候?qū)⑤斎敕柎畯淖蟮接乙来颂钤诩垘У牡谔柛褡樱褡颖３挚瞻?。非確定型圖靈機在輸入串上的計算過程可以表示為一棵樹，不同的分支對應(yīng)著每一步計算的不同的可能性。只要有任意一個分支進入接受狀態(tài)，則稱接受；只要有任意一個分支進入拒絕狀態(tài)，則稱拒絕；某些分支可能永遠(yuǎn)無法停機，但只要有一個