８　テューリング機械入門
8.1　コンピュータで解けない問題
8.2　テューリング機械
8.3　テューリング機械のプログラム技法
8.4　基本テューリング機械の拡張
8.5　制限されたテューリング機械
8.6　テューリング機械とコンピュータ
8.7　第８章の要約
8.8　第８章の参考文献

９　決定不能性
9.1　帰納的可算でない言語
9.2　帰納的可算な決定不能問題\r
9.3　テューリング機械の決定不能問題\r
9.4　ポストの対応問題
9.5　他の決定不能問題\r
9.6　第９章の要約
9.7　第９章の参考文献

10　実行不能な問題
10.1　クラスＰとクラスＮＰ
10.2　最初のＮＰ完全問題
10.3　制限された形の充足可能性問題
10.4　その他のＮＰ完全問題
10.5　第10章の要約
10.6　第10章の参考文献

11　その他の「問題のクラス」
11.1　ＮＰに属す言語の補集合
11.2　多項式領域で解ける問題
11.3　ＰＳに対して完全な問題
11.4　乱数を利用して定義される言語のクラス
11.5　素数性判定問題の計算量
11.5　第11章の要約
11.6　第11章の参考文献

索引