Задание 12 ЕГЭ по информатике 2027

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

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

Ответчисло в поле ответа
Баллы1 балл
Проверяетумение выполнить алгоритм для исполнителя с фиксированным набором команд — машины Тьюринга, заданной таблицей
Сколько времени закладыватьоколо 6 минут по спецификации ФИПИ

Какие бывают подтипы

Пример с полным разбором

Условие. На ленте машины Тьюринга записана двоичная запись числа 47 без ведущих нулей, остальные ячейки пустые (пустой символ — λ). Головка стоит в пустой ячейке сразу справа от числа, в состоянии q0. Команда «0, L, q1» означает: записать в ячейку 0, сдвинуться на одну ячейку влево и перейти в состояние q1; буква S вместо сдвига означает остановку. Выполните программу из таблицы и запишите получившееся число в десятичной системе.

λ01
q0λ, L, q1
q11, S, q11, S, q10, L, q1
  1. . Головка в состоянии q0 видит пустую ячейку: команда «λ, L, q1» оставляет λ, сдвигает головку на последнюю цифру числа и переводит её в q1.
  2. В q1 на единице команда «0, L, q1»: единица становится нулём, головка идёт дальше влево. Так четыре последние единицы превращаются в нули.
  3. Пятая цифра справа — 0. Команда «1, S, q1» записывает 1 и останавливает машину.
  4. На ленте . Программа прибавляет к числу единицу: так же работает перенос разряда при сложении столбиком.

Ответ: 48

Ещё задания с решением

Выполнить программу машины Тьюринга

Условие.

На ленте машины Тьюринга (исполнителя МТ) записано число 834 в двоичной системе без ведущих нулей, по одной цифре в ячейке; во всех остальных ячейках стоит пустой символ λ. Головка в состоянии q0 стоит на первой пустой ячейке справа от записи числа.

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

Какое число окажется записано на ленте после остановки исполнителя? Ответ дайте в десятичной системе счисления.

Решение.

Двоичная запись числа 834 — 10 разрядов.

Последний разряд стёрт: вместо него в ячейке пустой символ.

Стереть младший двоичный разряд — то же самое, что разделить число на 2 нацело.

Ответ: 417

Выполнить программу машины Тьюринга

Условие.

На ленте машины Тьюринга (исполнителя МТ) записано число 845 в двоичной системе без ведущих нулей, по одной цифре в ячейке; во всех остальных ячейках стоит пустой символ λ. Головка в состоянии q0 стоит на первой пустой ячейке справа от записи числа.

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

Какое число окажется записано на ленте после остановки исполнителя? Ответ дайте в десятичной системе счисления.

Решение.

Двоичная запись числа 845 — 10 разрядов.

Последний разряд стёрт: вместо него в ячейке пустой символ.

Стереть младший двоичный разряд — то же самое, что разделить число на 2 нацело.

Ответ: 422

Выполнить программу машины Тьюринга

Условие.

На ленте машины Тьюринга (исполнителя МТ) записано число 393 в двоичной системе без ведущих нулей, по одной цифре в ячейке; во всех остальных ячейках стоит пустой символ λ. Головка в состоянии q0 стоит на первой пустой ячейке справа от записи числа.

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

Какое число окажется записано на ленте после остановки исполнителя? Ответ дайте в десятичной системе счисления.

Решение.

Двоичная запись числа 393 — 9 разрядов.

Последний разряд стёрт: вместо него в ячейке пустой символ.

Стереть младший двоичный разряд — то же самое, что разделить число на 2 нацело.

Ответ: 196

Частые ошибки

Что нужно знать для задания 12

Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.

  1. Две команды Редактора
  2. Программа ПОКА и её перенос на Python
  3. Разбор: строка из одинаковых цифр
  4. Когда прямая симуляция слишком долгая
  5. Машина Тьюринга: лента, головка, состояния
  6. Программа машины Тьюринга: таблица переходов
  7. Разбор: задание 12 в форме демоварианта

Открыть темы в курсе

Ответы на частые вопросы

Сколько баллов за задание 12?
Один, если число полностью совпало с верным.
Нужно ли знать машину Тьюринга заранее?
Правила работы исполнителя подробно описаны в самом условии, с примером. Но быстро читать таблицу-программу стоит научиться заранее: по спецификации на задание отводится около 6 минут.
Что такое такт?
Одна выполненная команда: запись символа, сдвиг и смена состояния. Иногда спрашивают, сколько тактов проработает программа до остановки.