交替式圖靈機

圖靈機在理論上能夠模擬現代數字計算機的一切運算， 可視為現代數字計算機的數學模型，是一種抽象的計算模型。交替式圖靈機（Alternating Turing Machine，ATM）是計算複雜度理論中定義的一種非確定型圖靈機（NTM）。與一般非確定型圖靈機不同，交替式圖靈機將接受語言的規則一般化到NP和反NP。交替式圖靈機的概念由Chandra和Stockmeye於1976年提出。

基本介紹

• 中文名：交替式圖靈機
• 外文名：Alternating Turing Machine
• 學科：計算機科學
• 類型：非確定型圖靈機
• 特點：接受語言的規則一般化到NP和反NP
• 提出者：Chandra和Stockmeye

定義

直觀描述

NP的定義中使用了語言的存在形式，亦即如果存在一個選擇都能夠使得圖靈機達到接受狀態，那么整個語言就能夠被接受。與此對應，反NP的定義中使用了語言的全稱形式，亦即整個語言被接受，若且唯若每一個選擇都達到一個接受狀態。結合這兩個定義，可以給出一個語言被交替式圖靈機接受的定義。

對一台交替式圖靈機而言，狀態集被劃分為兩部分：存在狀態（existential state）和全稱狀態（universal state）。存在狀態的接受條件為如果該狀態存在一種轉移序列到達接受狀態，而全稱狀態的接受條件為對該狀態而言，任何一種轉移序列都能夠到達接受狀態。（因而，一個不包含任何轉移的全稱狀態無條件接受，而一個不包含任何轉移的存在狀態無條件拒絕。）互動式圖靈機接受此語言，若且唯若初始狀態得到接受。

形式化描述

形式地，一台（單帶）交替式圖靈機是一個5元組，其中：

是一個有限大小的狀態集；

是一個有限大小的字母表；

被稱為轉移函式（ 代表帶頭左移， }代表帶頭右移）；圖靈機狀態可以轉移到狀態

是初始狀態，開始時控制就在這一狀態上；

定義每個狀態的類型（接受狀態或拒絕狀態），其中 代表全稱狀態， 代表存在狀態。，其中表示讀寫頭是向左移還是向右移, - 表示不移動，不同狀態可以隨著字元轉換。

如果 的格局在狀態 中，且 ，那么，格局為接受格局。如果格局滿足 ，那么，格局為拒絕格局。對於格局滿足 ，該格局接受若且唯若所有一步之內能夠到達的格局是接受格局。反之，如果這些格局中存在一個格局拒絕，那么拒絕。對於格局滿足 ，該格局接受若且唯若存在一個一步之內能夠到達的格局是接受格局。反之，如果所有一步之內可達的格局拒絕，那么拒絕。 接受輸入串 ，如果的初始格局（即 的狀態為 ，帶頭在帶的最左端，帶中包含 ）被接受。否則， 拒絕 。

k次交替圖靈機

k次交替圖靈機是一種將存在狀態和全稱狀態互相轉移次數限定在 次的交替式圖靈機。亦即，定義狀態集 ，其中，狀態集 為存在狀態，狀態集 為全稱狀態（或者相反）。並且，不存在從 到 的狀態轉移滿足 。例如，考慮以下電路最小化問題：給定一個能夠計算布爾函式 的電路 和一個整數 ，確定是否存在一個最多包含 個門的電路 可以計算 。一台2次交替圖靈機從一個存在狀態出發可以在多項式時間內解決這個問題（在存在狀態通過猜測電路 的 個門，此後進入全稱狀態，猜測輸入並檢查輸出是否和 相同）。一台從存在狀態（或者全稱狀態）出發的次交替圖靈機可以在多項式時間內解決 （或者 ）的問題。

資源上界

在利用上面的定義確定一台交替式圖靈機是否接受或拒絕某一格局時，並不需要檢查當前格局可以到達的所有格局。具體來說，對於存在格局，如果某一將來格局被接受即可標記為接受。對全稱格局，如果某一將來格局被拒絕，則可被標記為拒絕。對於運行時間，規定一台ATM在 時間內判定一個形式語言，如果對於任意長度為 的輸入，通過 步檢查（必要的）格局即可接受或拒絕初始格局。對於運行空間，規定一台ATM在 空間內判定一個形式語言，如果至多修改圖靈機帶上從左端起 位即可完成對必要格局的檢查。

示例

也許交替式圖靈機解決的最簡單的問題是量詞布爾公式問題。這一問題是布爾可滿足性問題的擴充，即每個變數可以被一個全稱量詞或存在量詞所約束。交替式圖靈機依照約束的次序對每一個存在量詞尋找一個可能的賦值，對每一個全稱量詞尋找所有的賦值。在對所有約束變數確定值之後，交替式圖靈機根據剩餘的布爾公式確定接受還是拒絕。因此，接受一個存在量詞意味著存在一個賦值，使得賦值後的量詞布爾公式可滿足。類似地，接受一個全稱量詞意味著對任何一個賦值，賦值後的量詞布爾公式可滿足。在ATM中，解決量詞布爾公式問題需要 時間和 空間。布爾可滿足性問題可被視為量詞布爾公式問題將所有變數約束為存在量詞的特例。從而普通的非確定型圖靈機可以有效地解決這一問題。

圖靈機

圖靈機由圖靈（Alan Turing）於 1936 年提出，當時的主要目的是為了理解計算問題的邊界，即什麼是可計算的。後來發現它是一種精確的計算機模型，可以模擬現實計算機的所有計算行為。一切“可計算”函式都等價於圖靈機可計算函式，而圖靈機可計算函式類又等價於一般遞歸函式類。圖靈機能表示算法、程式和符號行的變換，因而可作為電子計算器的數學模型，也可用作控制算法的數學模型，在形式語言理論中還可用來研究短語結構語言。非確定型圖靈機和確定型圖靈機的不同之處在於，在計算的每一時刻，根據當前狀態和讀寫頭所讀的符號，機器存在多種狀態轉移方案，機器將任意地選擇其中一種方案繼續運作，直到最後停機為止。具體而言，其狀態轉移函式為

其中 是狀態集合（包含初始狀態、接受狀態、拒絕狀態和終止狀態）， 是帶字母表， 分別表示讀寫頭向左和向右移動；符號 表示集合 的冪集，即

開始的時候將輸入符號串從左到右依此填在紙帶的第號格子，他格子保持空白。非確定型圖靈機 在輸入串 上的計算過程可以表示為一棵樹，不同的分支對應著每一步計算的不同的可能性。只要有任意一個分支進入接受狀態，則稱 接受 ；只要有任意一個分支進入拒絕狀態，則稱 拒絕 ；某些分支可能永遠無法停機，但只要有一個分支可以進入接受或拒絕狀態，我們就說 在輸入 上可停機。注意，我們規定必須 是無矛盾的，即它不能有某個分支接受 而同時另一個分支拒絕 ，這樣有矛盾的非確定型圖靈機是不合法的。非確定型圖靈機在計算能力上並沒有因為加上了非確定性的狀態轉移而有所增強。