ポストの問題
「ポストの対応問題」とはべつもの
問題
ref wiki
②の領域に属するのは、計算不可能かつ半決定可能な集合たち
ref 
p.127
↑の2つが同じ問題を指していて、ただ別の言い方をしているだけなのかはわからん
wikiの方が何を言っているか??
結論
成り立たない
つまり、計算不可能かつ半決定可能な集合\alpha,\betaで\alpha\equiv_T\betaとなるものが存在する
各領域の中に無限個の同値類が存在する
関連する定理
計算可能集合全体は
\equiv_Tで1つの同値類になる
\equiv_mで3つの同値類になる
\emptysetと\mathbb{N}とその他に分けられる
算術的階層の①に限った場合の同値類
多対一還元#5fb7cadd1982700000fbcccdらへんの延長の話
証明
計算可能集合内の集合\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に変更したものである
yは\betaの外ならどこにいてもいいので、複数描いてる
このfが帰着関数になる
したがって\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}だけである
参考
『C言語による計算の理論』 8.4