🧱

11F7 Yコンビネータを再帰的に作り出す

2026/04/24に公開

以前のブログで不動点定理について書いたが、下記の本にも ${\bf Y}$ コンビネータについて書いてあったので、紹介する。

参考書：
Curry, Hindley, Seldin (1972) Combinatory logic_Volume II

11F7 Yコンビネータ

次のような性質を持つコンビネータはパラドックス的コンビネータである。

(22)\quad{\bf Y}x=x({\bf Y}x)

${\bf Y}X$ は $X$ の不動点になっているので、不動点コンビネータと呼びたいところだが、パラドックス的なコンビネータと呼ぶことにする。

(23)\quad{\bf Y}=SI{\bf Y}

$(\zeta)$ 則が成り立てば、(22)から(23)を導ける。

ちなみに $(\zeta)$ 規則は次の通り。

(\zeta)\quad x\notin M, x\notin N\text{ ならば、}Mx=Nx \Rightarrow M=N

全ての $x$ について、

SI{\bf Y}x = Ix({\bf Y}x) = x({\bf Y}x) = {\bf Y}x

つまり、 $SI{\bf Y}x = {\bf Y}x$
$({\zeta})$ 規則より、 $SI{\bf Y} = {\bf Y}$ が導かれる。

Rosenbloomの ${\bf Y}$ コンビネータは

(24)\quad{\bf Y}_0\equiv\lambda x.(\lambda y.x(yy))(\lambda y.x(yy))

となる。

Turingの ${\bf Y}$ コンビネータは

\begin{array}{llll} (25)&\quad{\bf Y}_1&\equiv&(\lambda xy.y(xxy))(\lambda xy.y(xxy))\\ & &=&WI(B(SI)(WI)) \end{array}

となるが、 $WI(B(SI)(WI))$ を計算してみよう。
第3項の $B(SI)(WI)$ は、

\begin{array}{lcl} B(SI)(WI)&\equiv&(\lambda xyz.x(yz))(SI)(WI)\\ &\triangleright& \lambda z.SI(WIz)\\ &\triangleright& \lambda z.SI(Izz)\\ &\triangleright& \lambda z.SI(zz)\\ &\equiv& \lambda z.(\lambda uvw.uw(vw))I(zz)\\ &\triangleright& \lambda z.\lambda w.Iw(zzw)\\ &\triangleright& \lambda z.\lambda w.w(zzw)\\ &\equiv_\alpha& \lambda xy.x(yyx)\\ \end{array}

そこで

\begin{array}{lcl} WI(B(SI)(WI)) &\equiv&WI(\lambda xy.x(yyx))\\ &\triangleright&I(\lambda xy.x(yyx))(\lambda xy.x(yyx))\\ &\triangleright&(\lambda xy.x(yyx))(\lambda xy.x(yyx))\\ &=&{\bf Y}_1 \end{array}

だが、 ${\bf Y}_0$ と ${\bf Y}_1$ には

(26)\quad{\bf Y}_1 = {\bf Y}_0(SI)

という関係がある。実際、

\begin{array}{rcl} {\bf Y}_0(SI)&\triangleright&(\lambda y.SI(yy))(\lambda y.SI(yy)),\\ \lambda y.SI(yy)&=&\lambda y.(\lambda uvw.uw(vw))I(yy)\\ &\triangleright&\lambda y.\lambda w.Iw(yyw)\\ &\triangleright&\lambda yw.w(yyw)\\ &=&\lambda xy.y(xxy) \end{array}

驚くべきことに、 ${\bf Y}$ コンビネータから再帰的に新たな ${\bf Y}$ コンビネータを生成することができる。つまり、

(28)\quad{\bf Y}_{n+1}\equiv{\bf Y}_n(SI)

が成り立つ。
では、 ${\bf Y}_{n+1}$ が ${\bf Y}$ コンビネータであるかを証明してみよう。つまり、

(28')\quad{\bf Y}_{n+1}\ x = x({\bf Y}_{n+1} x)

を示せばよい。

$n=0$ の場合は(26)で証明済みである。
全ての $x$ について、

{\bf Y}_n\ x=x({\bf Y}_n\ x)

が成り立つときに、

{\bf Y}_{n+1}\ x = x({\bf Y}_{n+1} x)

が成り立つことを示せばよい。全ての $x$ に対して

\begin{array}{l} {\bf Y}_{n+1}\ x=({\bf Y}_n(SI))x \end{array}

${\bf Y}_n$ は ${\bf Y}$ コンビネータなので、 ${\bf Y}_n (SI)=(SI)({\bf Y}_n(SI))$ を満たすので、

\begin{array}{lcl} ({\bf Y}_n(SI))x &=& (SI)({\bf Y}_n(SI))x\\ &\triangleright& Ix({\bf Y}_n(SI)x)\\ &\triangleright& x({\bf Y}_n(SI)x)\\ &\equiv& x({\bf Y}_{n+1}\ x) \end{array}

よって再帰的に

{\bf Y}_n\ x=x({\bf Y}_n\ x)

が成り立つので、全ての

n\geq 0

に対して、(28)が成り立つ。