ラムダ式で表されたチャーチ数は、次のように定義することができる。
0 = λfx.x
1 = λfx.fx
2 = λfx.f(fx)
3 = λfx.f(f(fx))
4 = λfx.f(f(f(fx)))
5 = λfx.f(f(f(f(fx))))
この定義を用いて自然数の演算を定義することができる。それを用いた次のラムダ式
λpqfx.pf(qfx) 3 1
を簡約して得られるラムダ式がチャーチ数として表す自然数はいずれか。
① 1 ② 2 ③ 3 ④ 4 ⑤ 5
④
ラムダ式はラムダ計算式ともいう。
例えば f(x) = x+1 の関数は、λx.x+1 と表記される。
この関数の引数が2であれば、
f(2) = 2+1 = 3 であるが、ラムダ式では
(λx.x+1)2 と表記し、(λx.x+1)2 → 2+1 → 3 となる。
変数が2つのラムダ計算式の場合、
例えば f(x, y) = x+y の関数は、λx.λy.x+y もしくは λxy.x+y と表記され、
(x, y) = (2, 3)の場合
(λx.λy.(x+y))23 → (λy.(2+y))3 → 2+3 → 5
もしくは
(λxy.x+y)23 → (λy.2+y)3 → 2+3 → 5 となる。
また、高階関数の場合、
例えば λf.λx.f(f(x)) は、関数 f とデータ x を引数とし、f を x に 2 回適用した値を返す f(f(x)) を表す。
たとえば，f(x) = x∗2 、すなわち f = λx.x∗2 のとき
f(f(x)) = f(x*2) →(x*2)*2 → x*4 だから
λf.λx.f(f(x)) → λx.x*4 を表す。
以下のように変形して計算できる。
λpqfx.pf(qfx) 3 1
→ λqfx.3f(qfx) 1
→ λfx.3f(1fx)
→ 3f(fx)
ここで、3 = λfx.f(f(fx)) だから
3f(fx)
→ λfx.f(f(fx)) f(fx)
→ f(f(f(fx))) → 4
| Ⅲ－３ | 目次 | Ⅲ－５ |