交替式圖靈機(jī)

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

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