The Turing combinator

Curry’s combinator solves the problem of recursion, but not flawlessly. One of its shortcomings we have already noted: it merely declares recursion. The identity $\mathrm{Y}\,F$​${} =_\beta F\,(\mathrm{Y}\,F)$ rests on β-equality, and there is no direct reduction from $\mathrm{Y}\,F$ to $F\,(\mathrm{Y}\,F)$ — to close the loop one has to step “backward” (a conversion). Let us try to fix this: to build another fixed-point combinator that unfolds recursion by a genuine forward β-reduction rather than proclaiming it as an equality.

We obtain this reduction — $\Theta\,F$​${} \twoheadrightarrow_\beta F\,(\Theta\,F)$ — by “pushing” the function itself, as an argument, inside the self-application: take $G$​${} = \lambda x\,y.\,y\,(x\,x\,y)$ and set $\Theta$​${} = G\,G$. Then in two β-steps:

The function (in the role of $y$) is not lost here; on each turn it is applied anew to the recreated $\Theta\,F$​${} = G\,G\,F$, and that is why the equality turns into an honest reduction. Unfolding $G$, we get the final form of the Turing combinator:

Let us compute the same factorial as in the chapter on Curry’s combinator (the same template $F$, the same numeral $\overline{3}$): now every turn of the recursion is a genuine β-reduction, not a β-equality:

Both give $\overline{6}$; the only difference is the status of the unfolding step — an equality for Curry versus a reduction for Turing.

In practice the Turing combinator is almost never used — its role is theoretical: it shows that recursion is reachable by an honest reduction, without a step “backward”, and in this capacity it is the standard companion of Y in textbooks.

But both Curry and Turing are designed for normal order (call-by-name). Under strict, eager order (call-by-value) both diverge: the argument $F$ — that is, $\mathrm{Y}\,F$ or $\Theta\,F$ itself — is evaluated in advance and unfolds forever, never reaching any useful work. This problem is solved by the next combinator — Z.