ЕГЭ · ЗАДАНИЕ 12
Машина Тьюринга · №23815
На ленте слева направо: 764 двойки, 122 тройки и 114 символов X. Головка q0 — в ближайшей пустой ячейке слева, за записью в обе стороны λ. После выполнения таблицы символ X заменяют одной десятичной цифрой так, чтобы сумма цифр равнялась 3496. Найдите эту цифру.
| Состояние / символ | λ | 2 | 3 | X |
|---|---|---|---|---|
| q0 | λ, R, q1 | — | — | — |
| q1 | λ, S, q1 | 3, R, q1 | X, R, q1 | 2, R, q1 |
Команда: записать символ → L (влево), R (вправо), N (без сдвига) или S (остановиться после записи) → новое состояние. Прочерк — отсутствие команды, не остановка.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 8
Таблица циклически заменяет 2→3, 3→X, X→2 за один проход. Сумма равна 764·3+122·X+114·2. Поэтому 122·X=976 и X=8.
def run(word, table, side="right"):
tape = dict(enumerate(word))
pos = len(word) if side == "right" else -1
state = 0
for step in range(100000):
symbol = tape.get(pos, "λ")
if symbol not in table[state]:
raise ValueError("Нет команды для текущей пары")
write, move, new_state = table[state][symbol]
tape[pos] = write
state = new_state
if move == "S":
cells = [i for i, x in tape.items() if x != "λ"]
if not cells:
return ""
return "".join(tape.get(i, "λ") for i in range(min(cells), max(cells)+1))
pos += {"L": -1, "R": 1, "N": 0}[move]
raise RuntimeError("Достигнут предел шагов, это не доказательство остановки")
table = [{'λ': ('λ', 'R', 1)}, {'λ': ('λ', 'S', 1), '2': ('3', 'R', 1), '3': ('X', 'R', 1), 'X': ('2', 'R', 1)}]
s = run("2"*764+"3"*122+"X"*114, table, "left")
for x in range(10):
if sum(x if c == "X" else int(c) for c in s) == 3496:
print(x)