Об одном красивом неизвестном решении одной известной задачи

«Каждый из нас лишь выиграет, создавая время от времени «игрушечные» программы с заданными искусственными ограничениями, заставляющими нас до предела напрягать свои способности. Искусство решения мини задач на пределе своих возможностей оттачивает наше умение для реальных задач»

Дональд Кнут (с)

Как известно, на машине Тьюринга (далее МТ) запрограммировать можно всё, что мы вообще считаем программируемым, но в реальности программы на МТ настолько громоздкие, что МТ редко используется даже в академических примерах. И тем не менее в некоторых отдельных случаях с помощью МТ получается написать небольшую программу, на КДПВ изображена программа из 5 состояний на алфавите из 3 символом. Если вы изучали программирование, то задачу, которую решает эта программа, вы скорее всего встречали. Если я сумел вас заинтересовать, то приглашаю в небольшое приключение по реверс инженирингу МТ.

Материал статьи предоставлен Владимиром Пинаевым

Читать далее