## Formal Language - Ch14 多一歸約 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.

$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}$

$EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable

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

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

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/歸約