計算理論と数理論理学
田中 一之 著
内容
目次
第1章 計算理論入門 1.1 オートマトンとモノイド 1.2 チューリング機械 1.3 計算可能な関数と原始再帰的関数 1.4 計算可能性と不可能性 1.5 再帰的部分関数とCE集合 1.6 ライスの定理と多対一還元 第2章 命題論理と計算の複雑さ 2.1 トートロジーと証明 2.2 命題論理の完全性 2.3 NP完全問題 2.4 グラフに関するNP完全問題 2.5 時間限定と領域限定のクラス 2.6 階層定理 2.7 PSPACE完全とTQBF 第3章 1階論理と決定問題 3.1 1階論理とは 3.2 スコーレムの定理 3.3 エーレンフォイヒト・フライセのゲーム 3.4 プレスバーガー算術の決定可能性 3.5 1階算術と論理式の階層 3.6 計算可能性理論と第一不完全性定理 3.7 第二不完全性定理 第4章 2階論理と無限オートマトン 4.1 2階論理 4.2 2階算術と解析的階層 4.3 無限列上のオートマトン 4.4 ωオートマトンとS1S 4.5 木オートマトンとS2S 4.6 有限モデル論 4.7 パリティゲームの無記憶決定性 第5章 階層理論と許容集合 5.1 オラクル計算と相対化 5.2 m還元と単純集合 5.3 T還元とポストの問題 5.4 算術的階層と多項式時間階層 5.5 解析的階層と記述集合論 5.6 クリプキ・プラテックの集合論 5.7 α再帰理論と再帰的巨大順序数 文献案内 問題解答 あとがき 用語索引 記号索引
