Комбинатор Тьюринга

Комбинатор Карри решает задачу рекурсии, но не безупречно. Один из его изъянов мы уже отметили: рекурсию он лишь декларирует. Тождество Y F=βF (Y F)\mathrm{Y}\,F =_\beta F\,(\mathrm{Y}\,F) держится на β-равенстве, а прямой редукции из Y F\mathrm{Y}\,F в F (Y F)F\,(\mathrm{Y}\,F) нет — чтобы замкнуть петлю, приходится шагать «назад» (конверсия). Попробуем это исправить: построить другой комбинатор неподвижной точки, который разворачивает рекурсию настоящей β-редукцией вперёд, а не провозглашает её равенством.

Добудем эту редукцию — Θ F↠βF (Θ F)\Theta\,F \twoheadrightarrow_\beta F\,(\Theta\,F) — «протолкнув» саму функцию аргументом внутрь самоаппликации: возьмём G=λx y. y (x x y)G = \lambda x\,y.\,y\,(x\,x\,y) и положим Θ=G G\Theta = G\,G. Тогда за два шага β-редукции:

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

Функция (в роли yy) здесь не теряется, а на каждом витке заново применяется к воссозданному Θ F=G G F\Theta\,F = G\,G\,F; поэтому равенство и превращается в честную редукцию. Разворачивая GG, получаем окончательный вид комбинатора Тьюринга:

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

Посчитаем тот же факториал, что и в разделе про комбинатор Карри (тот же шаблон FF, то же число 3‾\overline{3}), только теперь каждый виток рекурсии — настоящая β-редукция, а не β-равенство:

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

Оба дают 6‾\overline{6}; разница лишь в статусе шага развёртки — равенство у Карри против редукции у Тьюринга.

На практике комбинатор Тьюринга почти не встречается — его роль теоретическая: он показывает, что рекурсия достижима честной редукцией, без шага «назад», и в этом качестве он стандартный спутник Y в учебниках.

Но и Карри, и Тьюринг рассчитаны на нормальный порядок (call-by-name). При строгом, энергичном порядке (call-by-value) оба расходятся: аргумент FF — то есть сам Y F\mathrm{Y}\,F или Θ F\Theta\,F — вычисляется заранее и разворачивается бесконечно, так и не дойдя до полезной работы. Эту проблему решает следующий комбинатор — Z.