映射归约

阐述

可计算函数

一个函数 $f:\Sigma^*\to\Sigma^*$ 是一个可计算函数，如果存在一个 Turing 机对每个输入 $w$ 停机且将 $f(w)$ 写在条带上。

定义

语言 A 可映射归约为 B（$A\le_m B$），如果存在一个可计算函数 $f:\Sigma^*\to\Sigma^*$ 且对于每个 $w$ 都有

$$w\in A\Leftrightarrow f(w)\in B$$

一种重要的归约方法是利用计算历史。

归约的推论

• $A\le_m B$ 与 $\bar A\le_m \bar B$ 等价
• 如果 $A\le_m B$ 且 B 可判定，那么 A 可判定
• 如果 $A\le_m B$ 且 A 不可判定，那么 B 不可判定
• 如果 $A\le_m B$ 且 B 可识别，那么 A 可识别
• 如果 $A\le_m B$ 且 A 不可识别，那么 B 不可识别
• 如果 A 可判定，那么 $A\le_m B$ 只要 $B\ne\emptyset, \Sigma^*$

实例

• $A_{\rm TM}$ 可归约为 $HALT_{\rm TM}$
• $A_{\rm TM}$ 可归约为 $E_{\rm TM}$
• $A_{\rm TM}$ 可归约为 $REGULAR_{\rm TM}$
• $E_{\rm TM}$ 可归约为 $EQ_{\rm TM}$
• 利用归约，可以证明 $EQ_{\rm TM}$ 既不是 T-可识别的，也不是 T-余可识别的。

性质

相关内容

参考文献