離散数学への招待(上)を読んだら、関数のイメージがわいたので、この勢いで以前読んですぐに挫折->放置という運命を辿っていた計算論を読み返してみた。
計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)- 計算可能な関数
- ラムダ計算の基礎
- ラムダ計算のモデル
3はよくわからなかったけど、2はそこそこ理解できた。1章はラムダ計算とは関係ないのだけど、チューリング機械を数学的に表現する話なのでそこそこ楽しかった。
λ式
- 変数xはλ式
- Mがλ式でxが変数のとき(λx.M)はλ式 # 関数抽象
- MとNがλ式のとき(MN)はλ式 # 関数適用
数式だけだと理解が進まないので、grassを動かしたり中を覗いてみたりしたのが良かった。
あとメモ
- Curryの不動点演算子: Y = λy.(λx.y(xx))(λx.y(xx))
- β正規形
- 正規化定理