内容
「計算の理論の世界へ、ようこそ！」
Michael Sipser教授の「Theory of Computation」の講義も、本書と同様に、このフレンドリーな挨拶から始まりました。彼の講義はMIT屈指の名講義で、教室には活気と笑いがあふれていました。2、3回の聴講を考えていた私はその魅力に魅せられて、91年秋学期の全講義に出席することになりました。
本書は、Sipser教授のMITでの講義ノートをもとにまとめられたものです。計算の理論の主テーマである、オートマトンと言語の理論、計算可能性の理論、そして計算の複雑さの理論をカバーしています。
「まえがき」を含めて、随所に講義の雰囲気が感じられます。定理を述べたあと直ちに証明に取り かからず、証明のアイディアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、教育的 配慮の行き届いた教科書だと言えましょう。――訳者まえがきより
