2 Краткая информация о задании 12

Краткая информация о задании 12

Задание 12 — про машину Тьюринга. С 2026 года прежний «Редактор» заменили этим исполнителем: машина ходит по бесконечной ленте, читает и переписывает символы по программе-таблице. Условие объёмное (описание работы занимает почти две страницы), но сам алгоритм всегда простой — нужно аккуратно его проследить.

Спрашивают либо результат работы (что останется на ленте), либо, наоборот, свойства исходных данных — например, наибольшее возможное число символов в начальной последовательности при заданном результате.

Проверяемые требования

Умение анализировать результат исполнения алгоритма формального исполнителя (машины Тьюринга).

Уровень сложности: повышенный.

Примерное время выполнения: 8 минут.

💡 Важный момент про способ решения

Задание 12 решается аналитически — трассировкой, а не кодом. Программа-эмулятор получилась бы длинной и ошибкоопасной, а на бумаге алгоритм прослеживается быстрее. Главное — понять механизм машины и вести пошаговую запись ленты.