Tree calculus: как объяснить теорию вычислений маме за час
Tree calculus — минимальное, модульное, тьюринг-полное и рефлексивное исчисление, где программы и данные представлены как бинарные деревья. Автор визуально объясняет правила редукции, показывая, как из трёх простых правил строится вся вычислительная мощь. Он проверил теорию на своей маме: после часа объяснений она смогла вручную выполнить редукции для «not true → false» и «not false → true», никогда не слышав о λ-исчислении.
Я проверил эту теорию на своей маме. После менее чем часа объяснений и набросков на бумаге она успешно выполнила редукции «not false → true» и «not true → false» и поняла, что происходит. Ого!