2015年5月23日 星期六

Formal Language - Ch10 變種圖靈機 Variants of Turing Machines

 

多帶圖靈機 (k-tape Turing machine)
多帶圖靈機和圖靈機類似,唯一的不同在於它可以有 $k\ (>1)$ 條紙帶,每條紙帶上都有一個讀寫頭。
  • 其狀態轉移函數 $\delta$ 修改為:$\delta : Q\times\Gamma^k \to Q \times \Gamma^k \times \{L, R\}^k$ 此處 $k$ 是紙帶的數目。
  • 表達式 $\delta(q, x_1, x_2, \ldots, x_k) = (q', x'_1, x'_2, \ldots, x'_k, m_1, m_2, \ldots, m_k)$,其中 $m_i = L$ 或 $R$。


多帶圖靈機與單帶圖靈機的等價
對於任意一個多帶圖靈機 $M$ ,存在一個單帶圖靈機 $M'$ ,滿足 $L(M) = L(M')$。

單帶圖靈機轉多帶圖靈機:顯然成立,改一下型別即可。
多帶圖靈機轉單帶圖靈機:改寫方式如下

符號定義
  • $\#$:分開不同紙帶的符號
  • $X^*$:符號上的點代表磁頭位置
  • $U$:代表「空」
  • 初始值:$\#W_1W_2W_3W_4...W_n\#U^*\#U^*\#U^*\#...\#$

多帶圖靈機的一次轉移轉成單帶圖靈機的以下步驟
  • 掃第一遍看磁頭位置
  • 再掃一遍用轉移函式轉換 (如果虛擬磁頭移到#上就補上U*然後全部右移)



[用心去感覺] 多紙帶圖靈機推導可得到的結論
  1. 一端無限的紙帶等價於兩端無限的紙帶(單紙帶等於雙紙帶)
  2. 計算能力:圖靈機 Turing machines > 下推自動機 PDAs > 有限狀態機 DFAs




非決定性圖靈機 (Nondeterministic Turing Machines)
如果不加特殊說明,通常所說的圖靈機都是決定型圖靈機。非決定型圖靈機和決定型圖靈機的不同之處在於,在計算的每一時刻,根據當前狀態和讀寫頭所讀的符號,機器存在多種狀態轉移方案,機器將任意地選擇其中一種方案繼續運作,直到最後停機為止。

具體而言,其狀態轉移函數為 $\delta: Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}}$,其中$Q$是狀態集合,$\Gamma$是帶字母表,$L, R$分別表示讀寫頭向左和向右移動;符號 $2^{A}$ 表示集合$A$的冪集。

例如,設非決定型圖靈機M的當前狀態為q,當前讀寫頭所讀的符號為x,若 $\delta(q,x) = \{ (q_1, x_1, d_1), (q_2, x_2, d_2), \ldots , (q_k, x_k, d_k)\}$ 則M將任意地選擇一個 $(q_i, x_i, d_i)$ ,按其進行操作,然後進入下一步計算。

非決定型圖靈機 $M$ 在輸入串 $\omega$ 上的計算過程可以表示為一棵樹,不同的分支對應著每一步計算的不同的可能性。只要有任意一個分支進入接受狀態,則稱 $M$ 接受 $\omega$ ;只要有任意一個分支進入拒絕狀態,則稱 $M$ 拒絕 $\omega$ ;某些分支可能永遠無法停機,但只要有一個分支可以進入接受或拒絕狀態,我們就說 $M$ 在輸入 $\omega$ 上可停機。注意,我們規定 $M$ 必須是無矛盾的,即它不能有某個分支接受 $\omega$ 而同時另一個分支拒絕$\omega$,這樣有矛盾的非決定型圖靈機是不合法的。

如果語言 $L$ 被非決定型圖靈機 $M$ 在多項式時間內接受,則一定存在多項式 $P$ 使得語言$L$ 被時間複雜度為 $O(2^{P(n)})$ 的決定型圖靈機程序所接受。這個定理說明了為什麼在證明 $P = NP$ 之前,所有的 $NPC$ 問題都只有指數時間複雜度算法。



決定性圖靈機與非決定性圖靈機的等價
對於任意一個非決定型圖靈機$M$,存在一個決定型圖靈機$M'$,使得它們的語言相等,即$L(M) = L(M')$。

決定性圖靈機轉非決定性圖靈機:顯然成立,改一下型別即可。
非決定性圖靈機轉決定性圖靈機:改寫方式如下

因為非決定型圖靈機的計算過程就是一棵樹,因此我們只需遍歷該樹就可以模擬其計算過程。採用疊代加深搜索(Iterative deepening search, IDS)遍歷 $M$ 的計算樹。具體證明如下:

對於非決定型圖靈機 $M$ ,構造一個決定型圖靈機 $M'$ 如下:
  1. 令 $k= 1$;
  2. 深度優先地模擬 $M$ 的每個分支的計算,但每個分支最多只計算 $k$ 步,如果某個計算分支在 $k$ 步內可以停機,則 $M'$ 也停機,並將該計算分支的計算結果輸出。
  3. 令 $k$ 增加 $1$,跳轉到上一步繼續執行。
顯然,若 $M$ 有某個分支可以停機,則此 $M'$ 也一定會找到該分支並停機。因此 $L(M) = L(M')$。





枚舉機 (Enumerators)
枚舉機不吃字串,只吐字串,且會一直吐字串直到吐出我們想要的字串,當吐出想要字串的時候就是圖靈機的接受狀態。設 $S ⊆ Σ*$ 為一個語言,$E$ 是一個枚舉器, 若 $L(E) = S$,則稱 $E$ 枚舉了語言 $S$。若存在這樣的 $E$,$S$ 就稱為遞歸可枚舉語言。


遞歸可枚舉語言和圖靈可識別語言的等價
對於任意一個圖靈機$M$,存在一個枚舉機$E$,使得它們的語言相等,即$L(M) = L(E)$。

圖靈機轉枚舉機:
若有枚舉器 $E$ 枚舉語言 $S$,構造一個圖靈機 $M$ 如下:
   
M = 對於輸入 $ω$
  1. 運行 $E$,依次生成字符串 $s_1, s_2, ...$;
  2. 若遇到某個 $s_i = ω$ 則進入接受狀態並停機。

注意當 $ω ∉ S$ 時,$M$ 可能永不停機,但 $M$ 所接受的語言集合恰好是 $S$,所以 $M$ 識別了 $S$ 。

枚舉機圖靈機
假設我們有圖靈機 $M$ 識別語言 $S$,構造一個枚舉器 $E$ 如下:

E = 忽略輸入
  1. 對 $i = 1, 2, 3, ...$ 重複下列步驟;
  2. 設 $Σ^* = {s_1, s_2, ...}$,分別將 $s_1, s_2, ... ,s_i$ 作為 $M$ 的輸入,模擬 $M$ 執行 $i$ 步;
  3. 若某個 $s_j$, $1 ≤ j ≤ i$,在 $i$ 步內可被 $M$ 接受,則將其輸出。

顯然,這樣構造的枚舉器 $E$ 最終輸出的語言恰好就是 $S$ 。注意 $S$ 中的字符串並沒有在 $E$ 中按字典序輸出,而且同一個串可能會被 $E$ 輸出多次,但根據枚舉器的定義, 這些都是允許的。




References

交大陳穎平教授正規語言講義

wiki
http://zh.wikipedia.org/wiki/非确定型图灵机
http://zh.wikipedia.org/wiki/多带图灵机
http://zh.wikipedia.org/wiki/递归可枚举语言





技術提供:Blogger.