【読書メモ】アンダースタンディング コンピュテーション

チューリング・マシンとはイギリスの数学者チューリングが考案した計算モデルである。チューリングとは第二次世界大戦中にナチス・ドイツ軍の暗号Enigmaを解読した人物である。チューリングは当時、、今で言うコンピュータの原型となる機械を実装して、Enigmaの解読を行ったそうだ。チューリングの軌跡については、イミテーション・ゲームという映画で描かれており、内容もなかなかおもしろいのでおすすめである。 

イミテーション・ゲーム エニグマと天才数学者の秘密 [Blu-ray]

計算モデルとRuby実装

計算モデルとは、その名の通り計算機の動きを数学的に表したものとなる。現在の計算機は、ノイマン型コンピュータと呼ばれていて、アメリカの数学者・物理学者のフォン・ノイマンが考案した構成をとっている。ノイマン型コンピュータは、コンピュータは、CPU、メモリなどの外部記憶装置、それらをつなぐバスによって構成されている。

本書は、ノイマン型コンピュータと言ったハードウェア的な話ではなく、どちらかというと、数学的なモデルにもとづいた理論の解説と実装を行っている。計算モデルには、オートマトン、プッシュダウン・オートマトン、チューリング・マシンなどいくつかあるが、本書ではこれらを実際にRubyで実装して解説しているのが、他の書籍と一線を画する。

計算モデルについて考えることは、計算というものの本質をとらえるのに役に立つ。例えば、ある問題Xがあって、問題Xが計算機で解けるということはどういう事なのだろうか？これは、ある計算モデルで、その問題Xを解釈できるかということを考えてみると理解が深まる。たとえば、オートマトンよりも、非決定性プッシュダウン・オートマトンの方が扱える解ける問題が多く、非決定性プッシュダウン・オートマトンよりも、チューリング・マシンの方が扱える問題が多い。これを分類したものが、チョムスキー階層と呼ばれている。チョムスキー階層のことまで話すと長くなるので、詳細はWikipedia等を参考してほしい。

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

λ計算とChurch数

RubyやPythonと言った、一般的なプログラミング言語は、チューリング完全であると言われる。チューリング完全とはすなわち、チューリング・マシンと計算能力が等価であると言うことを意味している。チューリング・マシンは計算モデルの一つであるが、チューリング・マシンと等価な計算モデルに、λ計算と呼ばれるものがある。

λ計算とは、1930年代にイギリスの数学者であるチャーチが考案した計算モデルであり、その計算能力はチューリング・マシンと等価であることが、チャーチ自身によって示されている。λ計算は、関数型プログラミング言語とよばれるHaskellやMLの基礎となっているモデルである。

λ計算をBNF形式で表すと以下のようになる。

E := ID

     | (λ ID. E)

     | (E E)

ここで、IDはxやyなどの識別子のことである。つまり、

((λx. ((x x) x)) (λy. y))

のように書くのがλ計算である。たったこれだけの表記法ではあるが、計算能力がチューリング・マシンと等価である。しかし、これだけの規則では四則演算はおろか、数値すら表せないように思える。ところが、実際には、数値と四則演算をλ計算にエンコードする事ができる。λ計算によって表された数をChurch数と呼ぶが、本書では、このChurch数を実際にRubyで実装している。Church数はなかなかに衒学的で理解が難しいが、こうしてRubyで実装して解説してくれるのは大変ありがたい。

また、さらに踏み込んだ内容として、停止性問題についても解説している。停止性問題とは、ある問題が計算できるとはどういうことかについて、停止性という観点から論ずるものである。停止性とは、ある問題を解くアルゴリズムがあったときに、そのアルゴリズムが最終的に停止するかどうかという事を示している。

計算の本質についてRuby実装を示しながら提示する本書は、大変エキサイティングでファンタスティックであった。難易度は若干高めだが、数学的な専門書よりは断然わかりやすいので、腕に覚えのあるプログラマは是非挑戦してみてほしい。最後に、本書の雰囲気を掴むために、本書で掲載されているFizzBuzzのλ計算プラグラム一部を見てみよう。

この見開きページだけを見ても、本書の凄さが伝わるだろう。美しい。