1　序論：計算のモデル
2　言語理論の基礎
2-1　言語と書き替えシステム
2-2　文法
2-3　Postシステム
2-4　Morkovアルゴリズム
2-5　Lシステム
2-6　演習問題
3　制限つきオートマトン
3-1　有限オートマトン
3-2　Kleeneの特徴づけ
3-3　汎順序機械
3-4　反復補題
3-5　プッシュダウン・オートマトン
3-6　演習問題
4　テューリング機械と帰納的関数
4-1　汎用性の高い計算モデル
4-2　機械語のプログラミング，Churchの仮説，万能機械
4-3　帰納定理と基本的な決定不能性の結果
4-4　帰納的集合と帰納的言語，帰納的可算集合と帰納的可算言語
4-5　還元可能性と創造的集合
4-6　合成に基づく万能性
4-7　演習問題
5　有名な決定問題
5-1　Postの対応問題とその応用
5-2　Hilbertの第10問題とその帰結：ほとんどの問題は多項式で表現できる
5-3　語の問題とベクトル加算系
5-4　演習問題
6　計算の複雑さ
6-1　基本概念と公理的理論
6-2　計算量のクラス，間隙定理，圧縮定理
6-3　加速定理，最良アルゴリズムを持たない関数
6-4　時間有界，クラスTとNT，NT完全問題
6-5　手に負えないという証明つきの問題
6-6　領域尺度とトレード・オフ
6-7　演習問題
7　暗号学
7-1　背景と古典的な暗号系
7-2　公開鍵暗号系
7-3　ナップザック・システム
7-4　RSAシステム
7-5　通信における不可能に思える問題を解くプロトコル
7-6　演習問題
8　オートマトン・言語理論における動向
8-1　ペトリ・ネット
8-2　類似な文法と言語
8-3　鼓動型オートマトン
8-4　演習問題