Статья Автор: Деникина Н.В., Деникин А.В.

Машина Тьюринга — проверка программой

Питон здесь — не решение, а проверка

Соблазн понятный: написать симулятор и прогонять им всё подряд.

Не сработает. В счётных задачах входов 2¹⁰⁰⁰, а на экзамене за номер дают шесть минут.

Зато симулятор идеален для другого: проверить гипотезу. Ты рассуждением нашёл ответ — а машина подтвердила.

Что нужно хранить

Всего три вещи, ровно как у самой МТ:

лента — словарь «позиция → символ», потому что индексы бывают отрицательными;
позиция головки — обычное число;
состояние — строка.

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

Пустой символ в коде пишем как '_': греческая лямбда в исходнике только мешает.

Функция run принимает ленту-строку, стартовую позицию головки и словарь правил, а возвращает две вещи: строку ленты после остановки и число шагов.

Порядок внутри шага — тот же, что в таблице

Сначала записать символ. Потом проверить S. Потом сдвинуть.

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

▶ Запусти и попробуй: смени в словаре dec команду ('q1','1'): ('0','S','q1') на ('0','L','q1') — увидишь, как вычитание превращается в инверсию.

# Симулятор МТ. Лента — словарь, пустой символ обозначаем '_'
def run(tape, head, rules):
    cells = {}
    for i in range(len(tape)):
        cells[i] = tape[i]
    state = 'q0'
    steps = 0
    while True:
        sym = cells.get(head, '_')
        if (state, sym) not in rules:
            break
        write, move, nstate = rules[(state, sym)]
        cells[head] = write          # сначала пишем
        steps = steps + 1
        if move == 'S':              # потом, если надо, встаём
            break
        if move == 'L':
            head = head - 1
        if move == 'R':
            head = head + 1
        state = nstate
    keys = []
    for i in cells:
        if cells[i] != '_':
            keys.append(i)
    out = ''
    for i in range(min(keys), max(keys) + 1):
        out = out + cells.get(i, '_')
    return out, steps

# программа вычитания единицы
dec = {('q0', '_'): ('_', 'L', 'q1'),
       ('q1', '_'): ('_', 'S', 'q1'),
       ('q1', '0'): ('1', 'L', 'q1'),
       ('q1', '1'): ('0', 'S', 'q1')}

seq = '1011000'
tape, steps = run(seq, len(seq), dec)
print(tape)
print(int(tape, 2))
print(steps)

Чем этот код намеренно проще

Здесь нет ни enumerate, ни генераторов, ни collections. Только словарь, цикл и условия.

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

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

Запусти код из блока выше. Что напечатает вторая строка вывода?

Проверить ответ

В симуляторе строку cells[head] = write переставили после сдвига головки. Что произойдёт?

Проверить ответ

Отметь всё, для чего симулятор действительно полезен на экзамене.

Проверить ответ

Куда смотреть дальше

Демонстрационный вариант ЕГЭ по информатике на сайте ФИПИ — там номер 12 дан в актуальной формулировке с машиной Тьюринга.
Открытый банк заданий ФИПИ — раздел с заданиями по исполнителям.
Задачи этого номера в банке SilverTests — тег «ЕГЭ-12. Выполнение алгоритмов для исполнителя (МТ)».

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать