Разборы · ЕГЭ, задание 12

Задание 12 ЕГЭ по информатике: машина Тьюринга

Что проверяет задание

В задании 12 дана программа исполнителя МТ (машины Тьюринга) и начальное содержимое ленты. Нужно понять, что сделает программа, и записать результат — например, получившееся число. 1 балл.

Что нужно знать

• Лента разбита на ячейки, в каждой — один символ; пустой символ обозначают λ. Головка в каждый момент смотрит на одну ячейку и находится в одном из состояний q₀, q₁, …
• Программа — таблица: строки — состояния, столбцы — символы. В клетке команда из трёх частей: что записать, куда сдвинуться (L — влево, R — вправо, S — стоп), в какое состояние перейти.
• Сначала записывается символ, потом происходит сдвиг.

Как решать

1. Прочитайте программу по строкам: что делает каждое состояние. Обычно одно состояние «проходит» по цифрам, не меняя их, другое что-то дописывает или заменяет.
2. Выполните программу на короткой ленте вручную, записывая ленту и положение головки после каждого такта.
3. Обобщите на исходные данные или смоделируйте работу программой.

Пример из демоверсии 2027

На ленте двоичная запись числа 2025, головка стоит в ближайшей ячейке справа от неё. Программа:

• q₀, λ → λ, L, q₁;
• q₁, λ → 1, L, q₂; q₁, 0 → 0, L, q₁; q₁, 1 → 1, L, q₁;
• q₂, λ → λ, S, q₂.

Запишите получившееся число в десятичной системе.

Решение. q₀ делает шаг влево на последнюю цифру. q₁ идёт влево по цифрам, не меняя их, а в первой пустой ячейке слева пишет 1 и переходит в q₂, которое останавливает машину. Итог: к двоичной записи 2025 = 11111101001₂ (11 цифр) слева приписана единица. Это 2¹¹ + 2025 = 2048 + 2025 = 4073.

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

b = bin(2025)[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)
print(s, int(s, 2))                     # 111111101001 4073

Типичные ошибки

• Сдвигают головку до записи символа — сначала запись, потом сдвиг.
• Путают L и R или начальное положение головки: читайте условие про начальную ячейку внимательно.
• Записывают в ответ двоичное число, когда спрашивают десятичное.

Потренироваться: задание 12 новые варианты с проверкой ответа