コンビネータには様々なものがある。
基本コンビネータ
(I) $Ix\equiv x$
(K) $Kfx\equiv f$
(S) $Sfgx\equiv fx(gx)$
他のコンビネータ
他のコンビネータもこの基本コンビネータ$I,K,S$で書き表せる。
(B) $B\equiv \lambda fgx.f(g(x))$
$\equiv S(S(KS)(S(KK)(S(KS)K))) (KI)$
(B') $B'\equiv\lambda fgx.g(f(x))$
$\equiv S(K(S(S(KS)K)))(S(KK)(S(KK)(S(S(KS)K)(KI))))$
(C) $C\equiv \lambda fgx.fxg\equiv S(S(KS)(S(KK)S))(KK)$
(C*) $C_*\equiv\lambda xy.yx\equiv S(K(SI))K$
(W) $W\equiv\lambda fx.fxx\equiv SS(KI)$
IもK,Sで表せる I=SKK
他の関数も$I,K,S$のみで表すことができる。
実際、$I\equiv SKK$となり、$I$も$S,K$で表すことができるので、全ての関数はたった二つのコンビネータ$S,K$で表すことができることになる。計算してみると、
$SKK\equiv(\lambda xyz.xz(yz))KK\rightarrow \lambda z.Kz(Kz)
\rightarrow \lambda z.z\equiv I$
一般に$w$がどんな項であっても$SKw\rightarrow I$となる。
$SKw\equiv(\lambda xyz.xz(yz))Kw\rightarrow \lambda z.Kz(wz)\rightarrow \lambda z.z\equiv I$
$SKS\rightarrow I$も成り立つ。
iota
更に驚くべきことに
$$\iota\equiv\lambda f.fSK$$
と$\iota$を定義すると、$I,K,S$を表せる。
これはイオタ・コンビネータと呼ばれ、言語学者のChris Barkerによって発見された。イオタはギリシャ文字であり、英語の"i"に対応し、ランボルギーニ・イオタという名を聞いたことがある人もいるかも。
I=ii
$\iota\iota\equiv(\lambda f.fSK)(\lambda f.fSK)$
$\equiv(\lambda f.fSK)SK
\equiv SSK(K)
\equiv SK(KK)$
$\equiv(\lambda xyz.xz(yz))K(SS)
\equiv\lambda z.Kz(SSz)
\equiv\lambda z.z\equiv I$
$$I\equiv\iota\iota$$
K=i(i(ii))
$\iota(\iota(\iota\iota))
\equiv\iota(\iota(I))$
$\equiv\iota((\lambda f.fSK)I)
\equiv\iota(ISK)
\equiv\iota(SK)$
$\equiv(\lambda f.fSK)(SK)
\equiv(SK)SK
\equiv SKSK$
$\equiv KK(SK)
\equiv K$
$$K\equiv\iota(\iota(\iota\iota))$$
S=i(i(i(ii))
$\iota(\iota(\iota(\iota\iota)))
\equiv\iota(K)
\equiv(\lambda f.fSK)K
\rightarrow KSK
\rightarrow S$
$$S\equiv\iota(\iota(\iota(\iota\iota)))$$
全ての関数がたった一つのコンビネータが表せるなんて、数学の世界は驚きに満ちている。
$\iota$を使ってフィボナッチ数列の関数を表現した動画参照。最後のおまけ部分で紹介されている。