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　情報の定義