不動点コンビネータ（ふどうてんコンビネータ、、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、）、パラドキシカル結合子（）などとも呼ばれる。ここで関数"f"の不動点とは、"f"("x") = "x"を満たすような"x"のことをいう。すなわち高階関数g が不動点コンビネータであるとは、事を指す。不動点コンビネータの定義は、任意の関数"f" に対し、が成立する事であるとも言い換えられる。第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子に束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算（）においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。一方、循環なく関数の意味を定義する（できる）、ということは、計算理論の上では重要である。まず、再帰関数の性質を簡単に振り返り、記号をいくつか定義する。関数"a" が再帰的に定義されているとき、"a"の定義式は何らかの高階関数"U" を用いて、と書ける。たとえば"a(x)" がxの階乗を計算する関数である場合、Uとしてを取る事ができる。上述のように定義された"U" が(1)を満たすのは明らかであろう。"U" を用いて高階関数formula_4をと定義する。（すなわち"V"は関数"f" を入力として受け取ると関数「formula_6」を出力する高階関数である。ラムダ計算の用語で言えば、"V" は"U" のカリー化formula_7にあたる。）"V" の定義より、formula_8はそれ自身関数であり、任意の"x" に対し、が成り立つ。ここでformula_10は関数formula_8に"x" を入力したときの値。さて、g を不動点コンビネータとするとき、不動点コンビネータの定義より特に、formula_12は"V" の定義域の元である事が分かる。"V" の定義域は関数の集合だったので、これはすなわちformula_12はそれ自身関数である事を意味する。この関数formula_12が(1)式で定義された再帰関数"a" と一致する事を示す事ができる（後述）。よって以下のようにすれば不動点コンビネータg で再帰関数"a" を実現できる事になる：最後にformula_12が(1)式で定義された再帰関数"a" と一致する事を示す。不動点コンビネータの定義より、formula_12はを満たす。前述したようにformula_12はそれ自身関数なので、値"x"に対しformula_21を考える事ができる。formula_21は以下を満たす：すなわち(1)と(5)を見比べると、(5)は(1)で"a"をformula_12 に置き換えたものに等しい事が分かる。(1)は"a" の（再帰的な）定義式であったので、これはすなわちformula_12 が"a" の定義式を満たす事を意味する。よってが成立する事が分かった。型無しラムダ計算や組合せ論理などの特定の数学的な計算形式化においては、すべての式は高階関数とみなすことができる。これらの形式化では、不動点コンビネータが存在することはすなわち、すべての関数が少なくとも1つの不動点を持つことを意味する。さらに、関数は複数の異なる不動点を持つことができる。単純型付きラムダ計算などの他のいくつかの体系では、十分に型付けされた不動点コンビネータを書くことはできない。それらの体系で再帰をサポートするには、明示的に言語体系に組み込む必要がある。それでも再帰データ型によって拡張された単純型付きラムダ計算などでは不動点演算子を書くことができるが、ある種の「実用的な」不動点演算子（常にいずれかの適用を返すもの）は制限される。多相ラムダ計算（、システムF、）では多相不動点コンビネータは型∀a.(a→a)→aを持つ（"a"は型変数）。型無しラムダ計算においてよく知られた（そしておそらく最もシンプルな）不動点コンビネータはYコンビネータと呼ばれる。これはハスケル・カリーによって発見されたもので、次のように定義される。実際に関数"g"を適用することによって、この関数が不動点コンビネータとして動作するのが分かる。これをそのままラムダ計算で使うと、評価戦略が値渡しだった場合には (Y g) が (g (Y g)) と展開された後も、引数の値を先に求めようとして (g (g (Y g))) →...→ (g ... (g (Y g))...) のように無限に展開され続けて止まらなくなってしまうので、次節で示すZコンビネータのように修正する。評価戦略が名前渡しの場合はこのまま使える。このカリーによるコンビネータのみをYコンビネータとすることもあるが、実装などでは不動点コンビネータを指す名前として他の形であってもYという名前を使っていることもある（#グラフ簡約の節の注を参照せよ）。SKIコンビネータ計算では次のようになる。値渡し評価（適用順序）でも使用可能なバージョンのYコンビネータは、通常のYコンビネータの一部をη変換することで与えられる。以下はPythonによる例である。JavaScript ではこのように実装できる。もう一つの一般的な不動点コンビネータは、チューリング不動点コンビネータである（発見者であるアラン・チューリングの名にちなむ）。これはシンプルな値渡し形式も持つ。SKIコンビネータ計算のSとKによる最もシンプルな不動点コンビネータは、ジョン・トロンプによって発見された以下であり、これは次のラムダ式と対応する。型無しラムダ計算における不動点コンビネータは無数に存在するので、特に珍しいわけではない。2005年、メイヤー・ゴールドバーグ (Mayer Goldberg) は型無しラムダ計算の不動点コンビネータの集合が帰納的可算集合であることを示した。次のようないくつかの不動点コンビネータ（ジャン・ウィレム・クロップによって組み立てられた）は、主として遊びに使われる。ここで型無しラムダ計算には不動点演算子と同じボーム木（）を持つラムダ式がある。すなわちそれらはλx.x(x(x ... ))と同じ無限の拡張を持つ。これは非標準不動点コンビネータ（）と呼ばれる。定義より、あらゆる不動点コンビネータは非標準でもあるが、すべての非標準不動点コンビネータが不動点コンビネータであるわけではない。それらのいくつかは「標準」の定義を満たさないからである。これらの変わったコンビネータは特にstrictly non-standard fixed point combinatorsと呼ばれる。例として、B = λx.xxかつM = λxyz.x(yz)としたときのコンビネータN = BM(B(BM)B)が挙げられる。非標準不動点コンビネータの集合は帰納的可算集合ではない。これまでの節で実装というよりは主に理論の観点から述べてきた、評価戦略が名前渡しの場合と値渡しの場合の違いは、実装においては、非正格(non-strict)なプログラミング言語（ないし処理系）と正格(strict)な言語の場合にほぼそのまま対応する。非正格な（遅延評価の、と言い換えてもだいたい同じ。具体的にはHaskellなどがそう）言語ないし処理系においては、ほぼ不動点コンビネータの意味そのままに循環的に実装できる。正格な場合は修正が必要であり、後述する。理論的には循環が無いことに意味があったが、実装においては循環的で普通は問題が無く、そのほうが効率的でもある。以下にHaskellによる不動点コンビネータの実装を示す。この不動点コンビネータはHaskellにおいては伝統的にcodice_1と呼ばれる。codice_1は多相不動点コンビネータであることに注意せよ（前述のシステムFに関する議論も参照）。なお、Haskellには型推論があるが、以下では曖昧さをなくすために型は明記する（一般に、こういった特殊な型を使う場合は型を明記したほうが良いし、推論の実装の限界のために明記が必要なこともある）。定義の後に使用例が続く。なお、型無しラムダ計算におけるカリーのYコンビネータは、そのまま実装しようとすると、Haskellの型チェッカによって拒否される。codice_1の適用は遅延評価されるので無限ループにはならない。たとえばcodice_4がcodice_5として展開されるとき、部分式codice_6は評価されない。ところが、Haskellによるfixの定義を正格(strict)プログラミング言語に持ち込むと無限ループになる。なぜなら、fへ渡した引数は事前に展開され、無限の呼び出しの連続codice_7を生み出すからである。MLのような正格言語においては、クロージャの使用を強制することによって無限再帰問題を回避することができる。codice_1の正格なバージョンは型∀a.∀b.((a→b)→(a→b))→(a→b)を持つべきである。要するに、これは関数を取って返す関数でのみ動く。例として、以下はcodice_1の正格なバージョンのOCamlコード実装である。これと同じアイデアは（この場合は「貧乏人のクロージャ (poor man's closures) 」として使われる）メソッド内部のインナークラス（Javaではローカルインナークラスと呼ばれる）をサポートしている正格言語で（単相）不動点コンビネータを実装するのに用いることができる。Javaの場合、そのようなクラスが無名だとしても構文はなお扱いにくい（Javaコード）。たとえば、C++の関数オブジェクトでは呼び出し構文は単純化されるが、それらはまだ生成されている段階である。できればboost::bindのような補助関数を用いることが望ましい（C++コード）。再帰データ型（システムFを参照）をサポートしているプログラミング言語では、型レベルで再帰を適切に計算することによってYコンビネータの型付けが可能になる。変数xを自己適用する必要性は同型の (Rec a -> a) を用いて定義される型 (Rec a) によって管理することができる。例として、以下のHaskellコードは、型とともに同型写像のInとoutの2つの方向の名前を持つ。そして次のように書くことができる。OCamlによる等価なコードは以下。グラフ簡約（を参照）による計算系では、不動点コンビネータへの適用(apply, application)は理論通り展開しても良いが、左の図のように循環のあるグラフに簡約するという一種の、のぞき穴的最適化が知られている。また、これはカリーのYコンビネータではないが(この図のように)便宜的にYという名前で呼ばれていることもある。不動点コンビネータは識別子に束縛されていない関数が自分自身を呼び出す一般的な方法であるが、言語によっては特別な名前などで自分自身を呼び出すことができる。たとえばJavaScriptでは自分自身を参照することができるような名前が用意されており次のように書くことができる。（なお、ECMAScript5のstrict modeではarguments.calleeの使用は禁止されている）

出典:wikipedia