計算理論の基礎 の商品レビュー

Michael Sipser(著者),渡辺治(訳者),太田和夫(訳者),田中圭介(訳者),阿部正幸(訳者),植田広樹(訳者),藤岡淳(訳者),渡辺治(訳者)

2023/05/27

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

2009/10/04

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