Главная / Задания ЕГЭ / Задание 12

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

Исполнитель МТ (машина Тьюринга). Дана программа для машины Тьюринга и строка на ленте. Нужно определить результат работы или найти, какой была исходная строка.

Решать задание 12 в тренажёре Пробный урок с преподавателем

Как решать

Проследите несколько шагов вручную: в каком состоянии головка и что она пишет.
Найдите закономерность: какой блок символов и как меняется целиком.
Составьте уравнение по количествам символов или смоделируйте программу на Python.

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

Не учитывают, что машина останавливается в определённом состоянии, а не в конце строки.

Пример задания

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

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

	λ	1	0
q₀	λ, L, q1
q₁		0, S, q1	1, L, q1

R — сдвиг вправо, L — влево, N — без сдвига, S — остановка программы.

После выполнения программы на ленте осталось ровно 1178 нулей. Известно, что от запуска до остановки машина выполнила 68 шагов. Сколько нулей было в исходной последовательности?

Показать ответ

Ответ: 1243

В тренажёре каждый раз новое задание этого типа: ответ проверяется сразу, после ответа виден короткий разбор.

Все задания ЕГЭ

Нужна помощь с ЕГЭ?

На пробном уроке посмотрим ваш уровень по 2–3 темам ЕГЭ по информатике и составим план подготовки.

Записаться на пробный урок