3. The Y combinator: The following famous term is called the Y combinator. Y=At. (Art (22)) (Az.t (22)) This term looks almost like the self-application of sa, but it is different in that it involves an additional function t in a subtle way. Consider an application Yt and let us see what we can learn about it using 3-reduction: Yt = (Az.t (z)) (Az.t (22)) ((Art (12)) (Art (22))) by 3-reduction noticing that the inner term is Yt t(Yt) So, Yt is equal to the function t applied to itself! One can use this to repeatedly unfold Yt. Yt=t(Yt)=t(t (Yt)) = t (t (t (Yt))) = --- This might seem like another form of an infinite loop, but it is actually quite useful. In fact, it is used to encode recursive functions in the lambda calculus. Consider the recursive definition of a function such as the factorial: define factorial = An. if (=n 1) 1 (*n (factorial (-1)) On the surface, this is a circular definition and cannot be expressed in lambda calculus. To resolve the difficulty, we first treat the right hand side of the definition as a function of "factorial": define define factorial = T factorial T=Af. An. if (n1)1 (*n (f(-1)) The definition of T is quite normal, but the first line is still a circular definition. However, this is exactly the kind of circularity that the Y combinator allows us to capture. The Y combinator satisfies the equality YT=T(YT). So, we can just say that factorial is YT and we get what we want without any circular definitions. Does this actually work? Here is a sample calculation: (YZ) 2 (YT) 1

Fig: 1