目次 概要 判定不可能な言語 証明 証明 対角線論法 証明 参考資料 概要 今回は以下に示す言語が判定不可能であり、その補集合が認識不可能であることを示していきます。 その次に、証明に関連して対角線論法について説明します。 判定不可能な言語 上記の が…

久しぶりの更新です. 今回は先日 AOJ 上で開催された早稲田大学プログラミングコンテスト 2020 の D 問題の思考フローに伴い, 群論を軽くつまみ食いしようと思います. （簡単のため, 定理等の詳細な説明を省いたり, 厳密性を欠く記述が見受けられると思いま…

競プロ記事初投稿です.今回はAtCoderで入水するまでにやったことを時系列でまとめていきたいと思います.まずはレートの変遷と累計AC数のグラフを見てみましょう. レートの変遷 AC数の変遷 僕が競プロを始めたのは1年と半年ほど前です.周りがやってて楽しそう…

今回私は某大学の某実験において五目並べのGUIアプリを作成しました。一月半という長い間格闘していたわけですが、その中でドツボにハマって時間を溶かした事案を書き連ねていきます。 ①ObjectInputStreamのインスタンスはObjectOutputStreamのインスタンス…

クラスPとNPについてのお話を試験前最後の記事とさせていただきます。 まず、クラスとは何か。しっかりと定義するのはとてもこの1記事では収まり切りません。そのため、「クラスはものの集まり」程度に思っておいてくれるといいかな、と思います。（あくまで…

今回はチューリング機械の決定可能性に関する話です。 目次 受理・認識・決定（判定） 決定可能（判定可能）言語 受理・認識・決定（判定） 下図に示すようなことを説明していきます。（ ではないです） 認識と決定の違い 計算状況についての記事で最後に触…

こんにちは。いつぞやに計算状況の記事を書きましたが、その定義を使って窓について考えると「んん・・・？」ってなります。私がなりました。そこで今回は、窓の書き方に合わせた計算状況を導入した後、合法な窓と非合法な窓について例示していきます。 第2…

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

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

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

こんばんは。前回は講義の概略をお話ししましたが、今回はチューリング機械の導入をしていこうと思います。今回の話は形式的定義および計算状況に限ったものなので、計算可能性にかかわる本質的（と思われる）な話は次回以降の記事になります。 注意 現状、 …

これは私個人の経験則なのですが、講義の内容が何に役立つのかが見えて来ず、それゆえ勉強に身が入らないということが少なからずあると思います。そこで今日はこの講義で学ぶ内容はそもそもどういった分野に属しているのか、特にチューリングマシンはどうい…

このブログは某大学の"情報数学B"の授業を元にしたものとなっています。私自身の認識を、このページをご覧の皆様と共有し、アウトプットの場とすることが目的です。可能な限り間違いのない記述をするよう努めますが如何せん私自身の理解が浅いもので、読んで…