Как построить машину Тьюринга: пошаговое решение

Дано: на ленте записано двоичное число $1011$ (это $11$ в десятичной записи), головка стоит над старшим разрядом, остальные клетки пустые. Найти: машину Тьюринга, которая прибавит к этому числу единицу, то есть её алфавит, состояния, таблицу переходов и трассировку до остановки.

Схема решения всегда одна: сначала проход вправо до конца числа, потом возврат влево с обработкой переноса. Ответ: достаточно двух рабочих состояний и шести команд; машина останавливается через 8 тактов, на ленте остаётся $1100$, то есть $12$. Калькулятор сверху прогоняет эту же программу такт за тактом: подвинь ползунок числа, и трассировка перестроится, а по длине хвоста из единиц сразу видно, докуда дойдёт перенос.

Решение по шагам

Дано. Слово $1011$ на ленте, слева и справа пустые клетки, головка над старшим символом.

Найти. Внешний алфавит, состояния, таблицу переходов, трассировку и заключительную конфигурацию.

Шаг 1. Внешний алфавит. На ленте встречаются только цифры двоичной записи и пустая клетка, поэтому

$$A = \{\, 0,\ 1,\ \lambda \,\},$$

где $\lambda$ - пустой символ. Он полноправный: по нему машина узнаёт, что число кончилось, и без него остановиться было бы не на чем.

Шаг 2. Состояния и их смысл. Прибавление единицы распадается ровно на две работы, значит, и рабочих состояний нужно два. Состояние $q_1$ - проход вправо: машина не трогает разряды, а просто ищет конец числа. Состояние $q_2$ - перенос: машина идёт справа налево и разбирается с разрядами. Плюс заключительное состояние $q_0$, в котором команд нет и работа кончается:

$$Q = \{\, q_0,\ q_1,\ q_2 \,\}.$$

Договоримся о нумерации клеток: старший символ слова лежит в клетке 1, значит, клетки числа это 1, 2, 3, 4, справа от него пустая клетка 5, слева пустая клетка 0. Ровно такую разметку показывает шапка трассировки в калькуляторе.

Шаг 3. Таблица переходов. Клетка таблицы на пересечении состояния и символа содержит три вещи: что записать, куда сдвинуть головку ($R$ вправо, $L$ влево, $N$ на месте) и в какое состояние перейти.

Читается она так. В $q_1$ и ноль, и единица переписываются сами в себя со сдвигом вправо: по дороге к концу числа разряды не меняются. Пустая клетка значит, что число кончилось: головка разворачивается влево и переходит в $q_2$. В $q_2$ единица становится нулём и перенос идёт дальше, ноль становится единицей и машина останавливается, а пустая клетка слева означает переполнение разрядной сетки, и там дописывается новая старшая единица.

Шаг 4. Трассировка. Конфигурация машины это тройка: слово на ленте, положение головки и текущее состояние. Такт это применение одной команды. Выписываем все такты для слова $1011$:

Первые четыре такта машина едет вправо, на пятом упирается в пустую клетку и разворачивается. Дальше идёт арифметика: два младших разряда были единицами и гасятся в нули (такты 5 и 6), а третий справа разряд с нулём принимает перенос и машина уходит в $q_0$.

Ответ. Машина задана алфавитом $A = \{0, 1, \lambda\}$, состояниями $q_0, q_1, q_2$ и шестью командами таблицы; на слове $1011$ она делает 8 тактов и оставляет на ленте $1100$, что в десятичной записи даёт $11 + 1 = 12$.

Как записывается команда и что значит детерминированность

Команду принято писать одной строкой в формате

$$q_i\, a_j \to a_k\, D\, q_m, \qquad D \in \{L, R, N\},$$

то есть «находясь в состоянии $q_i$ и видя символ $a_j$, запиши в клетку $a_k$, сдвинь головку по направлению $D$ и перейди в $q_m$». Наша программа в таком виде занимает шесть строк, и калькулятор сверху печатает их под трассировкой целиком.

Требование детерминированности звучит просто: на каждую пару «состояние и символ» приходится не больше одной команды. В таблице это значит, что в клетке либо ровно одна тройка, либо прочерк. Если бы в $q_2$ на символ $1$ стояли две разные команды, машина перестала бы быть детерминированной и превратилась бы в недетерминированную модель, где вычисление ветвится в дерево.

Пустая клетка таблицы означает остановку: команды нет, машина стоит, и поэтому для $q_0$ строку вообще не заводят. Результат это просто то, что осталось на ленте в заключительной конфигурации.

Почему машина действительно прибавляет единицу

Возьми обычное сложение столбиком и прибавь единицу к младшему разряду. Пока в разряде стоит единица, сумма даёт $1 + 1 = 10$: в разряде остаётся ноль, а единица уходит в перенос влево. Как только встретился ноль, он превращается в единицу и перенос гасится. Цепочка обрывается, старшие разряды остаются нетронутыми.

Состояние $q_2$ повторяет этот школьный алгоритм буквально: команда «$1 \to 0$, влево» значит «разряд обнулился, перенос жив», а «$0 \to 1$, стоп» значит «перенос погашен». Третий случай, пустая клетка в $q_2$, отвечает числу из одних единиц: для $111$ перенос проходит все разряды насквозь, машина пишет единицу на свободном месте слева и получает $1000$.

Может показаться, что состояние $q_1$ лишнее и можно начать прямо с младшего разряда. Но головка стоит над старшим символом, а перенос идёт справа налево, и перепрыгнуть в конец слова машина не умеет: единственный способ узнать, где кончается число, это дойти до пустой клетки.

Сколько тактов работает машина

Число тактов легко посчитать заранее. Пусть в числе $n$ разрядов, а младших разрядов, подряд равных единице, ровно $k$. Тогда машина делает $n$ тактов на проход вправо, один такт на разворот у пустой клетки, $k$ тактов на гашение единиц и ещё один на запись итоговой единицы:

$$T = n + 1 + k + 1 = n + k + 2.$$

Для нашего слова $1011$ получается $n = 4$, $k = 2$ и $T = 8$ - сходится с трассировкой. Для $10111$ выйдет $5 + 3 + 2 = 10$ тактов, для $111$ получится $3 + 3 + 2 = 8$. Худший случай это число из одних единиц, где $k = n$ и $T = 2n + 2$, то есть время растёт линейно по длине записи. Такая оценка и есть сложность алгоритма на модели Тьюринга, а как её записывают через $O$-нотацию, разобрано в задаче про оценку сложности алгоритма.

Другие машины на той же ленте

Смена задачи меняет программу, но не схему рассуждения: сначала алфавит, потом роли состояний, потом таблица. Оба варианта ниже прогоняются в калькуляторе сверху чипами выбора.

Унарная запись. Число $N$ это $N$ палочек подряд, прибавить единицу значит дописать палочку в конец, переноса нет вовсе. Хватает одного состояния и двух команд: «$1 \to 1$, вправо, $q_1$» и «$\lambda \to 1$, стоп, $q_0$»; для числа 5 выходит 6 тактов. Плата за простоту программы это длина ленты, растущая как само число.

Инверсия разрядов. Задача «заменить каждый ноль на единицу и наоборот» решается одним проходом: «$0 \to 1$, вправо», «$1 \to 0$, вправо», «$\lambda \to \lambda$, стоп». Возврата нет, потому что разряды независимы, и на слове $1011$ машина остановится через 5 тактов со словом $0100$.

Из таких кирпичиков собираются сколь угодно сложные программы, а саму программу можно закодировать словом и подать на вход другой машине, получив универсальную машину Тьюринга; на этом же пути возникает проблема остановки. Есть и равносильные модели с другой записью, например нормальные алгорифмы Маркова.

Частые ошибки

• Забывают команду для пустого символа. Без строки $\lambda$ в $q_1$ машина уедет вправо по пустой ленте и не остановится: пустой символ обязан быть и в алфавите, и в таблице.
• Начинают перенос со старшего разряда. Головка стоит слева, и соблазн прибавлять прямо там велик, но перенос в позиционной записи идёт справа налево. Без прохода $q_1$ получится не то число.
• Теряют случай числа из одних единиц. Для $111$ перенос выходит за левый край слова, и без команды на $\lambda$ в $q_2$ машина сломается ровно на этом входе.
• Пишут сдвиг после смены состояния. В команде $q_i a_j \to a_k D q_m$ все три действия происходят за один такт: запись, сдвиг, смена состояния. Трассировка, где символ записали в одном такте, а сдвинулись в следующем, неверна.
• Дублируют команды. Две разные команды на одну пару «состояние и символ» ломают детерминированность. В таблице переходов каждая клетка заполняется ровно один раз.
• Путают заключительное состояние с рабочим. Из $q_0$ переходов нет: лента больше не меняется, и строку «$q_0$: ничего не делать» дописывать не нужно.

FAQ

Сколько состояний нужно машине для прибавления единицы? Два рабочих плюс заключительное. Меньше не получится: проход к концу числа и обработка переноса это разные режимы, и различать их машина может только состоянием, потому что символ под головкой в обоих случаях один и тот же.

Обязательно ли начинать с левого края слова? Нет, стартовая конфигурация задаётся условием задачи. Если в методичке головка изначально стоит над младшим разрядом, состояние $q_1$ вообще не нужно, программа сокращается до трёх команд. Важно только, чтобы трассировка соответствовала заявленному началу.

Чем таблица переходов отличается от графа состояний? Содержанием ничем, это две формы записи одной программы: в таблице строка это состояние, а столбец символ, в графе состояния это вершины, а команды подписанные дуги. Таблицей проще проверять детерминированность.

Что писать в ответе к такой задаче? Четыре вещи: алфавит, множество состояний с указанием начального и заключительного, таблицу переходов и трассировку на заданном входе. Словесного описания алгоритма без таблицы недостаточно.

Коротко

1. Выписываем внешний алфавит: цифры записи плюс пустой символ, у нас $A = \{0, 1, \lambda\}$.
2. Делим алгоритм на режимы и даём каждому состояние: $q_1$ едет вправо до конца числа, $q_2$ обрабатывает перенос справа налево, $q_0$ заключительное.
3. Заполняем таблицу переходов в формате $q_i a_j \to a_k D q_m$; каждая клетка заполняется не больше одного раза.
4. Проверяем крайние случаи: число из одних единиц требует отдельной команды на пустой символ в $q_2$.
5. Трассируем вход такт за тактом: для слова $1011$ машина делает 8 тактов и оставляет на ленте $1100$, то есть $11 + 1 = 12$.