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

[Door]

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

[sulnedinfind]

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

[uvelichitel]

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

[sulnedinfind]

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

[DuMMeR]

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

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

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

[uvelichitel]

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