計算理論の基礎

著者 : マイケル・シプサ 渡辺治 太田和夫

• 共立出版 (2000年4月15日発売)

作品紹介・あらすじ

計算の理論の世界へ、ようこそ!Michael Sipser教授の「Theory of Computation」の講義も、本書と同様に、このフレンドリーな挨拶から始まりました。彼の講義はMIT屈指の名講義で、教室には活気と笑いがあふれていました。2,3回の聴講を考えていた私はその魅力に魅せられて、91年秋学期の全講義に出席することになりました。本書はSipser教授のMITでの講義ノートをもとにまとめられたものです。計算の理論の主テーマである、オートマトンと言語の理論、計算可能性の理論、そして計算の複雑さの理論をカバーしています。

感想・レビュー・書評

[おぬまさんの感想 · 2023年5月27日]

図書館で借りた。丁度最近第3版が発売されたらしいが、借りたのは初版。1冊もので、大きい。
計算理論とは、いわゆるコンピュータで何が計算できて、何は計算できないのか等を突き詰めていく研究領域だ。そのためのオートマトン、チューリングマシン、正規言語・形式言語などを基礎として学ぶ。
計算可能性、判定可能性、帰着可能性…、さらには計算の複雑さ、そういったあたりが詳しく記述されている。
証明なども詳しく、理解が深まるのは間違いない。

[Mikioです。さんの感想 · 2005年11月21日]

オートマトン：入力に対して処理を行ない、結果を出力する簡単な機械。こんなものが世の中の文明の基礎になってるなんて、、これを勉強しないてはない。
この本は、でかい！たかい！！しかし、抽象的なオートマトンや計算論について具体的に記述しており、素人の僕にも分かった気にさせてくれる！！！