計算理論と数理論理学

共立出版
田中一之　

• 価格: 4,620円（本体4,200円＋税）
• 発行年月: 2022年06月
• 判型: Ａ５
• ISBN: 9784320114722

内容情報

[BOOKデータベースより]

第１章　計算理論入門（オートマトンとモノイド；チューリング機械　ほか）
第２章　命題論理と計算の複雑さ（トートロジーと証明；命題論理の完全性　ほか）
第３章　１階論理と決定問題（１階論理とは；スコーレムの定理　ほか）
第４章　２階論理と無限オートマトン（２階論理；２階算術と解析的階層　ほか）
第５章　階層理論と許容集合（オラクル計算と相対化；ｍ還元と単純集合　ほか）

[日販商品データベースより]

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

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

時間的な広がりにおいても、1960年代のクリプキの許容可能順序数の理論から、最近のパリティゲームの無記憶決定性の証明まで、あまり一般向けの解説がないような話題も掘り起こして著者独自目線で数理論理学と計算理論の広がりを描いている。