計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座) |
|
売れ筋ランキング ＞ 計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)
帰納関数論、λ計算、λ計算のモデルを扱う入門書。読んでいて非常に楽しかった。 確かに難しいところも多々ある。λ計算をまったく知らない人が読んでいけるとは思えない。私も分からなくなって数ヶ月放置し、他の本で別の説明を読んでから読み直したりした。 各項目にうまくつながりをつけるように書いてある。特にD∞を導入するあたりは最高。天下り的にD∞を導入するのではない。λ計算のモデルとはそもそもどういうものになるか、と一般的に考えた後、D∞を提示していく。これによってλのタームがどのような役割を担ったものなのか、λ計算がいったい何を表現しようとしているのか納得が行く。 非常にうまく書かれている本とはいえ、独習者にはきつい。読書会やゼミのテキストとして活用できる本だろう。 最初に割り算と引き算について、自然数で閉じるように定義をしている。 次ぎに、ユークリッドの互除法の原理の説明がある。 gcd(x,y) = gcd(y,mod(x,y)) if (y>0) = x (y=0) いきなりmod関数を使っている。 １．６計算不可能な関数と決定不能な問題で、 「帰納的述語ではない」ということと、計算不可能という関係がよくわからなかった。 決定不能な問題としては、Postの対応問題、Hilbertの第１０問題の紹介があるが、証明は省略されている。参考文献として、廣瀬健の帰納的関数が参考文献にある。 「コンピュータで計算ができる関数とはいかなるものか？」というモチベーションからスタートして、その概念を厳密に定式化する。また抽象化されたプログラミング言語であるラムダ計算を全くの基礎から解説し、計算可能性との関係、ベームの木、ラムダモデルなど、かなり高度な内容まで詳しく説明されている。 全く前知識なしで読み通せるくらい親切で、しかし、高度な内容までほとんど省略なく書いてある。証明も無駄がなくエレガントなものが多い。 計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)を楽天で検索 |
