『計算できるもの、計算できないもの』

こんにちは。

不思議なタイトルだったので、
買ってみました。

『マスターアルゴリズム』にしようか、
３０分間くらい本棚の前で悩んでいましたが、
面白そうだったのでこっちにしました。

主な内容は、

・計算機による計算とは何か
・計算できるものと計算できないものの
　境目はどこなののか

などを明らかにする計算理論について、
書かれていています。この辺は計算機科学
においてもっとも基本的かつ重要なものです。

本書では、計算理論に必要な概念の説明や
証明にはPythonプログラムが利用されていて、
理解しやすいようにしてあります。

計算可能問題と計算不能問題、
扱いやすい問題と扱いにくい問題、
文章では簡単に表現できても計算機には
解けない重要な問題が多くある、
効率よく解ける問題と解けない問題があること
チューリングマシン、有限オートマトン、
万能計算、非決定性、NP完全性などの
分野について、書かれていてます。

あと、計算理論のアラン・チューリングと
リチャード・カープの論文など、
参考にしてあります。

内容は盛りだくさんなので、少しずつ
読みすすめています。