第1章　導入
　　1.1　一番大切な定義
　　1.2　自然数,表記の約束
　　1.3　部分関数
　　1.4　関数プログラム
　　1.5　現実のC言語との相違
　　1.6　再び,一番大切な定義
　　1.7　計算の理論の概観
　　第1章の章末問題

第2章　ジャンププログラム
　　2.1　準備
　　2.2　ジャンププログラム
　　2.3　ジャンププログラムへの書換え
　　2.4　特定形プログラム
　　第2章の章末問題

第3章　万能関数
　　3.1　自然数のペアのコード化
　　3.2　自然数の有限列のコード化
　　3.3　ジャンププログラムのコード化
　　3.4　万能関数
　　第3章の章末問題

第4章　計算可能・不可能の境界付近
　　4.1　対角線論法
　　4.2　停止問題の決定不可能性
　　4.3　パラメータ定理
　　4.4　再帰定理
　　4.5　ライスの定理
　　第4章の章末問題

第5章　原始帰納的関数
　　5.1　原始帰納的関数とは
　　5.2　原始帰納的関数の定義
　　5.3　具体例
　　5.4　while文のないプログラム
　　5.5　限定反復プログラム
　　5.6　限定反復プログラムから原始帰納的関数へ
　　5.7　原始帰納的でない計算可能関数
　　第5章の章末問題

第6章　帰納的部分関数
　　6.1　準備
　　6.2　帰納的部分関数,帰納的述語
　　6.3　「計算可能」との同値性
　　6.4　クリーネの標準形定理
　　6.5　最小化に関する注意
　　第6章の章末問題

第7章　半決定可能集合
　　7.1　集合を扱うことについて
　　7.2　集合を半決定するプログラム
　　7.3　集合を枚挙するプログラム
　　7.4　さまざまな同値な条件
　　第7章の章末問題

第8章　計算不可能性の度合い
　　8.1　量化の重なり具合による比較
　　8.2　算術的階層
　　8.3　万能述語,そして算術的階層が潰れないこと
　　8.4　還元可能性による比較
　　8.5　完全集合
　　第8章の章末問題

第9章　チューリング機械
　　9.1　チューリング機械とは
　　9.2　正確な定義
　　9.3　具体例
　　9.4　自然数上の関数の計算可能性
　　9.5　チューリング機械の変種
　　9.6　万能チューリング機械
　　9.7　計算不可能性：ビジービーバー関数,ポストの対応問題
　　第9章の章末問題

第10章　P≠NP予想
　　10.1　ハミルトン閉路問題
　　10.2　多項式時間計算可能性
　　10.3　非決定性チューリング機械
　　10.4　P≠NP予想の正確な内容
　　10.5　多項式時間還元可能性
　　10.6　NP完全問題
　　第10章の章末問題

第11章　ラムダ計算
　　11.1　導入
　　11.2　ラムダ項
　　11.3　ベータ簡約
　　11.4　チャーチ-ロッサーの定理
　　11.5　簡約の標準的な順番と最左簡約
　　11.6　自然数上の関数の計算と決定不可能問題
　　11.7　型付きラムダ計算
　　第11章の章末問題

付録A　チューリング機械シミュレータ
付録B　ラムダ計算の定理の詳細な証明
　　B.1　チャーチ-ロッサーの定理
　　B.2　簡約順番の標準化定理
　　B.3　帰納的部分関数のラムダ項による計算

章末問題略解
参考文献
索引