ラムダ計算まとめ - オボエガキ用

概要

ラムダ式の定義

BNFによる定義

前提) 記号 identifier = {a,b,c,...,x,y,z,...}
1) ::=
2) ::= (λ.)　　（ラムダ抽象）
3) ::= ()　　（関数適用）
where, identifierは可算無限集合（自然数集合Nと濃度が同じ集合）

集合による定義

Vを可算無限個の変数の集合とする。
ラムダ式(lambda term)の集合とは、次の条件1)〜3)を満たす最小の集合Λのこと。
1) $\lambda\in V \to \Lambda$
2) $M\in\Lambda ,x\in V \to (\lambda x.M)\in\Lambda$ (ラムダ抽象)
3) $M,N\in \Lambda \to (MN)\in\Lambda$ (関数適用)

参考リンク

Wikipedia(ラムダ計算 - Wikipedia)
住井英二郎氏(pdf)(http://www.kb.ecei.tohoku.ac.jp/~sumii/class/keisanki-software-kougaku-2005/lambda.pdf)
武市・胡氏(pdf)(Mathematical Structures in Computation Models)
高橋正子(計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座))
ラムダ計算基礎文法最速マスター - 貳佰伍拾陸夜日記