不動点コンビネータ
ラムダ計算の用語で言えば、V はU のカリー化 λ f . ( λ x . U ) {\displaystyle \lambda f.(\lambda x.U)} にあたる。) V の定義より、 V ( f ) {\displaystyle V(f)} はそれ自身関数であり、任意のx に対し、
V ( f ) ( x ) = U ( f , x ) {\displaystyle V(f)(x)=U(f,x)} ...(3)
が成り立つ。ここで V ( f ) ( x ) {\displaystyle V(f)(x)} は関数 V ( f ) {\displaystyle V(f)} にx を入力したときの値。
さて、g を不動点コンビネータとするとき、不動点コンビネータの定義より特に、 g ( V ) {\displaystyle {\boldsymbol {g}}(V)} はV の定義域の元である事が分かる。 V の定義域は関数の集合だったので、これはすなわち g ( V ) {\displaystyle {\boldsymbol {g}}(V)} はそれ自身関数である事を意味する。 この関数 g ( V ) {\displaystyle {\boldsymbol {g}}(V)} が(1)式で定義された再帰関数a と一致する事を示す事ができる(後述)。
よって以下のようにすれば不動点コンビネータg で再帰関数a を実現できる事になる:
U のプログラムを書く。
V を(2)式のように定義し、 a = g ( V ) {\displaystyle a={\boldsymbol {g}}(V)} とする。
型無しラムダ計算や組合せ論理などの特定の数学的な計算形式化においては、すべての式は高階関数とみなすことができる。これらの形式化では、不動点コンビネータが存在することはすなわち、すべての関数が少なくとも1つの不動点を持つことを意味する。さらに、関数は複数の異なる不動点を持つことができる。
単純型付きラムダ計算などの他のいくつかの体系では、十分に型付けされた不動点コンビネータを書くことはできない。それらの体系で再帰をサポートするには、明示的に言語体系に組み込む必要がある。それでも再帰データ型によって拡張された単純型付きラムダ計算などでは不動点演算子を書くことができるが、ある種の「実用的な」不動点演算子(常にいずれかの適用を返すもの)は制限される。多相ラムダ計算(英: polymorphic lambda calculus、システムF、英: System F)では多相不動点コンビネータは型∀a.(a→a)→aを持つ(aは型変数)。