Как устроена машина Тьюринга и где проходит граница вычислимого

Интерактивная статья ведёт от устройства машины к пределам вычислений. У неё четыре части: лента, головка, программа и состояние. Пять команд позволяют печатать символ, двигать головку, менять состояние и останавливать выполнение.

Примеры запускаются в тексте и прокручиваются пошагово вперёд или назад. Сначала машина бесконечно печатает нули, затем чередует 0 и 1 и складывает 2 и 6 в двоичной записи.

Дальше разбор «Turing Machines» переходит к задаче остановки: нельзя написать программу, которая по любой программе и входным данным наверняка определит, завершится вычисление или будет идти вечно. Через этот предел объясняется полнота по Тьюрингу: система полна, если может смоделировать машину Тьюринга.

Читать стоит тем, кто хочет связать определение с исполняемыми примерами и понять границы алгоритмов.