ポストの問題

Emil Leon Postが定期

Richard M. FriedbergとAlbert Abramovich Muchnikによって証明

「ポストの対応問題」とはべつもの

問題

停止性問題よりもチューリング次数が低い計算不可能な帰納的可算集合が存在するか

ref wiki

算術的階層の図の②の中の全ての集合の間で$$\equiv_T$$が成り立つか？

②の領域に属するのは、計算不可能かつ半決定可能な集合たち

ref 『C言語による計算の理論』 p.127

↑の2つが同じ問題を指していて、ただ別の言い方をしているだけなのかはわからんmrsekut

wikiの方が何を言っているか??

結論

成り立たない

つまり、計算不可能かつ半決定可能な集合$$\alpha,\beta$$で$$\alpha\equiv_T\beta$$となるものが存在する

各領域の中に無限個の同値類が存在する

この同値類の中で$$\le_m$$や$$\le_T$$が最大の同値類に属する集合$$\varphi$$が存在し、これのことを完全集合と言う

廣瀬「計算論」や廣瀬「帰納的関数」に証明が載っているらしい

関連する定理

計算可能集合全体は

$$\equiv_T$$で1つの同値類になる

$$\equiv_m$$で3つの同値類になる

$$\emptyset$$と$$\mathbb{N}$$とその他に分けられる

算術的階層の①に限った場合の同値類mrsekut

多対一還元#fbcccdらへんの延長の話mrsekut

証明

計算可能集合内の集合$$\alpha,\beta$$について論じる

$$\equiv_T$$について

$$\alpha$$が計算可能ならばどんな$$\beta$$に対しても$$\alpha\le_T\beta$$である

∵チューリング還元の定義よりmrsekut

したがって計算可能集合のあいだでは全て$$\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$$の外ならどこにいてもいいので、複数描いてるmrsekut

この$$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