還元可能性
reducibility
何らかの問題を、チューリングマシンの停止性問題に帰着させることで、その問題の決定不能であることを導ける 2つの集合$ \alpha,\betaの計算不可能性の度合いを比較する
$ \alphaが$ \betaに還元可能であるとき、$ \alpha\le\betaのように表記する
$ \betaが計算可能である仮定すると、$ \alphaも計算可能になる
$ \betaの方が$ \alphaより計算不可能性の度合いが高いmrsekut.icon
難しい方へ還元(帰着)するmrsekut.icon
いくつかの還元の方法
$ \beta=\overline{\mathrm{HaltPair}}は③の領域
例えば②の中の集合$ \alphaと、③の中の集合$ \betaが$ \alpha\equiv_m\betaとなることはないという主張
「帰着の方向」と、上の定義の「写像の方向」が逆転しているのが、非直感的で最初わかりにくかったmrsekut.icon
$ Aから$ Bへ帰着可能」というときは、$ Bの方が同等以上に難しい
簡単なものから難しいものへ帰着する
今知りたいのは$ B
既知の$ Aからの全域関数を考えることで、$ Bについて間接的に知ることができる でもこれって全射かどうかは言ってないから、$ Bの方で漏れがあったりしないのか #?? 定義的には漏れがあろうが、写像が示せれば$ Aの全てに対しては対応が取れたことになるのでそれで十分なのかなmrsekut.icon
参考