計算理論と数理論理学
著：田中 一之
内容紹介
本書は「計算理論」と「数理論理学」を同時に学ぶための、学部上級から大学院初年級レベルの教科書あるいは独習書である。背景の説明も充実しているので、幅広くリファレンスとしても活用できる。
両分野を同時に学ぶといっても、単に両分野の共通項を括り出したり類似性を強調したりするのではなく、それぞれの違いは違いとして認めながら、両分野の稜線に立って壮大な景色を展望している。
時間的な広がりにおいても、1960年代のクリプキの許容可能順序数の理論から、最近のパリティゲームの無記憶決定性の証明まで、あまり一般向けの解説がないような話題も掘り起こして著者独自目線で数理論理学と計算理論の広がりを描いている。
目次
第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 α再帰理論と再帰的巨大順序数
文献案内
問題解答
あとがき
用語索引
記号索引
ISBN：9784320114722
。出版社：共立出版
。判型：A5
。ページ数：312ページ
。定価：4200円（本体）
。発行年月日：2022年06月
。発売日：2022年06月24日
。国際分類コード【Thema（シーマ）】 １：PB。
