Задание 12 ЕГЭ по информатике. Машина Тьюринга

Короткие выдержки из урока

• Программа исполнителя — это таблица правил. В каждой клетке задана команда «заменить → сдвинуть L/R/S → перейти в состояние/стоп». Команду выбирают по состоянию и символу, находящемуся под головкой.
• В разборе на сайте показано, как по символу в ячейке подобрать нужную команду и применить её пошагово (λL, 1L и т. п.).
• Типовой план: выписать известные длины/количества символов → понять, когда МТ работает/останавливается → при необходимости промоделировать на короткой ленте → ответить на вопрос.

Универсальный Python-симулятор Машины Тьюринга

Имеет смысл применять только в заданиях повышенной сложности!

Симулятор читает таблицу правил в виде словаря {(state, read): (write, move, next_state)}. Лента — словарь индексов в символы, пустой символ — 'λ' (как в уроке). Движение: 'L', 'R', 'S' (стоять).

from collections import defaultdict

class TuringMachine:
    def __init__(self, rules, tape_str="", blank='λ', start_state='q0', accept_states=('HALT',)):
        self.rules = rules
        self.blank = blank
        self.state = start_state
        self.accept = set(accept_states)
        self.tape = defaultdict(lambda: blank)
        for i, ch in enumerate(tape_str):
            self.tape[i] = ch
        self.head = 0

    def step(self):
        sym = self.tape[self.head]
        key = (self.state, sym)
        if key not in self.rules:
            # нет правила → останов (неявный)
            self.state = 'HALT'
            return False
        write, move, next_state = self.rules[key]
        self.tape[self.head] = write
        if move == 'L': self.head -= 1
        elif move == 'R': self.head += 1
        # 'S' — стоим
        self.state = next_state
        return self.state not in self.accept

    def run(self, max_steps=10_000):
        steps = 0
        while steps < max_steps and self.state not in self.accept:
            cont = self.step()
            steps += 1
            if not cont: break
        return steps

    def read_str(self, left=0, right=40):
        return ''.join(self.tape[i] for i in range(left, right+1))

# Пример: пустая программа — сразу стоп
tm = TuringMachine(rules={}, tape_str="1011")
tm.run()
print(tm.state)  # HALT

Обзор модели

• Лента: двусторонне бесконечная, представлена разреженной структурой (словарь index → символ).
  Пустой символ задаётся параметром blank (по умолчанию 'λ').
• Состояние: строковый идентификатор ('q0', 'q1', …, 'HALT' и т.п.).
• Алфавит: любые символьные строки (например, '0', '1', 'X', '#', 'a' и т.д.).
• Правила (программа): детерминированная таблица переходов
  rules[(state, read_symbol)] = (write_symbol, move, next_state),
  где move ∈ {'L','R','S'} (Left/Right/Stay).
• Головка: целочисленный индекс текущей ячейки.
• Остановка: попадание в одно из accept_states или отсутствие подходящего правила.

Атрибуты экземпляра

• rules: dict[tuple[str, str], Transition]
  Таблица переходов. Ключ — пара (state, read_symbol), значение — тройка действий.
• blank: str
  Символ пустой ячейки ленты. По умолчанию 'λ'.
• state: str
  Текущее состояние МТ.
• accept: set[str]
  Множество «останавливающих»/допускающих состояний (обычно содержит 'HALT').
• tape: collections.defaultdict[int, str]
  Разреженная лента: неинициализированные ячейки отдают blank.
• head: int
  Позиция головки.
• step_counter: int
  Счётчик выполненных тактов (обновляется в run/step).

Основные методы

• __init__(rules, tape_str="", blank='λ', start_state='q0', accept_states=('HALT',), head=0)
  Инициализация ленты из строки (посимвольно), установка правил/состояния/головки/пустого символа.
• step() -> bool
  Выполняет один такт:
• читает символ под головкой;
• находит правило (write, move, next_state);
• записывает символ; смещает головку L/R/S;
• меняет состояние.
  Возвращает True, если симуляция может продолжаться (не остановились), иначе False.
• run(max_steps: int = 10_000, trace: bool = False, hook: Callable | None = None) -> int
  Запускает МТ до остановки или до достижения лимита тактов.
  Если trace=True или задан hook(snapshot), можно логировать каждый шаг.
• read_str(left: int, right: int, *, fill: str = None) -> str
  Возвращает срез ленты как строку в диапазоне [left, right].
  (Удобно для визуальной проверки результата.)
• reset(tape_str: str = "", state: str | None = None, head: int = 0)
  Полный сброс ленты/состояния/головки для повторных запусков.
• snapshot(window: tuple[int, int] | None = None) -> dict
  Снимок текущего шага: состояние, позиция головки, шаг, и (опционально) окно ленты.
• strict: bool (необязательный флаг, см. ниже)
  Если включён, отсутствие правила вызывает исключение (а не неявный стоп).

Почему такие структуры?

• Словарь ленты (defaultdict): экономит память и время на «пустых» участках, что особенно важно в учебных задачах с длинными ходами и небольшим числом реально тронутых ячеек.
• Правила как dict: O(1) доступ к переходу по паре (state, symbol); удобно строить из таблиц или CSV.
• Строковые состояния и символы: позволяют свободно расширять алфавит ({'0','1','X','λ'}) и вводить семантические состояния ('qScan', 'qBack' и т.п.), что повышает читабельность.

МТ над двоичными числами: +1, −1, ×2, ÷2

Как представляем число

Будем хранить двоичное число как непрерывный блок из 0/1 на ленте, без разделителей, головка стартует на крайнем левом бите (состояние q0). Пустой — λ.

×2 (умножение на 2): приписать 0 справа

rules_mul2 = {
    # q0: идём вправо до первого λ справа от числа
    ('q0','0'): ('0','R','q0'),
    ('q0','1'): ('1','R','q0'),
    ('q0','λ'): ('0','S','HALT'),  # на пустой — дописали 0 и стоп
}

tm = TuringMachine(rules_mul2, tape_str="1011")  # 11₍₁₀₎
tm.run()
print(tm.read_str(0, 5))  # 10110  (22₍₁₀₎)

÷2 (целочисленное деление на 2): убрать последний бит

rules_div2 = {
    # пройти до конца, запомнив, что нашли конец
    ('q0','0'): ('0','R','q0'),
    ('q0','1'): ('1','R','q0'),
    ('q0','λ'): ('λ','L','qE'),   # шаг назад — на последний бит
    # стереть последний бит (любой: 0 или 1) и остановиться
    ('qE','0'): ('λ','S','HALT'),
    ('qE','1'): ('λ','S','HALT'),
}

tm = TuringMachine(rules_div2, tape_str="10110")  # 22 -> 11
tm.run()
print(tm.read_str(0, 5))  # 1011

+1 (инкремент): классический перенос

Идём в конец; если видим 0 — превращаем в 1 и стоп. Если 1 — превращаем в 0 и несём перенос влево; если дошли до левой границы (λ) — пишем 1 слева и стоп.

rules_inc = {
    ('q0','0'): ('0','R','q0'),
    ('q0','1'): ('1','R','q0'),
    ('q0','λ'): ('λ','L','qC'),          # дошли до конца, начинаем перенос

    # перенос: если '0' → пишем '1' и стоп; если '1' → пишем '0' и несём перенос дальше
    ('qC','0'): ('1','S','HALT'),
    ('qC','1'): ('0','L','qC'),
    ('qC','λ'): ('1','S','HALT'),        # переполнение: приписали '1' слева
}

tm = TuringMachine(rules_inc, tape_str="111")  # 7 + 1 = 8
tm.run()
print(tm.read_str(-1, 4))  # 1000

−1 (декремент, для N>0): обратный перенос

Идём в конец; если видим 1 — превращаем в 0 и стоп. Если 0 — превращаем в 1 и несём «заём» влево; крайний левый ноль в итоге исчезать не должен — соблюдаем корректность для N>0.

rules_dec = {
    ('q0','0'): ('0','R','q0'),
    ('q0','1'): ('1','R','q0'),
    ('q0','λ'): ('λ','L','qB'),

    ('qB','1'): ('0','S','HALT'),    #  ...1 → ...0 (завершили)
    ('qB','0'): ('1','L','qB'),     #  ...0 → ...1, продолжаем заём
    # Если число было вида 1000... → упрёмся в λ слева: просто стоп (ведущий 1 "съедать" не нужно в этой модели)
    ('qB','λ'): ('λ','S','HALT'),
}

tm = TuringMachine(rules_dec, tape_str="1000")  # 8 - 1 = 7
tm.run()
print(tm.read_str(0, 4))  # 0111 (ведущий 0 можно трактовать как отсутствующий бит)

Примечание: в учебных задачах часто допускается «ведущий 0» после декремента; при желании можно дописать пост-проход слева направо, стирающий крайний ведущий ноль.

Не только {0,1}: расширяем алфавит

В задачах МТ может понадобиться алфавит вида {0,1,X,λ} (метки/«крестики»), или, например, {a,b,c,λ}. Симулятор выше поддерживает любые символы: просто используйте их в rules и на ленте. Это удобно для стратегий «пометил → вернулся → продолжил» и для копирования/частичного копирования.

Копирование, частичное копирование и удаление

Дублирование унарного блока 1…1 (копирование)

Постановка: на ленте 111λλ…, хотим получить 1110111 (скопировать блок через разделитель 0). Идея: бежим по исходному блоку, временно помечая прочитанные 1 как X, каждый раз, когда видим X — идём вправо к разделителю 0, через него — в конец и дописываем 1, возвращаемся к следующему непомеченному 1.

rules_copy = {
    # q0: ищем не помеченную '1'
    ('q0','1'): ('X','R','qGoRight'),
    ('q0','X'): ('X','R','q0'),
    ('q0','0'): ('0','R','qEnd'),          # все исходные 1 помечены
    # идём вправо к разделителю 0
    ('qGoRight','1'): ('1','R','qGoRight'),
    ('qGoRight','X'): ('X','R','qGoRight'),
    ('qGoRight','0'): ('0','R','qToTail'),
    # добегаем до хвоста второго блока и дописываем '1'
    ('qToTail','1'): ('1','R','qToTail'),
    ('qToTail','λ'): ('1','L','qBack'),
    # возвращаемся в начало, ищем следующую '1'
    ('qBack','1'): ('1','L','qBack'),
    ('qBack','0'): ('0','L','qBack'),
    ('qBack','X'): ('X','L','qBack'),
    ('qBack','λ'): ('λ','R','q0'),
    # завершение: заменить X обратно на 1 и остановиться
    ('qEnd','X'): ('1','R','qEnd'),
    ('qEnd','1'): ('1','R','qEnd'),
    ('qEnd','λ'): ('λ','S','HALT'),
}

tm = TuringMachine(rules_copy, tape_str="1110")
tm.run(50_000)
print(tm.read_str(0, 12))  # 1110111...

Частичное копирование

Вместо копирования всех символов можно вставить фильтр: копировать только каждый второй X (нумеруя их счётчиком в состоянии), или только первые k штук (состояния q1, q2, ... выступают счётчиком).

Удаление подстроки

Шаблон: найдите первый символ подстроки, отметьте состояние «ищем подряд», при несовпадении откатитесь и снимите отметки, при полном совпадении — пройдите и замените найденные символы на λ, затем «схлопните» хвост (или оставьте «дырки» — по условию).