Formal Language - Ch14 多一歸約 Mapping Reducibility

多一歸約 Mapping Reducibility
We have many types of reductions, now we'll formally define one of them : Mapping Reducibility.

Definition : A function $f:\Sigma^*  \rightarrow \Sigma^*$ is called computable if there is a TM that on every input $w$ halts with $f(w)$ on its tape (and nothing else).

Definition : Language $A$ is mapping reducible (or, many-one reducible) to language $B$, denoted $A \leq_m B$, if there is a computable function $f:\Sigma^* \rightarrow \Sigma^*$ such that, for every $w$

    $W \in A $ iff $ f(w) \in B$

The function $f$ is called the reduction of $A$ to $B$


[用心去感覺] 多一歸約是一種「包裝」

$A \leq_m B$      ( $w \in A \leftrightarrow f(w) \in B$ )

• 所有在$A$的字串都在$B$裡 (的某些字串)、所有不在$A$的字串都不在$B$裡
• 沒有one-to-one和onto的限制條件!

多一歸約性質

If $A \leq_m B$ and $B$ is decidable, then $A$ is decidable.
If $A \leq_m B$ and $A$ is undecidable, then $B$ is undecidable.

概念：把 $A$ 相關的東西轉成 $B$ 的，$B$ 的決定器就可以用了!
證明：$M$ is $B$ the decider for $B$ and $f$ be the reduction from $A$ to $B$.

      $f$ = 在一個字串$w$有以下行為

1. 計算 $f(w)$
2. 在 $M$ 上跑 $f(w)$

用多一歸約證明不可決定性問題

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

$<M,w> \in A_{TM}$ if and only if $<M',w'> \in HALT_{TM}$

可計算函數 f : $f$會輸入$<M,w>$並輸出$<M',w'>$，如果 $A_{TM}$ 的$M$拒絕的話就讓$M'$當機(一直迴圈)，這樣$HALT_{TM}$就會拒絕


$EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable
概念：根據定義兩邊取補集是一樣的，$A_{TM} \leq_m B$ 則 $A_{TM}' \leq_m B'$

先證明 $A_{TM}$ 可歸約成 $EQ_{TM}'$
可計算函數 f : $f$ 會輸入 $<M,w>$ 並輸出 $<M_1,M_2>$

• $M_1$ 
• 拒絕所有的字串
• $M_2$
• 如果$M$接受字串$w$ ，則$M_2$接受所有的字串；
• 如果$M$拒絕字串$w$，則$M_2$拒絕所有的字串 

再證明 $A_{TM}$ 可歸約成 $EQ_{TM}$
可計算函數 g : $g$ 會輸入 $<M,w>$ 並輸出 $<M_1,M_2>$

• $M_1$ 
• 接受所有的字串(只有這裡與前者不同)
• $M_2$
• 如果$M$接受字串$w$ ，則$M_2$接受所有的字串；
• 如果$M$拒絕字串$w$，則$M_2$拒絕所有的字串 

多一歸約可證出的結論

一個語言$A$和他的補集$A'$只可能有三種情況

1. $A$和$A'$都是可決定語言，例如
• $A_{DFA}$ ($A_{NFA}$、$A_{REX}$)
• $A_{CFG}$
• $E_{DFA}$
• $E_{CFG}$
• $EQ_{DFA}$  
• 注意：$EQ_{CFG}$是不可決定語言，因為EQ比較「難」
2. $A$和$A'$都不是圖靈可辨識語言，例如：$EQ_{TM}$
3. $A$是「圖靈可辨識」語言，但是是「不可決定性」語言 ，而$A'$不是圖靈可辨識語言，例如
1. $A_{TM}\  \underleftrightarrow{\tiny complement} \ A_{TM}'$ (右側是co-Turing-recognizable，較難)
2. $E_{TM}'\  \underleftrightarrow{\tiny complement} \ E_{TM}$ 
3. $EQ_{CFG}'\  \underleftrightarrow{\tiny complement} \ EQ_{CFG}$ 

各種語言的「難度」示意圖

• A language L is decidable if and only if both L and L' are Turing-recognizable. 
• Language L is called co-Turing-recognizable, if L' is Turing-recognizable. $A_{TM}'$ is an example of co-Turing-recognizable language. 
• Every decidable language is co-Turing-recognizable

References

Mapping Reducibility
http://www.cs.rit.edu/~ib/Classes/CS389_Winter08-09/Slides/Ch5-3-MappingReducibility.pdf

wiki - 可計算函數
http://zh.wikipedia.org/wiki/可计算函数

wiki - 歸約
http://zh.wikipedia.org/wiki/歸約

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