可计算函数
一个函数 f:Σ∗→Σ∗ 是一个可计算函数,如果存在一个 Turing 机对每个输入 w 停机且将 f(w) 写在条带上。
语言 A 可映射归约为 B(A≤mB),如果存在一个可计算函数 f:Σ∗→Σ∗ 且对于每个 w 都有
w∈A⇔f(w)∈B
一种重要的归约方法是利用计算历史。
归约的推论
- A≤mB 与 Aˉ≤mBˉ 等价
- 如果 A≤mB 且 B 可判定,那么 A 可判定
- 如果 A≤mB 且 A 不可判定,那么 B 不可判定
- 如果 A≤mB 且 B 可识别,那么 A 可识别
- 如果 A≤mB 且 A 不可识别,那么 B 不可识别
- 如果 A 可判定,那么 A≤mB 只要 B=∅,Σ∗
- ATM 可归约为 HALTTM
- ATM 可归约为 ETM
- ATM 可归约为 REGULARTM
- ETM 可归约为 EQTM
- 利用归约,可以证明 EQTM 既不是 T-可识别的,也不是 T-余可识别的。
相关内容
参考文献