Church 数のメモ

プログラミング scheme

404 Blog Not Found:TuringとChurchの狭間で で少しすっきりしたので、分かったところまでメモ。

0 := λ f x . x
1 := λ f x . f x
2 := λ f x . f f x

自然数 \huge n の場合を自分用に噛み砕いて。

  • 自然数 \huge n は、2 変数関数である。
  • 関数 \huge n の第一引数は、関数である。
  • 関数 \huge n の第二引数は、第一引数である関数の引数になる
  • 関数 \huge n の値は \huge \underbrace{f\cdots f}_{n}(x)
    • すなわち、\huge n(f,x) \equiv \underbrace{f\cdots f}_{n}(x)

後は未消化。特に Y combinator のところ。
でも、Church 数の解説は大変ありがたかったです。