Задание 12 ЕГЭ: исполнитель МТ

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

О чём задание: На ленте — двоичная запись числа или ряд нулей и единиц. Программа дана таблицей: строка — состояние головки, столбец — символ под ней, в клетке — команда «что записать, куда сдвинуться, в какое состояние перейти». Нужно понять, что программа делает с лентой.
Что нужно сделать: Десять задач — по одной на каждую форму, все на экране сразу, решай в любом порядке: дописать справа, дописать слева, прибавить или вычесть 1, инверсия, стереть справа, правка в начале числа, автомат «число в число», сколько нулей или единиц, обратная задача и «сколько могло быть».
Чем решать: Головой и черновиком. Подпиши каждое состояние одной фразой («идёт влево по цифрам», «прибавляет 1», «пишет 1 и стоп»), прогони программу на коротком числе — и станет видно правило. Его и примени к своему числу. Программа на Python, которая выполняет таблицу, — второй способ, он в подсказке внизу.
Отметка: Ошибся — разбор появится сразу, а кнопка «Новые числа» даст задачу того же типа: исправленная задача не засчитывается, засчитается новая. Доделать можно всё, хоть до пятёрки.
Ответ: Одно целое число в десятичной записи: 4073, а не 111111101001. Сверка знак в знак, как на КЕГЭ.

Задачи

наработано на—

Подсказка: как решать задание 12

Как читать таблицу

Работа начинается в q₀. Смотрим, что под головкой, и берём клетку на пересечении строки состояния и столбца символа. Команда : записать 1, шаг влево, перейти в q2. — записать и остановиться. Порядок столбцов в шапке бывает разный (λ, 0, 1 или λ, 1, 0) — сверяйся с шапкой, а не с памятью.

Приём: подпиши каждое состояние

В строке состояния	Что оно делает
и	идёт влево по цифрам, ничего не меняя, — до края числа
и , остаётся в себе	инверсия: меняет каждую цифру на противоположную
(в себя), (дальше)	прибавляет 1: единицы справа становятся нулями, первый 0 — единицей
(в себя), (дальше)	вычитает 1: нули справа становятся единицами, первая 1 — нулём
на пустой клетке	дописывает 1 рядом с числом
	стирает цифру

Дальше прогони программу на коротком числе (пять-шесть цифр) на черновике — правило станет видно — и примени его к своему числу.

Что получается с числом

Программа	Число x (n двоичных цифр) превращается в
дописала справа	x · 4 + 3 (k цифр s справа: x · 2^k + s)
дописала слева	x + 2ⁿ (слева : x + 2ⁿ⁺¹)
прибавила 1 и дописала 1	(x + 1) · 2 + 1
инверсия всех цифр	2ⁿ − 1 − x
стёрла последнюю цифру	x // 2

Автомат на ряду одинаковых цифр

Если головка идёт по ряду из 57 единиц и переходит q1 → q2 → q3 → q2 → q3 …, состояния ходят по кругу. Выпиши первые клетки, найди блок, который повторяется, и посчитай: сколько полных блоков, что в остатке.

Обратная задача

Пойми правило и сними действия в обратном порядке: убрать дописанные цифры, отменить инверсию или «+1». Инверсия теряет длину: у результата впереди могли быть нули, поэтому исходных чисел много — бери наименьшее или наибольшее, как спрашивают.

Второй способ — программой

Одна строка — одна клетка таблицы. Для обратной задачи то же самое оборачивают в и перебирают в цикле. Пользоваться не обязательно: таблица на экзамене маленькая, и разбор руками быстрее.

Пять ловушек

Шапка таблицы. Столбцы 0 и 1 стоят в разном порядке;
Где головка. Слева или справа от числа — от этого зависит, с какого края она начнёт;
Пустая клетка — тоже символ. Команда в столбце λ срабатывает за краем числа: там дописывают;
Ответ в десятичной. Двоичную запись с ленты переведи;
Ведущие нули. После инверсии число может начинаться с нуля — на значение это не влияет.

Откуда эти задачи

Задачи авторские, составлены в форме задания 12 ЕГЭ по информатике. Форма задания и способ решения — как на экзамене, а условия написаны своими словами. Числа каждый раз новые.

Материалы подготовлены с использованием технологий искусственного интеллекта.