1.機械と言語
1.1 語と言語
1.2 対応，関係，グラフ
1.3 問題と符号化
練習問題1
2.Turing機械
2.1 多テープTuring機械
2.2 Turing機械のプログラムによる表現
2.3 単テープTuring機械
練習問題2
3.計算可能性
3.1 可算，帰納的可算，計算可能性
3.2 万能Turing機械
3.3 計算不能な問題
練習問題3
4.計算機モデル論
4.1 非決定性機械
4.2 交互機械
4.3 多プッシュダウン機械
4.4 ランダム・アクセス機械
4.5 計数器機械と帰納的関数
練習問題4
5.形式言語
5.1 生成文法
5.2 正則集合
5.3 文脈自由言語
5.4 0型言語と1型言語
5.5 文脈自由文法に関する計算不能問題
練習問題5
6.基本定理
6.1 線形加速定理
6.2 構成可能関数
6.3 時間量と領域量の関係
6.4 2テープTuring機械
6.5 階層定理
6.6 対数領域と多項式時間
7.完全問題
7.1 実際的計算可能性
7.2 完全問題
7.3 NP完全問題
7.4 PSPASE完全問題
7.5 EXPTIME完全問題
7.6 P完全問題とNL完全問題
7.7 詰め込み論法と未解決問題
練習問題7
練習問題解答
索　　引