Повышенный (1 балл) Время: 4-7 мин Python Словарь table while True if / elif Все задачи №12 в каталоге

Задание №12. Машина Тьюринга: пишем свой симулятор

Тема: Исполнитель МТ: таблица состояний, лента, головка, перебор входных чисел

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

Что от тебя хотят

У машины Тьюринга есть лента из ячеек, на ленте записаны символы (нули, единицы и пустое место λ), и есть головка, которая стоит над одной ячейкой. Ещё есть состояние (q1, q2, ...) и таблица программы. На каждом шаге машина смотрит на символ под головкой и на своё состояние и по таблице выполняет три действия.

Записывает новый символ в ячейку под головкой.
Сдвигает головку: L влево, R вправо, N остаётся, S останавливается.
Меняет состояние.

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

Строки таблицы это состояния, столбцы это символы на ленте. В клетке записано три вещи: что писать, куда двигаться, в какое состояние перейти. Вот программа из досрочного ЕГЭ-2026, которая прибавляет единицу к двоичному числу (голова стоит справа от числа, на пустой ячейке):

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

В словаре Python каждая клетка превращается в одну запись: ключ это пара (состояние, символ), значение это тройка (что писать, куда двигаться, новое состояние).

Идея: один цикл вместо рисования ленты

Лента это список ячеек, головка это номер ячейки. Цикл повторяет три действия, пока не встретит S. Чтобы голова не вышла за край списка, ленту с обеих сторон «подкладываем» пустыми ячейками.

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

Разбор 1: пошагово на числе 2047

На ленте записано двоичное представление числа 2047, головка стоит справа от него. Программа из таблицы выше. Какое число окажется на ленте после выполнения программы?

2047 это одиннадцать единиц подряд. Первое окно печатает ленту после каждого шага: головка идёт налево по единицам, превращая их в нули, доходит до пустой ячейки, пишет туда единицу и останавливается. Получается единица и одиннадцать нулей, то есть 2048: программа действительно прибавляет 1.

Разбор 2: подбор по условию

Другая программа: в q0 головка шагает влево с пустой ячейки, а в q1 каждый 0 меняет на 1, каждую 1 на 0 и идёт дальше влево, пока не дойдёт до λ. То есть она инвертирует все цифры.

После выполнения программы на ленте оказалась двоичная запись числа 156. Определите наибольшее число, меньшее 10000, которое могло быть записано на ленте до начала работы.

Запускаем программу для каждого числа от 1 до 9999, склеиваем ленту (выбрасываем λ) и переводим результат в десятичную систему. Если получилось 156, запоминаем число. Последнее запомненное и есть наибольшее: 8035. Проверка: 8035 это 1111101100011, после инверсии 0000010011100, ведущие нули не считаются, остаётся 156.

Условие вроде «найти наибольшее число меньше 10000» решается тем же перебором: запусти все числа, сохраняй подходящее и в конце выведи последнее.

Разновидности и прототипы задания на экзамене

Тип 1: Что окажется на ленте

Дано число и программа. Запускаем симулятор и читаем результат.

Тип 2: Какое число было сначала

Известен результат или условие на него. Перебираем исходные числа и проверяем.

Тип 3: Сколько чисел подходит

Считаем, для скольких начальных чисел результат удовлетворяет условию. Тот же перебор, только вместо запоминания числа увеличиваем счётчик.

Код решения на Python

Запустить код в онлайн-песочнице

table = { (state, symbol): (...) }list(bin(n)[2:])while Trueif / elif / break"".join(tape).replace("λ", "")

Симулятор: пошаговый запуск на числе 2047

table = {
    ("q0", "λ"): ("λ", "L", "q1"),
    ("q1", "λ"): ("1", "L", "q2"),
    ("q1", "0"): ("1", "S", "q1"),
    ("q1", "1"): ("0", "L", "q1"),
    ("q2", "λ"): ("λ", "S", "q2"),
}

n = 2047
tape = ["λ"] * 20 + list(bin(n)[2:]) + ["λ"] * 20
head = 20 + len(bin(n)[2:])
state = "q0"

while True:
    symbol = tape[head]
    new_symbol, move, new_state = table[(state, symbol)]
    tape[head] = new_symbol
    state = new_state
    print(state, "".join(tape))
    if move == "L":
        head -= 1
    elif move == "R":
        head += 1
    elif move == "S":
        break

result = "".join(tape).replace("λ", "")
print(result, int(result, 2))

Задача из базы, которую решает этот код Открыть в песочнице

Перебор: какое число было на ленте

table = {
    ("q0", "λ"): ("λ", "L", "q1"),
    ("q1", "0"): ("1", "L", "q1"),
    ("q1", "1"): ("0", "L", "q1"),
    ("q1", "λ"): ("λ", "S", "q1"),
}

answer = 0
for n in range(1, 10000):
    tape = ["λ"] * 20 + list(bin(n)[2:]) + ["λ"] * 20
    head = 20 + len(bin(n)[2:])
    state = "q0"
    while True:
        new_symbol, move, state = table[(state, tape[head])]
        tape[head] = new_symbol
        if move == "L":
            head -= 1
        elif move == "R":
            head += 1
        elif move == "S":
            break
    result = "".join(tape).replace("λ", "")
    if int(result, 2) == 156:
        answer = n

print(answer)

Задача из базы, которую решает этот код Открыть в песочнице

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

✕ Не так

Сдвинуть головку до записи

Символ запишется уже не в ту ячейку.

✓ Так

Сначала tape[head] = new_symbol, потом сдвиг.

✕ Не так

Забыть сменить состояние

Машина останется в старом состоянии и пойдёт по другой строке таблицы.

✓ Так

После записи всегда state = new_state.

✕ Не так

Писать if вместо elif в выборе движения

После head -= 1 следующий if может сработать ещё раз.

✓ Так

Цепочка if / elif / elif: срабатывает ровно одна ветка.

✕ Не так

Не подложить пустые ячейки по краям

Головка уходит за левый край ленты, и Python падает или читает не с того конца.

✓ Так

["λ"] * 20 с обеих сторон: хватит любого числа шагов.

ГРОБ

ГРОБ №12: Длинная лента и большие числа

Числа в условии доходят до миллионов, и перебор в десять тысяч кажется слишком долгим.

Как обойти

Симулятор работает за доли миллисекунды на число. Перебор до миллиона укладывается в несколько секунд, так что просто запусти его. Для этого лишнюю печать из цикла убери.

Лайфхаки на экзамене

Головка стоит справа от числа, если в условии сказано «в ближайшей справа ячейке»: её номер это начало + длина числа.
Клетки таблицы без записи («—») в программе не встречаются. Если симулятор падает на KeyError, ты что-то переписал неверно.
Каждую клетку таблицы переписывай один раз и по порядку: строку за строкой. Перепутанная клетка самая частая ошибка.

Банк реальных задач №12 Открыть в тренажере СмартКИМ