読者です 読者をやめる 読者になる 読者になる

オタクof数理の共同ブログ

京大情報学科数理工学コースの学生4人による共同ブログです

チューリングマシンが受理する言語

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

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

帰納可算集合(Recursively Enumerable)

言語L帰納可算集合であるとは, あるTMMによって

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

帰納的集合(Recursive)

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

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を受理しない\}
です. この言語が対角線論法を用いて示されることでも有名です.

それでは