ポストの問題
「ポストの対応問題」とはべつもの
問題
算術的階層.iconの図の②の中の全ての集合の間で$ \equiv_Tが成り立つか？
②の領域に属するのは、計算不可能かつ半決定可能な集合たち
ref 『C言語による計算の理論』.icon p.127
↑の2つが同じ問題を指していて、ただ別の言い方をしているだけなのかはわからんmrsekut.icon
結論
成り立たない
つまり、計算不可能かつ半決定可能な集合$ \alpha,\betaで$ \alpha\equiv_T\betaとなるものが存在する
この同値類の中で$ \le_mや$ \le_Tが最大の同値類に属する集合$ \varphiが存在し、これのことを完全集合と言う 関連する定理
計算可能集合全体は
$ \equiv_Tで1つの同値類になる
$ \equiv_mで3つの同値類になる
$ \emptysetと$ \mathbb{N}とその他に分けられる
算術的階層の①に限った場合の同値類mrsekut.icon 証明
計算可能集合内の集合$ \alpha,\betaについて論じる
$ \equiv_Tについて
$ \alphaが計算可能ならばどんな$ \betaに対しても$ \alpha\le_T\betaである
したがって計算可能集合のあいだでは全て$ \equiv_Tが成り立つ
$ \equiv_mについて
$ \alphaが計算可能で、$ \emptyset\subsetneq \beta\subseteq\mathbb{N}ならば$ \alpha\le_m\betaが成り立つ
なぜなら$ x\in\beta,y\notin\betaとなる$ x,yが存在するので、
それを使って以下のような関数$ fを定義すればいい
$ f(z) = \left\{ \begin{array}{ll} x & (z\in\alpha) \\ y & (z\notin\alpha) \\ \end{array} \right.
これは、$ \alphaの特性関数の戻り値の1/0をx/yに変更したものである
https://gyazo.com/fd1c758bd37469ae1d71c70d5c64822a
$ yは$ \betaの外ならどこにいてもいいので、複数描いてるmrsekut.icon
したがって$ \emptysetでも$ \mathbb{N}でもない計算可能集合の間では全て$ \equiv_mが成り立つ
一方、
$ \alpha\le_m\emptysetが成り立つのは$ \alpha=\emptysetのときだけであり
$ \alpha\le_m\mathbb{N}が成り立つのは$ \alpha=\mathbb{N}のときだけである
したがって
$ \emptysetとの間で$ \equiv_mが成り立つのは$ \emptysetだけであり、
$ \mathbb{N}との間で$ \equiv_mが成り立つのは$ \mathbb{N}だけである
参考