エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
チューリングマシンが受理する言語 - オタクof数理の共同ブログ
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
チューリングマシンが受理する言語 - オタクof数理の共同ブログ
こんにちは, よねすけです. 今回はチューリングマシンの話を書きたいと思います. 以下チューリングマシ... こんにちは, よねすけです. 今回はチューリングマシンの話を書きたいと思います. 以下チューリングマシンをTMと省略します. 帰納的可算集合(Recursively Enumerable) 言語が帰納的可算集合であるとは, あるTMによって と書けることを言います. この集合をと書く事があります. 帰納的集合(Recursive) 言語が帰納的集合であるとは, ある必ず止まるTMによって と書けることを言います. この集合をと書くことがあります. この定義から明らかなようにが分かります. に含まれる言語は必ず止まるTMによって認識出来るので可解であることも分かります. このような言語は色々あります. 一番簡単な言語はalphabetからなる列全体を集めた次の言語じゃないでしょうか. これを認識するTMはすべての入力に対して初期状態と受理状態を一致させることによって設計できます. 状態遷移図