# Mutually recursive definition of the terms to nonreqursive defenition with Y combinator.

Let there be a mutually recursive definition of the terms $${foo}$$ and $${bar}$$. In general, it can be written as $${foo} = P {foo} {bar}$$ $${bar} = Q {foo} {bar}$$ Here $$P$$ and $$Q$$ are some terms that contain neither $${foo}$$ nor $${bar}$$. Using the $$Y$$-combinator, find nonrecursive definitions for $${foo}$$ and $${bar}$$. Try to find the most "compact" solution, with the smallest number of $$Y$$-combinators possible

### My attempts

1. I tried to explicitly write $$foobar = PfoobarQfoobar$$, but it didn't work.
2. I tried to start an auxiliary $$bar'=\lambda f.Qf(bar'f)$$, and through it get a nonrecursive form with $$Y$$ combinator.
3. I tried to find the dependence by explicitly describing $$foo=Pfoobar=PPfoobarbar=...=P...Pfoobar...bar$$.
• Are you interpreting the 1st one as $foo=((P\text{ }foo)(bar))$? Feb 26 at 13:13
• @SohamSaha Yes. Feb 26 at 13:40

Mutual recursion can always be merged. If $$f,g$$ are mutually recursive, then define a third function $$h = \lambda x. x f g$$. Now you can express $$f = h (\lambda p q. p)$$ (Exercise: express $$g$$), and write a recursive equation using $$h$$ alone.

Another way to solve this is to solve for $$f$$ assuming you already know $$g$$. This gives you an expression $$f = \dots g\dots$$. Now substitute this into the equation for $$g$$ and you get a recursive equation for $$g$$ alone, which you can solve using Y.

• Do you talking something like this: for $foo$ -- $hP = f$ and $f = h(\lambda p q. p)$; for $bar$ -- $hQ = g$ and $g = h(\lambda p q. q)$ Feb 26 at 17:02

Disclaimer: I have been reading about lambda calculus and combinatory logic only for some months. But I think that I have an idea for this question. If you find any problems, please comment.

\begin{align*} \text{foo} &= \text{P foo bar}\\ &=\text{P foo (Q foo bar)}\\ &=\text{P foo (Q foo (Q foo (...)))}\\ &=\text{P foo (Y (Q foo))}\\ &=\text{P foo (S (K Y) Q foo)}\\ &=\text{S P (S (K Y) Q) foo}\\ &=\text{Y (S P (S (K Y) Q))} \end{align*}

Similarly we can extract a definition for $$\text{bar}$$

• $\text{P foo (Y (Q foo))}$ why we cant take outside foo at this step? like: $\text{P foo (Y (Q foo))}=(\lambda f. \text{P f (Y (Q f))) foo}$. Feb 26 at 15:53
• @replikeit of course we can, but I thought that the situation demanded a purely CL-type solution. If your context permits you to mix combinators with lambda calculus, I don’t think there should be any problem. But I am not experienced enough to know if that is admitted as good practice or not. Feb 26 at 16:14
• Actually I had done it that way too, but changed it to combinatorial format at the end. Feb 26 at 16:14
• Then this is right solution. Thank you. Feb 26 at 16:15
• You’re welcome :) @replikeit Feb 26 at 16:27