ラムダ計算
上で述べたように、ラムダ計算は計算可能な全ての関数を表現することができる。また、上では 2 + 3 のような算術をラムダ式の一部として用いた。 2 + 3 などは計算可能であるから、もちろんラムダ計算による表現が可能である。もちろん、 2 + 3 以外にも計算可能な全ての関数の表現が可能である。ここではそれらのうちの主なものを紹介する。
例えば、ある数に 2 を加える関数 f を考える。これは通常の書き方では f(x) = x + 2 と書くことができるだろう。この関数 f は、ラムダ計算の式(ラムダ式という)では λx. x + 2 と書かれる。変数 x の名前は重要ではなく、 λy. y + 2 と書いても同じである。同様に、この関数に 3 を適用した結果の数 f(3) は (λx. x + 2) 3 と書かれる。関数の適用は左結合である。つまり、 f x y = (f x) y である。今度は、引数(関数の入力)に関数をとりそれに 3 を適用する関数を考えてみよう。これはラムダ式では λf. f 3 となる。この関数に、先ほど作った 2 を加える関数を適用すると、 (λf. f 3) (λx. x + 2) となる。ここで、
(λf. f 3) (λx. x + 2) と (λx. x + 2) 3 と 3 + 2
の3つの表現はいずれも同値である。
ラムダ計算では、関数の引数は常に1つである。