А-машина Тьюринга и кофе-машина Хоара пит-стоп

[@Door]

Может не в тему, но хочу всем посоветовать «Читаем Тьюринга» — Чарлз Петцольд — очень интересно и хорошо написано! И спасибо за статью

[@sulnedinfind]

А ссылку на оригинал? Судя по поросюшкам, что-то из Милевского?

[@uvelichitel]

Текст авторский, но разумеется компиляция а не исследование. Картинки, каюсь понадерганы. Рисовать я не умею.

[@sulnedinfind]

Тогда извините и спасибо за статью :)

[@DuMMeR]

Заметим, что можно редуцировать в произвольном порядке и получить при этом равнозначный результат.

Так ведь аппликативный порядок не всегда приводит к нормальной форме, а нормальный всегда, если это возможно. Тот же традиционный пример:

(λx.y) ((λx.x x) (λx.x x))

[@uvelichitel]

Ну точное, развернутое описание возможных стратегий редукции и order of evaluation — это тема для отдельной статьи. В SICP две главы.