2019-01-01から1ヶ月間の記事一覧
クラスPとNPについてのお話を試験前最後の記事とさせていただきます。 まず、クラスとは何か。しっかりと定義するのはとてもこの1記事では収まり切りません。そのため、「クラスはものの集まり」程度に思っておいてくれるといいかな、と思います。(あくまで…
今回はチューリング機械の決定可能性に関する話です。 目次 受理・認識・決定(判定) 決定可能(判定可能)言語 受理・認識・決定(判定) 下図に示すようなことを説明していきます。( ではないです) 認識と決定の違い 計算状況についての記事で最後に触…
こんにちは。いつぞやに計算状況の記事を書きましたが、その定義を使って窓について考えると「んん・・・?」ってなります。私がなりました。そこで今回は、窓の書き方に合わせた計算状況を導入した後、合法な窓と非合法な窓について例示していきます。 第2…
ところで今日はセンター試験当日だったみたいですね。 なんだか英語のリスニングで野菜のモンスターが話題になったようなので僕も真似してみました。ご査収ください。
今回は句構造文法(生成規則 に対する制限がない文法)と万能TMについてお話していきます。 目次 句構造文法とTM 万能TM 句構造文法とTM 証明のお気持ちは上図にほとんど集約されています。 TM を、句構造文法 の開始記号 および を入力とし、 に対する書き…
※結構長くなります 目次 概要 計算能力の等価性の証明 1. 片側無限テープTM 2. kテープTM 3. 決定性TM まとめ 概要 今回はチューリング機械(以降TMと表記します)の様々なモデルについて扱っていきます。今回扱うモデルは3つ。 1. 片側無限テープTM 2. 多テ…