パソコンを使っていると、その多彩な機能に隠れて忘れがちなのだが、コンピュータは本質的には「計算機」である。そのコンピュータの根幹をなす計算論について、比較的コンパクトに、それでいて本格的に解説したのが本書である。

   大がかりになりがちな本書のテーマを、著者は「計算論の上級コースが1つしかない大学で1単位分の講義に使う場合を主に想定して」、原理よりもむしろどのように理解していけばよいのかを主軸にまとめあげている。単純に数学の解説書と考えた場合、もう少し説明の欲しい部分もあるが、計算論を俯瞰（ふかん）する概説書としては、十分に機能を果たしているといえる。

   本書では、伝統的な有限オートマトンから文脈自由言語、コンピュータの基礎といえるチューリング機械、アルゴリズムで解けない問題を扱う決定不能性、逆にアルゴリズムで解くことができる問題の計算量について扱う。基本的に学生向けに書かれており、解説はもちろんのこと、例や練習問題をほどよく盛り込み、深い理解を容易にする工夫が凝らされている。とくに練習問題は、記号により難易度を分けているため、レベルに応じて効率的に学ぶことが可能となっている。

   本書を読み解くにあたり、数学の知識は必要不可欠だが、他の数学書に比べて若干敷居は低くなっている。数学を専門としない学生や、計算論を基礎から学び直したい人、コンピュータの原理をもう少し掘り下げて知りたいという人には最適な入門書だ。（大脇太一）