計算理論の基礎 [原著第 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 情報の定義