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

Задание 12 ЕГЭ по информатике проверяет, умеете ли вы исполнить алгоритм для исполнителя с фиксированным набором команд; в демоверсии 2027 года это исполнитель МТ, машина Тьюринга с программой в виде таблицы. Решают его вручную: шаг за шагом отслеживают содержимое ленты, положение головки и её состояние.

Как решать

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

Ведите запись на бумаге. Выпишите ленту с числом в двоичной записи, отметьте под ней положение головки и текущее состояние. На каждом шаге найдите клетку таблицы на пересечении строки текущего состояния и столбца символа под головкой, запишите новый символ, сдвиньте головку и смените состояние. Работа заканчивается на команде с буквой S.

Прежде чем исполнять программу до конца, посмотрите, что делает каждое состояние. Обычно одно состояние только проводит головку вдоль записи, а другое меняет символы: заменяет 0 на 1 и 1 на 0 или переносит единицу при прибавлении. Когда смысл состояния понятен, остаток ленты можно дописать сразу.

В ответ записывают число, которое осталось на ленте, в десятичной системе счисления. Ведущие нули значение не меняют: запись 011000 означает 24.

Для проверки подойдёт короткая программа на Python: таблица переходов записывается словарём с ключом «состояние, символ», лента — словарём «номер ячейки — символ». Такая программа приведена в каждом примере.

Примеры с решением

Пример 1

Исполнитель МТ устроен так же, как в демоверсии ЕГЭ 2027 года. Лента разделена на ячейки с символами λ (пустая ячейка), 0 и 1. Команда «символ, сдвиг, состояние» записывает символ в текущую ячейку, сдвигает головку на одну ячейку (L — влево, R — вправо) или останавливает исполнителя (S) и переводит головку в новое состояние.

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

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

      λ          0          1
q0    λ, L, q1
q1    λ, S, q1   0, L, q1   0, L, q2
q2    λ, S, q2   1, L, q2   0, L, q2

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

Проверка ответа на Python

# Таблица программы: (состояние, символ в ячейке) -> (что записать, сдвиг, новое состояние)
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('0', 'L', 'q1'),
    ('q1', '1'): ('0', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '0'): ('1', 'L', 'q2'),
    ('q2', '1'): ('0', 'L', 'q2'),
}
tape = dict(enumerate(bin(38)[2:]))  # двоичная запись 38 в ячейках 0, 1, 2, ...
pos = len(tape)                      # головка в ближайшей ячейке справа от записи
state = 'q0'
while True:
    write, move, state = prog[(state, tape.get(pos, 'λ'))]
    tape[pos] = write
    if move == 'S':
        break
    pos += 1 if move == 'R' else -1
cells = ''.join(tape[i] for i in sorted(tape) if tape[i] != 'λ')
print(int(cells, 2))

Ответ: 24

Число 38 в двоичной системе — 100110. Состояние q0 переводит головку на последнюю цифру. В состоянии q1 головка идёт влево по нулям, ничего не меняя, а первую встреченную единицу заменяет нулём и переходит в q2. В состоянии q2 все цифры левее заменяются на противоположные, на пустой ячейке исполнитель останавливается. Младший ноль остаётся, единица второго разряда становится нулём, четыре левые цифры 1001 превращаются в 0110. На ленте остаётся 011000, то есть 24.

Пример 2

Исполнитель МТ и форма записи программы такие же, как в примере 1.

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

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

      λ          0          1
q0    λ, R, q1
q1    λ, L, q2   0, R, q1   1, R, q1
q2    1, S, q2   1, S, q2   0, L, q2

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

Проверка ответа на Python

prog = {
    ('q0', 'λ'): ('λ', 'R', 'q1'),
    ('q1', '0'): ('0', 'R', 'q1'),
    ('q1', '1'): ('1', 'R', 'q1'),
    ('q1', 'λ'): ('λ', 'L', 'q2'),
    ('q2', '1'): ('0', 'L', 'q2'),
    ('q2', '0'): ('1', 'S', 'q2'),
    ('q2', 'λ'): ('1', 'S', 'q2'),
}
tape = dict(enumerate(bin(47)[2:]))
pos = -1                             # головка в ближайшей ячейке слева от записи
state = 'q0'
while True:
    write, move, state = prog[(state, tape.get(pos, 'λ'))]
    tape[pos] = write
    if move == 'S':
        break
    pos += 1 if move == 'R' else -1
cells = ''.join(tape[i] for i in sorted(tape) if tape[i] != 'λ')
print(int(cells, 2))

Ответ: 48

Число 47 в двоичной системе — 101111. В состоянии q1 головка проходит запись слева направо до пустой ячейки и возвращается на последнюю цифру в состоянии q2. В q2 единицы заменяются нулями, пока не встретится ноль; ноль заменяется единицей, и исполнитель останавливается. Программа прибавляет к двоичному числу единицу: 101111 превращается в 110000, то есть в 48.

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

Потренироваться на тренажёре

Частые вопросы

Что делать, если в таблице нет команды для пары «состояние — символ»?

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

Можно ли решать задание 12 программой?

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

Как записать ответ, если на ленте остались ведущие нули?

Переведите запись в десятичную систему. Ведущие нули значение не меняют: 011000 — это 24.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 11 и задание 13.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.