I　計算理論とは
1　すべては計算から始まる
　　1.1　計算理論の誕生と展開
　　1.2　この本の学び方

2　計算理論のための概念や用語
　　2.1　集合
　　2.2　系列と言語
　　2.3　関数と問題
　　2.4　グラフ
　　2.5　論理演算とド・モルガンの法則
　　2.6　定理と証明
　　2.7　再帰
　　2.8　アルゴリズムの記述
　　問題

II　有限オートマトン，プッシュダウンオートマトン，そして文脈自由文法
3　有限オートマトン
　　3.1　有限オートマトンの導入
　　3.2　非決定性有限オートマトン
　　3.3　決定性有限オートマトンと非決定性有限オートマトンの等価性
　　3.4　正規表現
　　3.5　有限オートマトンの受理能力の限界
　　問題

4　文脈自由文法
　　4.1　文脈自由文法の導入
　　4.2　文脈自由文法と導出のあいまいさ
　　4.3　チョムスキーの標準形
　　4.4　文脈自由文法の言語生成能力の限界
　　4.5　さまざまな形式文法
　　問題

5　プッシュダウンオートマトン
　　5.1　プッシュダウンオートマトンの導入
　　5.2　プッシュダウンオートマトンと文脈自由文法の等価性
　　問題

III　計算可能性
6　チューリング機械
　　6.1　チューリング機械の基本
　　6.2　チューリング機械のロバスト性
　　6.3　チャーチ・チューリングの提唱
　　問題

7　チューリング機械の万能性とその限界
　　7.1　万能チューリング機械
　　7.2　停止問題の決定不能性
　　7.3　帰着
　　7.4　ポストの対応問題
　　問題

IV　計算の複雑さ
8　クラスPとクラスNP
　　8.1　現実的に計算できる問題とできない問題の例
　　8.2　時間を限定した計算
　　8.3　クラスPとクラスNP
　　8.4　クラスEXP
　　8.5　アルゴリズムの計算時間の評価
　　問題

9　論理回路に基づいた計算時間限定の計算
　　9.1　非決定性チューリング機械の論理式による模倣のあらまし
　　9.2　論理回路と離散回路
　　9.3　決定性チューリング機械を模倣する論理回路
　　9.4　非決定性チューリング機械を模倣する論理回路
　　9.5　論理回路を模倣する論理式
　　問題

10　NP完全性
　　10.1　NP完全の定義
　　10.2　さまざまなNP完全問題
　　問題

解答
文献
おわりに
索引