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

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

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

Θ 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).

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

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

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

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}

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

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

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