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