Задание 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».

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

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

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

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

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

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

Решение

Разберём, что делает каждое состояние:

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

Одно и то же число 221 может получиться из нескольких исходных чисел (всего подходящих — 2 среди чисел до 733), поэтому надёжнее всего перебрать исходные числа по возрастанию и смоделировать программу для каждого.

Ответ: 221.

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

def run(n):
    b = bin(n)[2:]
    tape = {i: ch for i, ch in enumerate(b)}
    pos, state = len(b), "q0"
    while True:
        write, move, state = prog[(state, tape.get(pos, L))]
        tape[pos] = write
        if move == "S":
            break
        pos += -1 if move == "L" else 1
    s = "".join(tape[i] for i in sorted(tape) if tape[i] != L)
    return int(s, 2) if s else None

print(next(n for n in range(1, 10 ** 5) if run(n) == 221))

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