Машина Тьюринга и состояния
Лента, состояние и положение головки: как локальные переходы определяют выполнение программы и изменение числа.
Машина Тьюринга выполняет программу над символами на ленте. За один шаг она читает и меняет содержимое одной ячейки, затем перемещается или останавливается. Из таких простых действий складывается преобразование всей записи: например, прибавление единицы к двоичному числу. Чтобы понять программу, нужно связать правило каждого шага с тем, что меняется на ленте.
Лента и алфавит
Лента разделена на ячейки и продолжается бесконечно в обе стороны. В рассматриваемых задачах двоичное число занимает несколько соседних ячеек; остальные пусты. Набор символов, которые машина может читать и записывать, называется алфавитом.
Здесь в ячейке может стоять цифра 0 или 1, а может быть пусто. Пустую ячейку обозначают знаком \lambda — греческой буквой «лямбда». Его называют пустым символом. Если обозначить алфавит буквой A, получим A=\{0,1,\lambda\}: внутри скобок перечислены все три возможных символа.
Например, число 101 занимает три соседние ячейки:
\cdots\;|\;\lambda\;|\;1\;|\;0\;|\;1\;|\;\lambda\;|\;\cdots
Ноль посередине — цифра числа. Ячейки с \lambda по краям пусты. Машина различает эти случаи: в таблице программы для 0 и для \lambda предусмотрены отдельные столбцы. Если команда предписывает записать \lambda вместо цифры, ячейка становится пустой: цифра стирается. Сама ячейка остаётся на месте, соседние цифры не сдвигаются.
Различие между цифрой и пустой ячейкой позволяет программе находить край числа. Например, в задаче о добавлении цифры слева ↗ машина сохраняет все встреченные цифры и движется влево. Только на пустой ячейке правило меняется: в неё записывается единица. Пустой символ здесь отмечает место, где заканчивается исходная запись.
Зачем нужны состояния
Символы читает и записывает головка. В каждый момент она находится над одной ячейкой. Однако одного прочитанного символа для выбора действия недостаточно: при первом проходе цифру может понадобиться сохранить, а после возврата — изменить.
Эти ситуации различает состояние — метка текущего этапа работы. Состояния обозначают q_0, q_1 и так далее. Индекс у буквы q только различает метки: он не считает шаги и не показывает число на ленте.
Например, в задаче со стиранием крайней левой цифры ↗ машина сначала проходит влево, сохраняя единицы. После возврата к началу числа она находится уже в другом состоянии и стирает первую единицу. Символ тот же, но этап работы изменился, поэтому нужна другая команда.
Как задаётся один переход
Переход — выполнение одной команды: запись символа, движение или остановка, выбор состояния после команды. В таблице программ рассматриваемых задач строку выбирает состояние, а столбец — символ под головкой. На их пересечении находится нужная команда; строки не выполняются подряд сверху вниз.
Движение на одну ячейку влево обозначается \mathrm L, вправо — \mathrm R. Знак \mathrm S в этих условиях означает остановку без сдвига. Во всех трёх случаях сначала записывается символ из команды. В другом описании исполнителя обозначения могут отличаться, поэтому их смысл задаёт условие.
Например, если в строке q_1 и столбце 1 стоит команда 0,\mathrm L,q_1, единица под головкой заменяется нулём, головка идёт влево, а состояние остаётся прежним. Если слева тоже единица, команда повторится. Если там ноль или пустая ячейка, потребуется другой столбец той же строки.
То же правило можно записать формулой. Текущее состояние обозначается q, прочитанный символ — a; команда задаёт записываемый символ b, действие головки d и состояние после шага q'. Штрих отличает новое состояние от прежнего, хотя они могут совпадать. Символ \delta («дельта») обозначает правило выбора команды:
\delta(q,a)=(b,d,q').
Для приведённого примера это \delta(q_1,1)=(0,\mathrm L,q_1). У каждой пары «состояние и символ» не более одной команды. Поэтому, если команда задана, следующий шаг определён однозначно. Это свойство называется детерминированностью.
Конфигурация и трасса
Для продолжения вычисления нужны содержимое ленты, положение головки и состояние. Вместе они образуют конфигурацию — полное описание машины в данный момент.
| Часть конфигурации | Зачем она нужна |
|---|---|
| Содержимое ленты | Показывает, что записано в ячейках |
| Положение головки | Указывает, какой символ читается сейчас |
| Состояние | Определяет строку таблицы команд |
В записи 101 головка над левой единицей и головка над правой единицей читают одинаковый символ. Но конфигурации различаются: после движения вправо в первом случае встретится ноль, во втором — пустая ячейка. Поэтому пошаговая запись выполнения, или трасса, сохраняет не только цифры на ленте, но и позицию головки со состоянием.
Как обосновать сокращённую трассу
Повторяющиеся шаги удобно описывать одним этапом. Основанием служит инвариант — утверждение, которое остаётся верным после каждого шага этого этапа. Сама лента при этом может меняться.
Например, головка начинает с правого края цепочки единиц и заменяет их нулями, двигаясь влево. После каждого такого шага обработанная часть исходной записи справа от головки состоит из нулей, а ещё не обработанная часть остаётся прежней. Следующая замена добавляет к обработанной части ровно одну ячейку, поэтому утверждение сохраняется.
Если исходных единиц десять, после десяти замен на их месте будут десять нулей. Головка окажется на пустой ячейке слева. Этот шаг требует отдельной проверки по таблице: прежняя команда выбиралась для единицы, а теперь прочитан другой символ.
Такое рассуждение объясняет и выход из повтора: с каждым шагом остаётся на одну необработанную единицу меньше. Но остановка всей программы зависит от последующих команд. Бесконечная лента сама по себе не означает ни обязательной остановки, ни бесконечной работы.
Символы и значение числа
После остановки на ленте остаётся запись, которую условие предлагает прочитать как число. Место цифры в этой записи называется разрядом. Крайний правый разряд — младший, крайний левый — старший. Вес разряда показывает значение единицы на этом месте. В двоичной записи веса справа налево равны 1,2,4,8,\ldots.
Например, в записи 101_2 единицы стоят на местах с весами 4 и 1, поэтому 101_2=1\cdot4+0\cdot2+1\cdot1=5_{10}. Ноль не добавляет ничего к сумме, но занимает своё место между единицами.
Общая формула складывает такие же вклады для записи любой длины. Пусть N — значение числа, k — количество цифр. Места нумеруются справа начиная с нуля; цифра на месте i обозначается b_i и имеет вес 2^i. Знак \sum означает сложение вкладов всех цифр:
N=\sum_{i=0}^{k-1}b_i2^i.
Добавление единицы слева от прежних k цифр увеличивает число на 2^k: правый край записи остаётся на месте, поэтому веса прежних цифр сохраняются. Для трёхзначной записи 101_2 получается 1101_2=5+2^3=13. Если же добавить ноль справа, прежние цифры окажутся на один разряд левее относительно нового края: 1010_2=2\cdot5=10. Поэтому удлинение записи само по себе ещё не определяет числовое действие программы.
Как по таблице отличить прибавление единицы от добавления цифры слева? Почему запись в последней команде может изменить ответ, даже если сразу после неё машина останавливается? Полные трассы и расчёты приведены в материале «Задание №12. Машина Тьюринга: выполнение программы на ленте».