計算理論と数理論理学

ホーム > 数理・科学 > 書籍

4,620円(税420円)

商品の説明

タイトル
計算理論と数理論理学
ISBN/JAN
9784320114722
著者
田中一之
出版社
共立出版
発売日
2022/06/24
商品説明
本書は「計算理論」と「数理論理学」を同時に学ぶための、学部上級から大学院初年級レベルの教科書あるいは独習書である。背景の説明も充実しているので、幅広くリファレンスとしても活用できる。両分野を同時に学ぶといっても、単に両分野の共通項を括り出したり類似性を強調したりするのではなく、それぞれの違いは違いとして認めながら、両分野の稜線に立って壮大な景色を展望している。時間的な広がりにおいても、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　ωオートマトンとS1S4.5　木オートマトンとS2S4.6　有限モデル論4.7　パリティゲームの無記憶決定性第5章　階層理論と許容集合5.1　オラクル計算と相対化5.2　m還元と単純集合5.3　T還元とポストの問題5.4　算術的階層と多項式時間階層5.5　解析的階層と記述集合論5.6　クリプキ・プラテックの集合論5.7　α再帰理論と再帰的巨大順序数文献案内問題解答あとがき用語索引記号索引