Задание №12. Короткий конспект
Порядок выполнения команды машины Тьюринга, отслеживание состояния и проверка двоичного результата.
Головка читает и изменяет одну текущую ячейку ленты. Состояние — метка этапа работы: q_0, q_1 и так далее. Строку таблицы выбирает состояние, столбец — символ под головкой. Ответ определяется по записи, оставшейся после остановки.
Одна команда
| Обозначение | Смысл |
|---|---|
| \lambda | «Лямбда», пустая ячейка. Запись \lambda стирает цифру без сдвига соседних |
| \mathrm L | На одну ячейку влево после записи |
| \mathrm R | На одну ячейку вправо после записи |
| \mathrm S | Запись, затем остановка без сдвига |
| 0,\mathrm L,q_3 | Записать ноль, сдвинуться влево, принять состояние q_3 |
Значение \mathrm S соответствует рассматриваемым условиям. Пустая клетка таблицы означает отсутствие команды, а не остановку.
Порядок решения
- Число переводится в систему счисления ленты. Рядом с цифрами отмечаются пустые ячейки, начальная позиция головки и состояние.
- По состоянию и символу выбирается команда. Сначала меняется содержимое текущей ячейки, затем выполняется движение или остановка.
- После шага записываются лента, позиция головки и состояние. Такая пошаговая запись называется трассой.
- Повторяющиеся шаги объединяются, если понятно, какие ячейки они обработают и где изменится символ или состояние.
- После остановки итоговая запись переводится в систему счисления ответа. Пустые ячейки по краям в число не входят.
Проверка по разрядам
Разряд — место цифры; вес разряда — значение единицы на этом месте. В двоичной записи веса справа налево: 1,2,4,8,\ldots. Номер разряда i отсчитывается от нуля справа, его вес равен 2^i.
При неизменном правом крае записи замена нуля единицей добавляет вес разряда, обратная замена вычитает его. Новая единица слева от прежних k цифр добавляет 2^k. Например, единица и десять нулей дают 2^{10}=1024.
Возможные ловушки
- Сдвиг раньше записи: изменится соседняя ячейка. Порядок команды: запись → движение → новое состояние.
- Пропуск записи при остановке: потеряется последняя замена, как в задаче с новой старшей единицей ↗. Запись выполняется и перед \mathrm S.
- Выбор только по символу: в другом состоянии та же единица может стираться вместо сохранения. Состояние учитывается на каждом шаге.
- Прибавление единицы по сходству таблиц: добавление разряда слева ↗ меняет число иначе. Действие определяется всеми выполненными командами.