Daily Archives: December 23, 2024

Y combinator

Posted on by

Why Yg = g(Yg) Enables Recursion

.

The following calculation verifies that Yg is indeed a fixed point of the function g:

\begin{aligned} Y g &= (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g \\ &= (\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)) \\ &= g\ ((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x))) \\ &= g\ (Y\ g) \end{aligned}

The lambda term g\ (Y\ g) may not, in general, \beta-reduce to the term Y\ g . However, both terms \beta-reduce to the same term, as shown.

— Wikipedia on Fixed-point combinator

.

\begin{aligned} Y g &= (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g \\ &= (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ (f := g) \\ &= (\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)) \\ &= (\lambda x.g\ (x\ x))\ (\lambda y.g\ (y\ y)) \\ &= (\lambda x.g\ (x\ x))\ (x := (\lambda y.g\ (y\ y))) \\ &= g\ ((\lambda y.g\ (y\ y))\ (\lambda y.g\ (y\ y))) \\ &= g\ (Y\ g) \end{aligned}

— Me@2024-12-22 11:53:21 PM

.

.

2024.12.22 Sunday (c) All rights reserved by ACHK