Что означает команда «0, L, q_(3)» в машине Тьюринга?

Записать в текущую ячейку 0, сдвинуться в соседнюю слева ячейку и перейти в состояние q_(3). Сдвиг идёт после записи, R сдвигает вправо, S завершает работу после записи.

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

Задание 12до 1 баллаисполнитель Редактор и машина Тьюринга

Раздел: Алгоритмы и программирование
Максимальный балл: 1 балл
Уровень: повышенный
Что проверяет: Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд
Что нужно сделать: Выполнить программу исполнителя с фиксированным набором команд и найти результат или исходные данные.
Как записать ответ: только число: целое, без пробелов и единиц измерения
Время: Около 6 минут по обобщённому плану ФИПИ
Элемент кодификатора: 3.3
Компьютер: Специальное ПО по плану ФИПИ не нужно: задание решают рассуждением, программа — для проверки
Файл к заданию: Нет — все данные в условии
В 2026 году: Тоже задание 12

Решать варианты КЕГЭ целиком →Практика на этой странице ↓

Задание 12 ЕГЭ по информатике 2027 года проверяет, по формулировке обобщённого плана ФИПИ, «умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд». Исполнителей два. Программа машины Тьюринга задана таблицей: строки — состояния головки, столбцы — символы на ленте, в клетках — команды «что записать, куда сдвинуться, в каком состоянии продолжить». Программа Редактора — циклы «ПОКА нашлось (…)» и команды «заменить (v, w)» над строкой цифр.

Файла к заданию нет, специализированное ПО не требуется: данные есть в условии, ответ — одно целое число, его вводят в станции КЕГЭ без пробелов. Уровень повышенный, по обобщённому плану около 6 минут, за верный ответ — 1 балл. В 2027 году тематика не менялась: в спецификации сказано «Изменения структуры КИМ отсутствуют», среди новых тем заданий 10, 13 и 23 задание 12 не названо. Средний процент выполнения в 2026 году — 60,3 (в 2025-м — 49,6).

Ниже — три типа задания с разбором и решением на Python; разбор демоверсии 2027 года и типичные ошибки — в конце, тренажёр с заданиями банка — сразу под этим текстом.

Тренажёр задания 12

Десять заданий номера 12 из банка тренажёра — с файлами, как на станции КЕГЭ. Решайте в песочнице Python прямо на странице или у себя; ответ проверяется по ключу, после проверки — верный ответ, разбор и решение на Python, а при ошибке — разбор от ИИ. Кнопка «Ещё 5 таких» у типа задания ниже даёт задания одного типа.

Банк тренажёра · Задание 12Без регистрации

Задание 12. Исполнитель с фиксированным набором команд

1 балл

Исполнитель Редактор получает на вход строку цифр и преобразует её.

Редактор может выполнять две команды, где v и w – некоторые последовательности символов (возможно, пустые): заменить (v, w) – заменить первое вхождение последовательности v в строке на последовательность w; нашлось (v) – проверить, входит ли последовательность v в строку (команда возвращает «да» или «нет»).

Дана программа для исполнителя Редактор:

НАЧАЛО
ПОКА нашлось (11)
   заменить (11, 2)
КОНЕЦ ПОКА
ПОКА нашлось (22)
   заменить (22, 1)
КОНЕЦ ПОКА
КОНЕЦ

Исходная строка состояла только из цифр «1», их количество неизвестно.

После выполнения программы в строке оказалось ровно 58 цифр «1».

Определите наименьшее возможное количество цифр в исходной строке.

Ответ

Целое число без пробелов, точек и других знаков.

Ответ — как на станции КЕГЭ: число или буквы без пробелов, у пары и таблицы — по клеткам. Проверка по ключу — без регистрации, при ошибке — разбор от ИИ.

Варианты целиком →

Загружаем задание…

Задание 12 вместе с остальными — в вариантах целиком.

Типы задания 12 с решением

Машина Тьюринга над двоичной записью числа

Пример условия

На ленте машины Тьюринга записана двоичная запись числа 182 без ведущих нулей, остальные ячейки заполнены символом λ. Головка стоит в ближайшей справа от записи ячейке, состояние q₀. Программа задана таблицей:

       λ              0              1
q_{0}  λ, L, q_{1}
q_{1}  1, S, q_{1}    0, L, q_{1}    1, L, q_{1}

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

1. Переведите таблицу в правила: паре «состояние — символ» соответствует тройка «записать, сдвиг, новое состояние». 2. Головка начинает в пустой ячейке справа, поэтому первый такт только переносит её на правую цифру числа. 3. Ведите трассировку: сначала запись, затем сдвиг; S завершает работу после записи. 4. Прочитайте непустые ячейки подряд и переведите запись в десятичную систему.

На примере: 182 = 10110110₂. В q₀ машина видит λ и уходит на последнюю цифру, затем в q₁ идёт влево, не меняя цифры, и в пустой ячейке слева по команде 1, S, q₁ записывает 1 — новый старший разряд. Получилось 110110110₂ = 256 + 182 = 438.

Решение на Python

n = 182
bits = list(bin(n)[2:])  # двоичные цифры числа, старшая — первая

# лента: список ячеек, головка стоит в пустой ячейке справа от записи
tape = bits + ['λ']
head = len(bits)

# программа МТ: (состояние, символ) -> (записать, сдвиг, новое состояние)
rules = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', '0'): ('0', 'L', 'q1'),
    ('q1', '1'): ('1', 'L', 'q1'),
    ('q1', 'λ'): ('1', 'S', 'q1'),
}

state = 'q0'
while True:
    write, move, state = rules[state, tape[head]]
    tape[head] = write          # сначала запись в текущую ячейку
    if move == 'S':             # S — остановка после записи
        break
    if move == 'L':
        head -= 1
        if head < 0:            # уходим за левый край — удлиняем ленту
            tape.insert(0, 'λ')
            head = 0
    else:
        head += 1
        if head == len(tape):
            tape.append('λ')

binary = ''.join(ch for ch in tape if ch != 'λ')
print(int(binary, 2))

Ответ: 438

Исполнитель Редактор: сколько цифр останется после программы

Пример условия

Дана программа для исполнителя Редактор:

НАЧАЛО
ПОКА нашлось (11) ИЛИ нашлось (22)
   ЕСЛИ нашлось (11)
   ТО заменить (11, 3)
   ИНАЧЕ заменить (22, 3)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
ПОКА нашлось (33)
   заменить (33, 1)
КОНЕЦ ПОКА
КОНЕЦ

Дана строка из 158 цифр «1», за которыми следуют 92 цифры «2». Сколько цифр «1» будет в строке после выполнения программы?

1. Разделите программу на две части: цикл по парам 11 и 22, затем цикл по тройкам. 2. Строку выписывать не нужно — считайте парами: 158 единиц дают 79 троек, 92 двойки — ещё 46. 3. После первой части единиц не остаётся, все тройки стоят одним блоком: 79 + 46 = 125. 4. Во второй части замена 33 → 1 убирает две тройки и добавляет единицу, значит, единиц будет 125 // 2 = 62; одна тройка останется.

На примере: ответ — 62 цифры «1».

Решение на Python

# начальная строка: блок единиц, за ним блок двоек
s = '1' * 158 + '2' * 92

# первая часть: заменяем первое вхождение 11 или 22 на тройку
while True:
    i = s.find('11')
    j = s.find('22')
    if i == -1 and j == -1:
        break
    if i != -1:
        s = s[:i] + '3' + s[i + 2:]
    else:
        s = s[:j] + '3' + s[j + 2:]

# вторая часть: тройки попарно превращаются в единицы
while '33' in s:
    k = s.find('33')
    s = s[:k] + '1' + s[k + 2:]

print(s.count('1'))

Ответ: 62

Исполнитель Редактор: наименьшая исходная строка

Пример условия

Дана программа:

НАЧАЛО
ПОКА нашлось (11)
   заменить (11, 2)
КОНЕЦ ПОКА
ПОКА нашлось (22)
   заменить (22, 1)
КОНЕЦ ПОКА
КОНЕЦ

Исходная строка состояла только из цифр «1», их количество неизвестно. После выполнения программы в строке оказалось ровно 43 цифры «1». Определите наименьшее возможное количество цифр в исходной строке.

1. Обозначьте исходную длину через N. Первый цикл заменяет пару 11 на 2, поэтому остаётся N // 2 двоек и, если N нечётно, ещё одна единица. 2. Второй цикл заменяет пару 22 на 1: из N // 2 двоек получается N // 4 единиц. 3. Всего единиц N // 4 + N % 2, и это равно 43. 4. При чётном N единиц ровно N // 4, значит N ≥ 172; при нечётном N // 4 = 42, значит подходят N = 169 и N = 171. Наименьшее — 169.

На примере: 169 единиц после первого цикла дают 84 двойки и одну единицу, после второго — 42 единицы плюс эта же единица, всего 43.

Решение на Python

def run(s):
    # первая часть программы: каждая пара 11 заменяется на 2
    while '11' in s:
        i = s.find('11')
        s = s[:i] + '2' + s[i + 2:]
    # вторая часть: каждая пара 22 заменяется на 1
    while '22' in s:
        i = s.find('22')
        s = s[:i] + '1' + s[i + 2:]
    return s


n = 1
while run('1' * n).count('1') != 43:  # ищем наименьшую подходящую длину
    n += 1

print(n)

Ответ: 169

Шаблоны кода на Python

Исполнитель Редактор

Пока (нашлось) и Если (нашлось) — это while и if с in, заменить(v, w) — replace с третьим аргументом 1: Редактор заменяет только первое вхождение.

Python

s = '1' + '8' * 80

while '18' in s or '288' in s or '3888' in s:
    if '18' in s:
        s = s.replace('18', '2', 1)
    elif '288' in s:
        s = s.replace('288', '3', 1)
    else:
        s = s.replace('3888', '1', 1)

print(s)
print(sum(int(c) for c in s))   # если спрашивают сумму цифр

Вывод

28
10

Машина Тьюринга

Таблицу переходов переписываете словарём: (состояние, символ) → (что записать, куда сдвинуться, новое состояние). Лента — словарь, пустая клетка — λ.

Python

n = 13
tape = dict(enumerate(bin(n)[2:]))   # двоичная запись на ленте
head = 0                             # головка над первой цифрой
state = 'q0'

rules = {
    ('q0', '0'): ('1', 'R', 'q0'),   # инвертировать цифры
    ('q0', '1'): ('0', 'R', 'q0'),
    ('q0', 'λ'): ('λ', 'S', 'q1'),   # стоп на пустой клетке
}

steps = 0
while True:
    write, move, state = rules[(state, tape.get(head, 'λ'))]
    tape[head] = write
    steps += 1
    if move == 'S':
        break
    head += 1 if move == 'R' else -1

cells = sorted(i for i in tape if tape[i] != 'λ')
print(''.join(tape[i] for i in range(cells[0], cells[-1] + 1)), steps)

Вывод

0010 5

Шаблоны кода ко всем заданиям

Как выполнять задание

Определите исполнителя: таблица состояний q₀, q₁, … — машина Тьюринга, циклы «ПОКА нашлось» и «заменить» — Редактор. От этого зависит, что вы трассируете: ленту или строку.
Для МТ перепишите таблицу в правила: паре «состояние — символ» сопоставьте тройку «записать, сдвиг, новое состояние». Пустая клетка значит, что такая пара за время работы не встретится.
Помните порядок: сначала символ записывается в текущую ячейку, только потом головка сдвигается; S останавливает машину после записи.
Для Редактора помните, что заменить (v, w) меняет только первое вхождение v, а тело цикла повторяется, пока команда нашлось истинна.
Прогоните программу на коротком примере, который считаете вручную. В ответ запишите одно число в десятичной системе: для МТ прочитайте ленту слева направо, отбросив пустые ячейки.

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

Лента и головка. Ячейки бесконечной ленты, пустой символ λ и состояния q₀, …, q_n−1; начальное состояние всегда q₀. За один такт выполняется одна команда.
Команда МТ. «0, L, q₃»: записать 0, сдвинуться влево, перейти в q₃; R — сдвиг вправо, S — остановка после записи.
Двоичная запись. Число читают как сумму степеней двойки, старший разряд слева. Приписанный слева разряд 1 увеличивает число на 2^k, где k — прежнее число разрядов; в Python перевод — int(строка, 2).
Редактор. заменить (v, w) меняет первое слева вхождение, нашлось (v) истинно, если v есть в строке. В Python это s.replace(v, w, 1) и v in s.

Как оценивается

Проверка автоматическая, по ключу: ответ должен быть записан в форме из условия и полностью совпасть с эталоном. Код и черновики не проверяют — значение имеет только ответ. За верный ответ — 1 балл, частичного балла нет.

Критерии всех заданий экзамена — на странице критериев ЕГЭ.

Разбор задания демоверсии 2027

В демоверсии 2027 года на ленте записано число 2025 = 11111101001₂, головка стоит в ближайшей справа пустой ячейке, состояние q₀. Программа такая: в q₀ по λ — «λ, L, q₁»; в q₁ команды «0, L, q₁» и «1, L, q₁» переписывают цифры без изменений, а по λ стоит «1, L, q₂»; в q₂ по λ — «λ, S, q₂».

Разберём руками. Первый такт переносит головку на правую цифру числа. Затем в состоянии q₁ машина идёт влево по всем 11 разрядам, не меняя их, и в пустой ячейке слева по команде «1, L, q₂» записывает 1 — новый старший разряд, после чего «λ, S, q₂» останавливает работу. На ленте получилась запись 111111101001₂ = 2¹¹ + 2025 = 4073 — это ключ ФИПИ.

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

Сдвиг раньше записи

В команде «0, L, q₃» сначала выполняется запись, и только потом головка сдвигается. Иначе символ уйдёт не в ту ячейку и всё содержимое ленты сместится.

Оси таблицы перепутаны

В программе МТ строки — состояния головки, столбцы — символы на ленте. Если читать таблицу транспонированной, правила окажутся привязаны не к тем парам «состояние — символ».

Работа продолжается после S

S означает остановку после выполнения текущей команды: ни сдвига, ни следующего такта уже не будет. Лишний шаг заметно меняет число на ленте.

replace без третьего аргумента

Команда заменить (v, w) меняет только первое вхождение: нужен s.replace('11', '2', 1). Запись без третьего аргумента заменит сразу все пары и даст другой результат.

Наибольшее вместо наименьшего

В задачах про наименьшую исходную строку подходящих значений несколько: 43 единицы после программы дают и 169 единиц, и 171, и 172. Ответ — меньшее.

Вопросы и ответы

Как решать задание 12 ЕГЭ по информатике?

Определите исполнителя и ведите трассировку. Для машины Тьюринга перепишите таблицу в правила «состояние, символ → запись, сдвиг, состояние» и выполняйте такты до S. Для Редактора считайте блоками: сколько пар заменяется за цикл и что остаётся в строке.

Что означает команда «0, L, q₃» в машине Тьюринга?

Записать в текущую ячейку 0, сдвинуться в соседнюю слева ячейку и перейти в состояние q₃. Сдвиг идёт после записи, R сдвигает вправо, S завершает работу после записи.

Чем Редактор отличается от машины Тьюринга в задании 12?

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

Нужно ли писать программу для задания 12?

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

Сколько баллов даёт задание 12 и сколько на него времени?

1 балл, частичного балла нет: ответ должен полностью совпасть с эталоном. По обобщённому плану на задание отводится около 6 минут, уровень — повышенный.

Другие задания раздела «Алгоритмы и программирование»

По демоверсии, спецификации и кодификатору ФИПИ 2027
Обновлено: 13 октября 2026 г.

Все задания ЕГЭ по информатике →

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

Тренажёр задания 12

Типы задания 12 с решением

Машина Тьюринга над двоичной записью числа

Исполнитель Редактор: сколько цифр останется после программы

Исполнитель Редактор: наименьшая исходная строка

Шаблоны кода на Python

Исполнитель Редактор

Машина Тьюринга

Как выполнять задание

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

Как оценивается

Разбор задания демоверсии 2027

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

Сдвиг раньше записи

Оси таблицы перепутаны

Работа продолжается после S

replace без третьего аргумента

Наибольшее вместо наименьшего

Вопросы и ответы

Как решать задание 12 ЕГЭ по информатике?

Что означает команда «0, L, q3» в машине Тьюринга?

Чем Редактор отличается от машины Тьюринга в задании 12?

Нужно ли писать программу для задания 12?

Сколько баллов даёт задание 12 и сколько на него времени?

Другие задания раздела «Алгоритмы и программирование»

Что означает команда «0, L, q₃» в машине Тьюринга?