「Yコンビネータ」は不動点演算子について説明しているこの項目へ転送されています。カリフォルニア州の企業については「Yコンビネータ (企業)」をご覧ください。

不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる。ここで関数 f {\displaystyle f} の不動点とは、 f ( x ) = x {\displaystyle f(x)=x} を満たすような x {\displaystyle x} のことをいう。

すなわち高階関数 g {\displaystyle {\boldsymbol {g}}} が不動点コンビネータであるとは、任意の関数 f {\displaystyle f} に対し、 p = g ( f ) {\displaystyle p={\boldsymbol {g}}(f)} とすると, f ( p ) = p {\displaystyle f(p)=p} が成立する

事を指す。

あるいは全く同じことだが、不動点コンビネータの定義は、任意の関数 f {\displaystyle f} に対し、 f ( g ( f ) ) = g ( f ) {\displaystyle f({\boldsymbol {g}}(f))={\boldsymbol {g}}(f)}

が成立する事であるとも言い換えられる。

第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子に束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。[1][2]

不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算（英: untyped lambda calculus）においては、ハスケル・カリーの Y = λf・(λx・f (x x)) (λx・f (x x)) という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。
不動点コンビネータによる再帰の実現

不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。一方、循環なく関数の意味を定義する（できる）、ということは、計算理論の上では重要である。

まず、再帰関数の性質を簡単に振り返り、記号をいくつか定義する。関数 a {\displaystyle a} が再帰的に定義されているとき、 a {\displaystyle a} の定義式は何らかの高階関数 U {\displaystyle U} を用いて、 a ( x ) = U ( a , x ) {\displaystyle a(x)=U(a,x)} (Eq. 1)

と書ける。たとえば a ( x ) {\displaystyle a(x)} が x {\displaystyle x} の階乗を計算する関数である場合、 U {\displaystyle 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 {\displaystyle U} が(Eq. 1)を満たすのは明らかであろう。

U {\displaystyle U} を用いて高階関数 V {\displaystyle V} を V   :   f ↦ U ( f , ⋅ ) {\displaystyle V~:~f\mapsto U(f,\cdot )} (Eq. 2)

と定義する。（すなわち V {\displaystyle V} は関数 f {\displaystyle f} を入力として受け取ると関数「 x ↦ U ( f , x ) {\displaystyle x\mapsto U(f,x)} 」を出力する高階関数である。ラムダ計算の用語で言えば、 V {\displaystyle V} は U {\displaystyle U} のカリー化 λ f . ( λ x . U ) {\displaystyle \lambda f.(\lambda x.U)} にあたる。） V {\displaystyle V} の定義より、 V ( f ) {\displaystyle V(f)} はそれ自身関数であり、任意の x {\displaystyle x} に対し、 V ( f ) ( x ) = U ( f , x ) {\displaystyle V(f)(x)=U(f,x)} (Eq. 3)

が成り立つ。ここで V ( f ) ( x ) {\displaystyle V(f)(x)} は関数 V ( f ) {\displaystyle V(f)} に x {\displaystyle x} を入力したときの値。

さて、g を不動点コンビネータとするとき、不動点コンビネータの定義より特に、 g ( V ) {\displaystyle {\boldsymbol {g}}(V)} は V {\displaystyle V} の定義域の元である事が分かる。 V {\displaystyle V} の定義域は関数の集合だったので、これはすなわち g ( V ) {\displaystyle {\boldsymbol {g}}(V)} はそれ自身関数である事を意味する。この関数 g ( V ) {\displaystyle {\boldsymbol {g}}(V)} が式で定義された再帰関数 a {\displaystyle a} と一致する事を示す事ができる（後述）。

よって以下のようにすれば不動点コンビネータg で再帰関数 a {\displaystyle a} を実現できる事になる：