Задание №12. Машина Тьюринга: выполнение программы на ленте
Чтение таблицы состояний, пошаговое изменение ленты и проверка результата по двоичным разрядам.
В задаче даны число на ленте, начальное положение головки, её состояние и таблица команд. Требуется получить запись после остановки машины и перевести её в указанную систему счисления. Решение строится на последовательном выполнении команд: после каждого шага нужно знать, что записано на ленте, где находится головка и какое состояние выбирает следующую команду.
Как читается одна команда
Лента разделена на ячейки. В ячейке может стоять цифра, а может быть пусто. Пустую ячейку обозначают знаком \lambda — греческой буквой «лямбда». Его называют пустым символом. Ноль — цифра в записи числа. Пустая ячейка означает, что цифры на этом месте нет. В таблице для нуля и \lambda предусмотрены отдельные столбцы.
Головка читает и изменяет содержимое одной текущей ячейки. Состояние — метка этапа работы: оно позволяет по-разному обрабатывать один и тот же символ, например при проходе влево и при возврате. Состояния обозначают q_0, q_1 и так далее. Индекс различает метки, а не считает выполненные шаги.
Строку таблицы выбирает текущее состояние, столбец — символ под головкой. На их пересечении находится команда одного шага. Её выполнение называется переходом. Команда задаёт, что записать, куда двигаться и какое состояние принять:
| Часть команды | Что выполняется |
|---|---|
| Первый символ | Запись в текущую ячейку, даже если символ не меняется |
| \mathrm L или \mathrm R | Сдвиг влево или вправо после записи |
| \mathrm S | Остановка после записи, без сдвига |
| Метка состояния в конце команды | Состояние после этого шага |
Например, 0,\mathrm L,q_3 означает: записать ноль в текущую ячейку, сдвинуть головку на одну ячейку влево и принять состояние q_3. Следующая команда выбирается для символа в новой ячейке и состояния q_3. Пошаговая запись этих изменений называется трассой.
Значение \mathrm S здесь соответствует условиям рассматриваемых заданий. Пустая клетка таблицы означает, что команда для этой пары состояния и символа не задана; это не команда остановки. Если при ручном выполнении понадобилась такая клетка, причина может быть в неверной позиции, состоянии или направлении предыдущего шага.
Полный пример: прибавление единицы
В задаче о преобразовании числа 1023 ↗ на ленте находится его двоичная запись без ведущих нулей. Головка находится в ближайшей пустой ячейке справа от числа и имеет состояние q_0. Требуется десятичное значение результата.
1. Исходная запись и таблица
Число 1023 на единицу меньше 2^{10}=1024. Поэтому оно состоит из десяти двоичных единиц: 1023_{10}=1111111111_2. Слева и справа от них находятся пустые ячейки. Программа имеет следующий вид; тире отмечает отсутствие команды.
| Состояние | \lambda | 0 | 1 |
|---|---|---|---|
| q_0 | \lambda,\mathrm L,q_1 | — | — |
| q_1 | 1,\mathrm L,q_2 | 1,\mathrm S,q_2 | 0,\mathrm L,q_1 |
| q_2 | \lambda,\mathrm S,q_2 | — | — |
Начальная ячейка пуста, поэтому первой выбирается команда в строке q_0 и столбце \lambda. Ячейка остаётся пустой, головка сдвигается влево на последнюю единицу и переходит в q_1. Сами цифры пока не изменились.
2. Проход по единицам
В состоянии q_1 на единице выполняется 0,\mathrm L,q_1. Последняя единица превращается в ноль; головка переходит к следующей единице слева. Состояние осталось прежним, поэтому повторяется та же команда. После двух таких замен запись равна 1111111100, после трёх — 1111111000.
Эти шаги можно объединить в один этап: каждая команда заменяет ровно одну единицу нулём и переводит головку к следующей цифре слева. Все десять исходных цифр равны единице. Поэтому после десяти замен на их месте будут десять нулей, а головка окажется в пустой ячейке слева, всё ещё в состоянии q_1. Здесь повтор заканчивается: теперь головка читает другой символ.
3. Новая единица и остановка
Когда головка читает пустую ячейку, строка q_1 задаёт уже другую команду: 1,\mathrm L,q_2. В пустую ячейку записывается единица. Она становится новой крайней левой цифрой — старшим разрядом, поэтому запись принимает вид 10000000000. Головка сдвигается ещё на одну ячейку влево и оказывается в пустой ячейке в состоянии q_2.
Теперь выполняется \lambda,\mathrm S,q_2: текущая ячейка остаётся пустой, работа заканчивается. Головка остановилась слева от числа; полученная запись при этом сохранилась. В таблице видно, как каждый этап меняет ленту и положение головки.
| Выполненные команды | Результат этапа | Головка |
|---|---|---|
| Первая | Десять единиц без изменений | На правой единице, q_1 |
| Следующие десять | Десять нулей | Слева от записи, q_1 |
| Двенадцатая | Единица и десять нулей | Слева от новой единицы, q_2 |
| Тринадцатая | Запись сохранена | Остановка |
4. Десятичный ответ и смысл преобразования
Место цифры в записи числа называется разрядом, а значение единицы на этом месте — весом разряда. В двоичной записи веса справа налево равны 1,2,4,8,\ldots. У полученной единицы справа десять цифр, поэтому её вес равен 2^{10}. Все остальные цифры — нули и ничего не добавляют к сумме: 10000000000_2=1024_{10}. Ответ: 1024.
Эта программа прибавляет к двоичному числу единицу. Прибавление начинается с крайней правой цифры — младшего разряда. В двоичной системе 1+1=10_2: на этом месте записывается ноль, а единица переносится на соседнее место слева. Такой переход единицы в соседний разряд называют переносом. Первый встретившийся ноль должен стать единицей; соответствующая команда 1,\mathrm S,q_2 сразу заканчивает работу. В исходном числе нулей нет, поэтому перенос проходит всю запись и создаёт новый разряд. Такое объяснение проверяет трассу, но вывод о прибавлении единицы относится именно к этой таблице.
Похожие таблицы могут менять число иначе
Добавление разряда слева
В задаче о добавлении разряда к числу 2027 ↗ проход влево устроен иначе. Команды состояния q_1 сохраняют и нули, и единицы, поэтому исходная запись 11111101011 не меняется. На пустой ячейке слева машина записывает единицу, сдвигается ещё левее и останавливается.
В исходной записи 11 цифр. Новая единица получает вес 2^{11}=2048. Веса прежних цифр сохраняются, поскольку правый край записи остался на месте. Поэтому результат равен 2027+2048=4075. В задаче с исходным числом 2025 ↗ такой же проход даёт 2025+2048=4073.
Последняя запись при остановке
В задаче с записью единицы при остановке ↗ головка сначала проходит влево по числу 2027, сохраняя его цифры. От пустой ячейки она возвращается вправо в состоянии q_2. Старшая единица заменяется нулём, после чего головка идёт влево и принимает состояние q_3. Команда 1,\mathrm S,q_3 записывает единицу в пустую ячейку и только затем останавливает машину.
В начале записи вместо одной ведущей единицы теперь стоят две цифры 10. Прежняя единица с весом 2^{10}=1024 исчезла, а новая имеет вес 2^{11}=2048. Остальные цифры сохранили свои места, поэтому:
2027-1024+2048=3051.
Итоговая запись — 101111101011. В задаче с таким же изменением числа 2025 ↗ расчёт даёт 2025-1024+2048=3049.
Стирание старшей цифры
В задаче со стиранием старшей цифры числа 1514 ↗ исходная запись равна 10111101010. После прохода влево и возврата к началу команда \lambda,\mathrm R,q_3 стирает старшую единицу и переводит головку к следующей цифре. Этот ноль заменяется единицей при остановке. На ленте остаётся запись 1111101010.
Стирание делает ячейку пустой, но не сдвигает соседние цифры. Поэтому веса оставшихся цифр сохраняются: исчезла единица с весом 1024 и появилась единица с весом 512. Результат равен 1514-1024+512=1002.
Возможные ловушки
- Движение перед записью. Изменение попадёт в соседнюю ячейку. В примере с прибавлением единицы ↗ это нарушит перенос. В трассе сначала отмечается замена под головкой, затем её новая позиция.
- Остановка до записи. В примере с последней командой ↗ пропуск записи уберёт новую старшую единицу из результата. Команда с \mathrm S тоже сначала записывает символ.
- Выбор команды только по символу. В примере со стиранием цифры ↗ единица при проходе сохраняется, а после возврата стирается. Различие задаёт состояние, поэтому в трассе оно указывается рядом с позицией головки.
- Пустая ячейка как ноль. В примере с добавлением разряда ↗ ноль сохраняется, а в пустую ячейку записывается единица. Смешение этих символов изменит команду и результат. На ленте и в таблице они обозначаются отдельно.
Другие исполнители в старых материалах
В старых задачах этого номера встречаются Редактор, Робот, Чертёжник и построение строк. Для каждого исполнителя нужны свои правила: у Редактора — первая слева замена и порядок проверок; у Робота — положение в клетке и стены; у Чертёжника — сумма перемещений; при построении строк — повторения и позиции символов. Эти правила не заменяют таблицу машины Тьюринга. В ней каждый шаг зависит от состояния и символа в одной текущей ячейке.