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 Y F\mathrm{Y}\,F =βF (Y F)=_\beta F\,(\mathrm{Y}\,F) rests on β-equality, and there is no direct reduction from Y F\mathrm{Y}\,F to F (Y F)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 — Θ F\Theta\,F ↠βF (Θ F)\twoheadrightarrow_\beta F\,(\Theta\,F) — by “pushing” the function itself, as an argument, inside the self-application: take GG =λx y. y (x x y)= \lambda x\,y.\,y\,(x\,x\,y) and set Θ\Theta =G G= G\,G. Then in two β-steps:

Θ F\displaystyle \Theta\,F =(G G) F  \displaystyle = (G\,G)\,F \; →β  (λy. y (G G y)) F  \displaystyle \to_\beta\; (\lambda y.\,y\,(G\,G\,y))\,F \; →β  F (G G F)\displaystyle \to_\beta\; F\,(G\,G\,F) =F (Θ F).\displaystyle = F\,(\Theta\,F).

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

Θ\displaystyle \Theta =(λx y. y (x x y)) (λx y. y (x x y)),Θ F\displaystyle = (\lambda x\,y.\,y\,(x\,x\,y))\,(\lambda x\,y.\,y\,(x\,x\,y)), \qquad \Theta\,F ↠βF (Θ F)\displaystyle \twoheadrightarrow_\beta F\,(\Theta\,F)
(1.26)

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

fac  3‾\displaystyle \mathbf{fac}\;\overline{3} =Θ F  3‾\displaystyle = \Theta\,F\;\overline{3} ↠βF (Θ F)  3‾\displaystyle \twoheadrightarrow_\beta F\,(\Theta\,F)\;\overline{3} ↠βmul  3‾  (Θ F  2‾)\displaystyle \twoheadrightarrow_\beta \mathbf{mul}\;\overline{3}\;(\Theta\,F\;\overline{2}) ↠βmul  3‾  (mul  2‾  (mul  1‾  (Θ F  0‾)))\displaystyle \twoheadrightarrow_\beta \mathbf{mul}\;\overline{3}\;(\mathbf{mul}\;\overline{2}\;(\mathbf{mul}\;\overline{1}\;(\Theta\,F\;\overline{0}))) ↠βmul  3‾  (mul  2‾  (mul  1‾  1‾))\displaystyle \twoheadrightarrow_\beta \mathbf{mul}\;\overline{3}\;(\mathbf{mul}\;\overline{2}\;(\mathbf{mul}\;\overline{1}\;\overline{1})) =6‾\displaystyle = \overline{6}

Both give 6‾\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 FF — that is, Y F\mathrm{Y}\,F or Θ F\Theta\,F itself — is evaluated in advance and unfolds forever, never reaching any useful work. This problem is solved by the next combinator — Z.