2015年5月26日 星期二

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

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





技術提供:Blogger.