Задание 12 ЕГЭ: машина Тьюринга: результат программы

Машина Тьюринга: двоичная запись числа на ленте. Тема номера — машина тьюринга. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a₀, a₁, …, a_n–1}), включая специальный пустой символ a₀.

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q = {q₀, q₁, …, q_n–1}. В начальный момент времени головка находится в начальном состоянии q₀.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может изменить символ в текущей ячейке и переместиться в соседнюю ячейку слева или справа от неё. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из трёх символов «L», «R», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.

Например, команда 0, L, q₃ выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q₃.

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «λ». В начальный момент времени головка находится на неизвестном расстоянии справа от самого правого символа «Z».

Программа

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X».

Возможное начальное состояние исполнителя:

Конечное состояние исполнителя после завершения выполнения программы:

Выполните задание.

На ленте в соседних ячейках записано двоичное представление числа 397 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.

Программа работы исполнителя:

Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.

Решение

397 = 110001101₂ (9 разрядов), головка стоит справа от числа. Что делают состояния:

• q₀ — на «λ» оставляет «λ», сдвигается влево и переходит в q₁.
• q₁ — проходит по цифрам влево, не меняя их; на «λ» пишет «1», сдвигается влево и переходит в q₂.
• q₂ — на «λ» пишет «1», сдвигается вправо и переходит в q₃.
• q₃ — проходит по цифрам вправо, не меняя их; на «λ» пишет «0» и останавливает машину.

Смены состояний по тактам (подчёркнута ячейка, которую головка обозревает после такта):

На ленте осталось 111100011010₂ = 3866.

Проверка моделированием программы:

L = "λ"
prog = {("q0", L): (L, "L", "q1"),
        ("q1", L): ("1", "L", "q2"),
        ("q1", "0"): ("0", "L", "q1"),
        ("q1", "1"): ("1", "L", "q1"),
        ("q2", L): ("1", "R", "q3"),
        ("q3", L): ("0", "S", "q3"),
        ("q3", "0"): ("0", "R", "q3"),
        ("q3", "1"): ("1", "R", "q3")}

b = bin(397)[2:]
tape = {i: ch for i, ch in enumerate(b)}
pos, state = len(b), "q0"          # ближайшая справа ячейка
steps = 0
while True:
    sym = tape.get(pos, L)
    write, move, state = prog[(state, sym)]
    tape[pos] = write
    steps += 1
    if move == "S":
        break
    pos += -1 if move == "L" else 1

s = "".join(tape[i] for i in sorted(tape) if tape[i] != L)
print(s, int(s, 2))

Решить такую задачу — новый вариант с проверкой