資料詳細

[ 和図書 ] 計算理論と数理論理学

田中一之／著 -- 共立出版 -- 2022.6 --

所蔵

所蔵は 1 件です。

遠隔複写申込みは、東京都在住・在勤・在学の方からお受けいたします。
複写カート機能には、Cookieを使用しています。申込む際はCookieを有効にしてください。

ISBN	4-320-11472-2
ISBN13桁	978-4-320-11472-2
タイトル	計算理論と数理論理学
タイトルカナ	ケイサンリロントスウリロンリガク
著者名	田中一之／著
著者名典拠番号	110002792420000
並列タイトル	MATHEMATICS OF LOGIC AND COMPUTATION
出版地	東京
出版者	共立出版
出版者カナ	キョウリツシュッパン
出版年	2022.6
ページ数	8, 299p
大きさ	22cm
価格	¥4200
内容紹介	「計算理論」と「数理論理学」を同時に学ぶための学部上級から大学院初年級レベルの独習書。両分野の話題をうまく交えながら、巧みな筆致で解説する。問題、文献案内、用語・記号索引付き。
書誌・年譜・年表	文献:p264～265
一般件名	計算量理論-ndlsh-00576481,記号論理学-ndlsh-00565709
一般件名	計算量理論 , 記号論理学
一般件名カナ	ケイサンリョウリロン,キゴウロンリガク
一般件名典拠番号	510702300000000 , 510630200000000
分類：都立NDC10版	410.9
テキストの言語	日本語
資料情報1	『計算理論と数理論理学』　田中一之／著　共立出版　2022.6（所蔵館：中央　請求記号：/410.9/5151/2022　資料コード：7115643192）
URL	https://catalog.library.metro.tokyo.lg.jp/winj/opac/switch-detail.do?lang=ja&bibid=1154031047

第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 α再帰理論と再帰的巨大順序数