Part I 数学的基礎
このパートは、本書全体で使う言葉と読み方をそろえる入口です。第1章〜第3章を通じて、集合・論理・証明・計算モデル・形式言語という基礎語彙を共有し、後続の「何が計算できるか」「どこまで効率化できるか」という議論を読める状態を作ります。
このパートで得るもの
- 定義・定理・証明を読むための最小限の数学的共通語彙
- 計算を機械として表現する視点と、その能力を言語として比較する視点
- 第4章以降で前提になる「モデル」「表現力」「限界」という見方
通し例: 安全なメッセージ配送基盤
このパートでは、安全なメッセージ配送基盤の「入力をどう定義し、どこまで機械的に読める形へ落とせるか」を見ます。メッセージの記法、入力バリデーション、簡単なコマンド文法を題材にすると、第1章〜第3章の役割分担を追いやすくなります。
なぜこの順番か
- 第1章で記法・論理・証明技法をそろえ、以後の章で使う文法を共有する
- 第2章でチューリング機械を導入し、「計算とは何か」を一般モデルとして定義する
- 第3章でより制約の強いオートマトンへ下り、計算能力の差を言語クラスとして読む
この順番により、「数学の準備」→「計算一般のモデル」→「制約付きモデルの階層」という流れで理解を積み上げられます。
読み飛ばしの目安
- 学部講義などで DFA / NFA / CFG / PDA をすでに一通り学んでいるなら、第1章は復習として薄く読み、第2章・第3章を優先して構いません
- 逆に、証明や論理記号に不安があるなら、第1章を飛ばさない方が後半の理解コストを下げられます
- 迷った場合は、まず第1章と第2章を読み、第3章は 付録C の演習と往復しながら進めるのが安全です
章の役割
- 第1章 数学的基礎: 本書全体の文法を与える
- 第2章 計算理論の基礎: 計算可能性を議論するための標準モデルを与える
- 第3章 形式言語とオートマトン理論: 言語クラスごとの表現力の差を可視化する
次のパートへの接続
Part I を読み終えると、「どのモデルで何を表せるか」は見えるようになります。Part II ではそこから一歩進み、「そもそも解けるのか」「解けるとしてどこまで効率化できるのか」を、決定不能性・複雑性・アルゴリズム解析の観点で扱います。