| 第1章 導入 1 |
| 1.1 一番大切な定義 2 |
| 1.2 自然数，表記の約束 4 |
| 1.3 部分関数 6 |
| 1.4 関数プログラム 9 |
| 1.5 現実のC言語との相違 14 |
| 1.6 再び，一番大切な定義 17 |
| 1.7 計算の理論の概観 20 |
| 第1章の章末問題 21 |
| 第2章 ジャンププログラム 23 |
| 2.1 準備 24 |
| 2.2 ジャンププログラム 25 |
| 2.3 ジャンププログラムへの書換え 27 |
| 2.4 特定形プログラム 37 |
| 第2章の章末問題 38 |
| 第3章 万能関数 39 |
| 3.1 自然数のペアのコード化 40 |
| 3.2 自然数の有限列のコード化 41 |
| 3.3 ジャンププログラムのコード化 45 |
| 3.4 万能関数 47 |
| 第3章の章末問題 52 |
| 第4章 計算可能・不可能の境界付近 53 |
| 4.1 対角線論法 54 |
| 4.2 停止問題の決定不可能性 57 |
| 4.3 パラメータ定理 59 |
| 4.4 再帰定理 61 |
| 4.5 ライスの定理 64 |
| 第4章の章末問題 66 |
| 第5章 原始帰納的関数 67 |
| 5.1 原始帰納的関数とは 68 |
| 5.2 原始帰納的関数の定義 69 |
| 5.3 具体例 71 |
| 5.4 while文のないプログラム 77 |
| 5.5 限定反復プログラム 79 |
| 5.6 限定反復プログラムから原始帰納的関数へ 82 |
| 5.7 原始帰納的でない計算可能関数 85 |
| 第5章の章末問題 88 |
| 第6章 帰納的部分関数 89 |
| 6.1 準備 90 |
| 6.2 帰納的部分関数，帰納的述語 91 |
| 6.3 「計算可能」との同値性 95 |
| 6.4 クリーネの標準形定理 96 |
| 6.5 最小化に関する注意 101 |
| 第6章の章末問題 104 |
| 第7章 半決定可能集合 105 |
| 7.1 集合を扱うことについて 106 |
| 7.2 集合を半決定するプログラム 107 |
| 7.3 集合を枚挙するプログラム 108 |
| 7.4 さまざまな同値な条件 110 |
| 第7章の章末問題 114 |
| 第8章 計算不可能性の度合い 115 |
| 8.1 量化の重なり具合による比較 116 |
| 8.2 算術的階層 117 |
| 8.3 万能述語，そして算術的階層が潰れないこと 121 |
| 8.4 還元可能性による比較 124 |
| 8.5 完全集合 127 |
| 第8章の章末問題 130 |
| 第9章 チューリング機械 131 |
| 9.1 チューリング機械とは 132 |
| 9.2 正確な定義 135 |
| 9.3 具体例 136 |
| 9.4 自然数上の関数の計算可能性 139 |
| 9.5 チューリング機械の変種 143 |
| 9.6 万能チューリング機械 144 |
| 9.7 計算不可能性 : ビジービーバー関数，ポストの対応問題 145 |
| 第9章の章末問題 149 |
| 第10章 P≠NP予想 151 |
| 10.1 ハミルトン閉路問題 152 |
| 10.2 多項式時間計算可能性 155 |
| 10.3 非決定性チューリング機械 158 |
| 10.4 P≠NP予想の正確な内容 160 |
| 10.5 多項式時間還元可能性 161 |
| 10.6 NP完全問題 163 |
| 第10章の章末問題 164 |
| 第11章 ラムダ計算 165 |
| 11.1 導入 166 |
| 11.2 ラムダ項 167 |
| 11.3 ベータ簡約 169 |
| 11.4 チャーチ－ロッサーの定理 172 |
| 11.5 簡約の標準的な順番と最左簡約 175 |
| 11.6 自然数上の関数の計算と決定不可能問題 177 |
| 11.7 型付きラムダ計算 179 |
| 第11章の章末問題 182 |
| 付録A チユーリング機械シミュレータ 183 |
| 付録B ラムダ計算の定理の詳細な証明 186 |
| B.1 チャーチ－ロッサーの定理 186 |
| B.2 簡約順番の標準化定理 191 |
| B.3 帰納的部分関数のラムダ項による計算 197 |
| 章末問題略解 201 |
| 参考文献 208 |
| 索引 209 |
図書
図書
図書
