計算理論の基礎 ２ 原著第３版

計算可能性の理論　

共立出版
Ｍｉｃｈａｅｌ　Ｓｉｐｓｅｒ　田中圭介　藤岡淳　阿部正幸　植田広樹　

• 価格: 3,740円（本体3,400円＋税）
• 発行年月: 2023年05月
• 判型: Ａ５
• ISBN: 9784320125629

内容情報

[BOOKデータベースより]

３　Ｃｈｕｒｃｈ‐Ｔｕｒｉｎｇの提唱（Ｔｕｒｉｎｇ機械；Ｔｕｒｉｎｇ機械の変型　ほか）
４　判定可能性（判定可能な言語；判定不可能性）
５　帰着可能性（言語理論における判定不可能問題　計算履歴を用いた帰着；単純な判定不可能問題　ほか）
６　計算可能性の理論における先進的な話題（再帰定理；数理論理における判定可能性　ほか）

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

Michael Sipser教授による “Theory of Computation” の講義はMIT屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。
　定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。
　第3版では、「決定性文脈自由言語」に関する節が新たに加えられたほか（第2巻）、問題や解答が追加されるとともに、いくつかの話題に関して、第2版刊行後の研究の進展について説明を加えた。