不動点コンビネータ
最後に g ( V ) {\displaystyle {\boldsymbol {g}}(V)} が(1)式で定義された再帰関数a と一致する事を示す。 不動点コンビネータの定義より、 g ( V ) {\displaystyle {\boldsymbol {g}}(V)} は
V ( g ( V ) ) = g ( V ) {\displaystyle V({\boldsymbol {g}}(V))={\boldsymbol {g}}(V)} ...(4)
を満たす。
前述したように g ( V ) {\displaystyle {\boldsymbol {g}}(V)} はそれ自身関数なので、値xに対し g ( V ) ( x ) {\displaystyle {\boldsymbol {g}}(V)(x)} を考える事ができる。
不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。一方、循環なく関数の意味を定義する(できる)、ということは、計算理論の上では重要である。
まず、再帰関数の性質を簡単に振り返り、記号をいくつか定義する。関数a が再帰的に定義されているとき、aの定義式は何らかの高階関数U を用いて、
a ( x ) = U ( a , x ) {\displaystyle a(x)=U(a,x)} ...(1)
と書ける。たとえばa(x) がxの階乗を計算する関数である場合、Uとして
U ( f , x ) = { 1 if x = 0 x f ( x − 1 ) otherwise {\displaystyle U(f,x)={\begin{cases}1&{\text{if }}x=0\\xf(x-1)&{\text{otherwise}}\end{cases}}}
を取る事ができる。上述のように定義されたU が(1)を満たすのは明らかであろう。
U を用いて高階関数 V {\displaystyle V} を
V : f ↦ U ( f , ⋅ ) {\displaystyle V~:~f\mapsto U(f,\cdot )} ...(2)
と定義する。 (すなわちVは関数f を入力として受け取ると 関数「 x ↦ U ( f , x ) {\displaystyle x\mapsto U(f,x)} 」を出力する高階関数である。