『計算できるもの、計算できないもの』を読み始めた…計算ってなんだろう…計算機ってなんだろう

計算できるもの、計算できないもの ―実践的アプローチによる計算理論入門

『計算できるもの、計算できないもの』が年末年始のおやすみに入る前に届き、けっこうな量のメモを取りながら読み進めていたけど、全然進まなかった。

---

昔、コンピュータサイエンスの授業を受けたとき、いきなり出てきた”オートマトン”や、”チューリングマシン”の解説が、それまで少し学んでいたプログラミングとか、目の前にある実際のコンピュータとどう関連するのか、全然分からなかったし、ましてやそれまで習ってきた四則演算みたいな「計算」とも全然違うもので、先生が言っている内容はロジカルだったけど、「なぜ今これを学んでいるんだっけ？」ってのが分からないまま過ぎて行った記憶が有る。

---

ある程度プログラミングの学習が進んでいくと、「そもそも計算って何だ？」「計算機って何だ？」みたいな疑問にいく時が有ると思うけど、この『計算できるもの、計算できないもの』はそれに少しだけ答えてくれる（気がする）。

冒頭で計算を「扱いやすい問題」「扱いにくい問題」「計算不能問題」の3つに分類し、まずは計算できない事例、計算問題のカテゴリや、各種問題の定義、定番のチューリングマシンの定義へ進む構成が、当時受けた授業より分かりやすかった。

そもそも日本語だと、computation、calculation、calculusとそれぞれ違う意味の単語を全部「計算」で済ませるから分からなくなる(ちなみに本書でいう計算は「computation」…｟かたく｠ (数学的)計算(法); 算定数値; コンピュータのによる処理.と辞書には書かれている)

たぶん、冒頭の、当時の自分は、個別の理論よりも「全体における位置付け」や「現実のコンピュータとの関わり」が知りたかったのだと思う。そうゆう意味では、知りたい順番に並んでいる本書を当時の自分に届けたいと思える構成だった。

さらに、個人的には、第６章の「万能コンピュータプログラム」、特に「6.3 実世界における万能計算」が一番分かりやすくて、色々な階層に万能計算できるものが存在する、という概念が最初に分かっていればもっと素直に理解できた気がする。多分当時は、チューリングマシンを、何か特定のVMみたいなものと捉えようとして混乱していたのかもしれない。実際のコンピュータが出現する前から存在する思考実験の題材である、と分かっていれば当時もっと良い成績が取れたに違いない :)

とはいえ、改めて「計算」について学び直そうと思い、年末年始の3日間くらいを使って集中的に読んだものの前半の流し読みくらいしかできなかったので、きっと一年くらいかけて読んでいかないといけない1冊なんだと覚悟した。

とにかく噛みごたえのある一冊です。流し読みだと全然頭に入ってこない。

誰か一緒に読んでください。

---

個人的には、よりコードの占める割合の多い『アンダースタンディング・コンピュテーション』の方を先に読んでおくと入りやすいかな、と感じた。ただ、『アンダースタンディング・コンピュテーション』もかなりの噛みごたえの有る本なので、そうそう簡単には読み終わらないのだけど(今回併せて読み返して、後半を全然読んで無いことに気づいて、こちらも読み直している)。

アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで