Что проверяет задание
Актуальный КИМ - исполнитель МТ: лента, головка, таблица команд. Нужно найти итоговое слово (часто как десятичное число), количество символов или исходные параметры. Старый «Редактор» (замены в строке) больше не используется.
Определения
Машина Тьюринга, головка на бесконечной ленте. Команда: записать символ, сдвинуться (L / R / N / S) и сменить состояние.
Исполнитель Редактор (устаревший формат), машина, которая умеет заменять фрагменты текущей строки на другие фрагменты.
Команда замены «заменить (A, B)», найти в строке указанное вхождение фрагмента A и заменить его на B. Важно, какое именно вхождение берут: обычно первое слева.
Пока, цикл: команда повторяется, пока в строке есть указанный фрагмент или пока истинно условие.
Лента машины Тьюринга, бесконечная в одну или обе стороны последовательность клеток. В каждой клетке, символ алфавита или пусто.
Головка, указывает на текущую клетку. Команда читает символ под головкой, пишет новый, сдвигает головку и меняет состояние.
Состояние, внутренний режим исполнителя. От пары «состояние + текущий символ» зависит команда.
Терминальное состояние, состояние останова. После перехода в него исполнитель заканчивает работу.
Инвариант цикла, свойство строки, которое сохраняется на каждом шаге замены. По инварианту часто видно, чему равна длина или сумма цифр в конце, не разворачивая все шаги.
Расходящаяся замена, правило, которое может увеличить строку так, что цикл не закончится. На экзамене обычно подбирают порядок команд так, чтобы процесс был конечным.
Порядок команд
Если в программе несколько замен, результат зависит от того, какая проверяется первой. Замена более длинного фрагмента раньше более короткого, другое правило, чем наоборот.
Цикл «пока есть A, заменить A на B» полностью вычищает A только если B само не порождает новое A неконтролируемым образом.
Общий алгоритм решения
- Выписать алфавит, начальную строку и полный набор правил с порядком.
- Понять, конечен ли процесс: каждая замена должна приближать строку к виду, где цикл останавливается.
- Найти инвариант: что не меняется или меняется предсказуемо (количество определённых символов, чётность, разность счётчиков).
- Довести строку до конечного вида аналитически или аккуратным моделированием, если длина невелика.
- Вычислить требуемую характеристику: длину, сумму цифр, количество символов, само слово.
- Если дан результат и нужен старт, идти от конечного вида назад, обращая замены там, где обращение однозначно.