ЕГЭ · ЗАДАНИЕ 12
Машина Тьюринга · №27624
На ленте двоичная запись числа 800 без ведущих нулей; с обеих сторон пустые символы λ. Головка в состоянии q0 находится в ближайшей пустой ячейке справа. Выполните программу из таблицы и запишите итоговое число в десятичной системе.
| Состояние / символ | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ, L, q1 | — | — |
| q1 | λ, R, q2 | 0, L, q1 | 1, L, q1 |
| q2 | — | 0, R, q2 | 1, R, q3 |
| q3 | λ, R, q4 | 0, R, q3 | 0, R, q4 |
| q4 | λ, S, q4 | 0, R, q4 | 1, R, q4 |
Команда: записать символ → L (влево), R (вправо), N (без сдвига) или S (остановиться после записи) → новое состояние. Прочерк — отсутствие команды, не остановка.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 544
После поиска левого края первая единица пропускается. Следующая единица заменяется нулём. В записи 1100100000₂ это разряд 2⁸: 800−256=544. Конечная запись: 1000100000₂.
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 = [{'λ': ('λ', 'L', 1)}, {'λ': ('λ', 'R', 2), '0': ('0', 'L', 1), '1': ('1', 'L', 1)}, {'0': ('0', 'R', 2), '1': ('1', 'R', 3)}, {'λ': ('λ', 'R', 4), '0': ('0', 'R', 3), '1': ('0', 'R', 4)}, {'λ': ('λ', 'S', 4), '0': ('0', 'R', 4), '1': ('1', 'R', 4)}]
result = run(bin(800)[2:], table, "right")
print(int(result, 2))