ところで今日はセンター試験当日だったみたいですね。 なんだか英語のリスニングで野菜のモンスターが話題になったようなので僕も真似してみました。ご査収ください。

今回は句構造文法（生成規則 に対する制限がない文法）と万能TMについてお話していきます。 目次 句構造文法とTM 万能TM 句構造文法とTM 証明のお気持ちは上図にほとんど集約されています。 TM を、句構造文法 の開始記号 および を入力とし、 に対する書き…

※結構長くなります 目次 概要 計算能力の等価性の証明 1. 片側無限テープTM 2. kテープTM 3. 決定性TM まとめ 概要 今回はチューリング機械(以降TMと表記します)の様々なモデルについて扱っていきます。今回扱うモデルは３つ。 1. 片側無限テープTM 2. 多テ…