Formal Language - Ch13 可歸約性 Reducibility

可歸約性 Reducibility
B歸約是將某個計算問題 (computational problem) 轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類，因轉換過程而異。A問題A可歸約為問題B：問題B的答案可用於解決問題A，因此解決A不會難於解決B。

寫作 $A \leq B$，通常也在$\leq$符號下標使用的歸約手法$\leq_x$。以下用決定性問題舉例：

• B是決定性問題 $\rightarrow$ A是決定性問題
• A是不可決定性問題 $\rightarrow$ B是不可決定性問題

可歸約性證明用法 - 歸謬法

若我們擁有一個已證明難以解決的問題，我們又獲得另一個相似的新問題。我們可合理推想此新問題亦是難以解決的。

假設若此新問題本質上容易解答，且若我們可展示每個舊問題的實例可經由一系列轉換步驟變成新問題的實例，則舊問題便容易解決，因此得到悖論。因此新問題可知亦難以解決。

不可決定性問題證明 

$HALT_{TM}$ 是不可決定的問題

  $HALT_{TM} = \{ <M,w> \ |\ M是一個圖靈機\ 且\ M在輸入為w時停機 \}$

先假設$HALT_{TM}$ $R$是決定性問題，然後用$R$構造一個圖靈機$S$ (決定器, decider）讓$A_{TM}$也是決定性問題，矛盾！

S = 一個圖靈機$M$和一個字串$w$有以下行為：

1. 如果字串$w$在圖靈機$R$上跑不會停機，則$R$會拒絕，那麼S就拒絕 。
2. 如果字串$w$在圖靈機$R$上跑會停機，則$R$會接受，那麼$S$就用字串$w$在輸入的圖靈機$M$上做模擬，直到停機，最後停在接受就接受，反之則拒絕。

因此，如果 $R$ 決定 $HALT_{TM}$，則 $S$ 決定 $A_{TM}$；因為 $A_{TM}$ 是不可決定的問題，所以 $HALT_{TM}$ 也是不可決定的問題。

$E_{TM}$ 是不可決定的問題

$E_{TM} = \{  <M>\ |\  M是一個圖靈機\ 且\ L(M) = \phi \}$

先假設$E_{TM}$ $R$是決定性問題，然後用$R$構造一個圖靈機$S$ (空決定器, empty decider)讓$A_{TM}$也是決定性問題，矛盾！

S = 一個圖靈機$M$和一個字串$w$有以下行為：

1. 先用圖靈機$M$和字串$w$創造一個圖靈機$M_w$如果進來的字串 $x$ 和目標 $w$ 相同，就讓 $w$ 正常在 $M$ 上跑，最後停在接受就接受，反之拒絕。
2. 在 $R$ (空決定器, empty decider) 上跑 $M_w$。
3. 如果 $R$ 接受，$S$ 就拒絕 (因為 $R$ 接受表答案為空)，如果 $R$ 拒絕，$S$就接受。

因此，如果 $R$ 決定 $E_{TM}$，則 $S$ 決定 $A_{TM}$；因為 $A_{TM}$ 是不可決定的問題，所以 $E_{TM}$ 也是不可決定的問題。


$REGULAR_{TM}$ 是不可決定的問題

$REGULAR_{TM} = \{  <M>\ |\ M是一個圖靈機\ 且\ L(M) 是正則語言(regular \ language) \}$

先假設$REGULAR_{TM}$ $R$是決定性問題，然後用$R$構造一個圖靈機$S$ (正則決定器, regular decider）讓$A_{TM}$也是決定性問題，矛盾！

S = 一個圖靈機$M$和一個字串$w$有以下行為：

1. 先創造一個過濾器$M_w(x)$，
• 如果字串 $w = 0^n1^n$ 就直接接受
• 如果字串 $w \neq 0^n1^n$ 就讓$w$正常在$M$上跑
2. 在 R (regular decider) 上跑$M_w$
3. 如果 $R$ 接受， $S$ 就接受，反之則拒絕

因此，如果 $R$ 決定 $REGULAR_{TM}$，則 $S$ 決定 $A_{TM}$；因為 $A_{TM}$ 是不可決定的問題，所以 $REGULAR_{TM}$ 也是不可決定的問題。

$EQ_{TM}$ 是不可決定的問題

$EQ_{TM} = \{ <M_1,M_2>\ |\ M_1 和 M_2 是兩個圖靈機\ 且\  L(M_1) = L(M_2) \}$

假設一個 $EQ_{TM}$ $R$是決定性問題，然後用$R$構造一個圖靈機$S$ (決定器, decider）讓$E_{TM}$也是決定性問題，矛盾！

S = 一個圖靈機$M$有以下行為：

1. 用$M_1$和$M_{reject}$($M_{reject}$ 拒絕所有輸入)來跑 $R$。
2. 如果 $R$ 接受， $S$ 就接受，反之則拒絕。

因此，如果 $R$ 決定 $EQ_{TM}$ ，則 $S$ 決定 $E_{TM}$；因為 $E_{TM}$ 是不可決定的問題，所以  $EQ_{TM}$ 也是不可決定的問題。



[補充] 線性有界自動機 linear bounded automaton
線性有界自動機(linear bounded automaton, LBA)是受限形式的非確定圖靈機，它不同於圖靈機的地方在於儘管磁帶在最初輸入進來時被認為是無限的，但輸入進來後只有其長度是初始輸入的線性函數的有限臨近部分可以被讀寫磁頭訪問。這個限制使 LBA 成為在某些方面比圖靈機更接近實際存在的計算機的精確模型。

• $LBA$ 可以被用來決定(decide) $A_{DFA}$ 、 $A_{CFG}$ 、 $E_{DFA}$ 和 $E_{CFG}$
• $LBA$ 可以被用來決定所有的 $CFL$ 

$A_{LBA}$ 是可決定的問題
$A_{LBA} = \{<M,w>\ |\ M是一個接受字串w的線性有界自動機(LBA)\}$

• Just count it : $q$ states $\times$ $n$ positions $\times$ $g^n$ possible tape content $=$ $qng^n$
• Proof idea : Because the number of all possible configurations can be exactly computed, the looping of a machine can therefore be determined.

$E_{LBA}$ 是不可決定的問題
$E_{LBA} = \{<M>\ |\ M是一個線性有界自動機(LBA)\ 且\ L(M) = \phi\}$

$ALL_{CFG}$ 是不可決定的問題
$ALL_{CFG} = \{ <G>\ |\ G是一個上下文無關文法(CFG)\ 且\ L(G)=\Sigma^* \}$



萊斯定理 Rice's Theorem 

是否有一個比較系統的方法來判斷哪些函數是不可決定的呢？

是有的，這就是著名的Rice's Theorem：這個定理是說，有一個函數集合 $B$ (即這個集合 $B$ 是函數 $f$ 的集合)，並且 $B$ 不是空集，也不是全部函數 $f$，那麼一個程式是否屬於 $B$ 是不可決定的。

也就是說，設P是一個複雜(nontrivial)性質，代表一堆圖靈辨識的語言有某種同樣的性質；且有些語言有，有些語言沒有這個性質。而決定這個圖靈機有沒有這樣性質的語言，是具有不可決定性的 (undecidable)。

例如，你出了一個作業要求學生寫一個程式，任意给定 $x$，輸出 $2x$。你驚奇地發現這門課竟然有200名學生，然後一個偷懶的想法在你腦中誕生了：我是不是能寫一個程式，來自動判斷學生上交的程序是否滿足要求呢？

Rice's theorem打破了你的幻想，這樣的程式是不存在的。這個例子中，令 $B$ 包含 $f(x)=2x$ 這個函數，助教想做的是判斷一個程式是否屬於這個集合 $B$，Rice's theorem告訴我們這樣的程式是不存在的。



References

Wiki - 歸約
http://zh.wikipedia.org/wiki/%E6%AD%B8%E7%B4%84

Internet - 什麼是可計算理論
http://fanli7.net/a/bianchengyuyan/20130628/377087.html

Computer Science notes ⇒ Theory of Computation
http://www.pling.org.uk/cs/toc.html

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