計算論とかラムダとか

最近ラムダっぽいことばっかり考えているので、ふつうの会話ができなくなりつつあります。そういうことを話す相手がいなくてイライラしたときは、SICP読書会でそういう話ができるので助かっています。

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

読み始めた。寝る前にベッドの中で15分くらい読んで寝るので、とてもゆっくり読み進めています。今は、原始帰納関数のおはなし。1年のときに記号論理学でゲーテルの不完全性定理の証明を見るときに簡単に勉強したので、懐かしい部分が多い。

原始帰納関数は全域的帰納関数(計算可能な関数)のサブセットで、原始帰納法により定義される関数の集合。原始帰納法は、プログラムの最も単純な再帰に対応するものですね。function(0) のときの値を定めて、function(n+1)の値はfunction(n)の値を使って計算する、ってやつです。定数関数、射影関数、サクセッサー関数を材料にして、原始帰納法を使って料理すると、実に様々な関数が出来上がる、という面白い世界。

全域的帰納関数だけど、原始帰納関数じゃない代表例で有名なのはAckerman関数。

記号論理学の授業では、帰納関数をチューリング完全で単純な構造を持つプログラムで表現し、そのプログラムを表す1つの自然数＝ゲーテル数を求める、ということをやった。理論的には、あらゆるプログラムは1つの自然数*1で表現することができるってのは言われてみれば当たり前だけど面白い。

この本ではどんな流れで帰納関数とラムダ計算がつながっていくのかまだ見てないのでわからない。楽しみ。

うちの学科は、プログラミングとかやるけどおそらく応用メインなのでこういうことは勉強しないんじゃないだろうか。計算機を生業とする人間ならば、実務には役立たないかもしれないけど勉強しといて損はないと思う。こういうことばっかりやって大学の授業をサボる俺はどうなんだろう。

で、今日はホテルで寝るんだけどこの本忘れて読めないよって言いたかっただけです。代わりに↓でも読みます。著者曰くプレゼンはSEXらしいです。

理系のための プレゼンのアイディア

*1:とても巨大な数になる