計算理論と数理論理学

書籍

オンデマンド版

大活字版

書籍

雑誌

電子版

読み上げ可能電子版

オーディオブック

著：田中一之

出版社：共立出版

同一作品の他版

アクセシブルブック

内容紹介

本書は「計算理論」と「数理論理学」を同時に学ぶための、学部上級から大学院初年級レベルの教科書あるいは独習書である。背景の説明も充実しているので、幅広くリファレンスとしても活用できる。

両分野を同時に学ぶといっても、単に両分野の共通項を括り出したり類似性を強調したりするのではなく、それぞれの違いは違いとして認めながら、両分野の稜線に立って壮大な景色を展望している。

時間的な広がりにおいても、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。

※同一作品の他版、アクセシブルブックにはAIにより推定されたものが含まれる場合があります。

ご購入はこちら

計算理論と数理論理学

内容紹介

目次