チューリングマシンが受理する言語 - オタクof数理の共同ブログ

こんにちは, よねすけです.

今回はチューリングマシンの話を書きたいと思います. 以下チューリングマシンをTMと省略します.

帰納的可算集合(Recursively Enumerable)

言語 $L$ が帰納的可算集合であるとは, あるTM $M$ によって

$L=L(M)$ と書けることを言います. この集合を ${\rm RE}$ と書く事があります.

帰納的集合(Recursive)

言語 $L$ が帰納的集合であるとは, ある必ず止まるTM $M$ によって

$L=L(M)$ と書けることを言います. この集合を ${\rm R}$ と書くことがあります. この定義から明らかなように ${\rm R}\subset{\rm RE}$ が分かります. ${\rm R}$ に含まれる言語は必ず止まるTMによって認識出来るので可解であることも分かります.
このような言語は色々あります. 一番簡単な言語はalphabet $\sum$ からなる列全体を集めた次の言語 $L_3=\sum^*$ じゃないでしょうか. これを認識するTMはすべての入力に対して初期状態と受理状態を一致させることによって設計できます. 状態遷移図は次のようになります.

f:id:otaku_of_suri:20170127135742p:plain

このときTMは1ステップで必ず止まるので $L_3$ は帰納的集合であることが分かります.

このような集合の他にそもそもTMで認識出来ない集合もあります. そのような言語の例として空集合問題や対角線言語があります. 空集合問題において考える言語は

$L_e=\{M|L(M)=\phi\}$ です. 空集合問題は一般に非可解である, すなわち ${\rm R}$ に含まれないことはよく知られていますが, ${\rm RE}$ にすら実は含まれないということはとても驚きでした.
対角線言語において考える言語は $L_d=\{\sigma_i|{\rm TM}\sigma_iは\sigma_iを受理しない\}$ です. この言語が対角線論法を用いて示されることでも有名です.

それでは