計算理論の基礎 [原著第 3 版] 2.計算可能性の理論(ケイサンリロンノキソゲンチョダイサンハンニケイサンカノウセイノリロン)

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

第 5 章 帰着可能性
5.1 言語理論における判定不可能問題
5.2 単純な判定不可能問題
5.3 写像帰着可能性

第 6 章 計算可能性の理論における先進的な話題
6.1 再帰定理
6.2 数理論理における判定可能性
6.3 Turing 帰着可能性
6.4 情報の定義