Исполнение алгоритма для исполнителя

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

«На ленте исполнителя МТ в соседних ячейках записана последовательность из 12 символов, каждый из которых 0 или 1; остальные ячейки содержат пустой символ λ. В начальный момент головка находится в ближайшей справа от последовательности ячейке в состоянии q0. Программа работы исполнителя задана таблицей. После выполнения программы в последовательности оказалось ровно 5 нулей. Какое наибольшее количество нулей могло быть в исходной последовательности?»

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

Тема состоит из шести подтем — у каждой своя страница. Идём по ним по порядку:

1. Лента, команда и такт — ты сейчас здесь.
2. Однократный проход и количества — таблицы, которые меняют каждый символ один раз.
3. Двоичное число на ленте — что таблица задачи темы делает с числом.
4. Хвост и обратная задача — ответ задачи темы: 11.
5. Состояния и фазы — таблицы из нескольких состояний.
6. Сумма, простота и ограничения на количества — дополнительный урок для редких вопросов.

Таблицу можно выполнить и вручную, и программой — выбирай вкладку «Вручную» или «Python». Программа помогает проверить ответ на коротких строках, но экзаменационную ленту из сотен символов перебором не решить: сначала нужно понять, что делает таблица.

Что видит машина в начале работы?

Лента — ряд ячеек, в каждой ровно один символ; λ — пустой символ, а не цифра 0. Головка читает одну ячейку и находится в одном состоянии. Возьмём короткое слово 10100. Пронумеруем ячейки с цифрами от 0 до 4 — это наши метки для решения. Головка стоит в ближайшей пустой ячейке справа, на ячейке 5, в состоянии q0.

Состояние — режим работы, а не номер шага: q0 — состояние, в котором машина начинает, а дальше она может много тактов подряд оставаться в одном состоянии.

Что означает команда 0, L, q3?

Команда — тройка: что записать в текущую ячейку, куда сдвинуться и в какое состояние перейти. Запись всегда идёт до сдвига. 0, L, q3: записать 0 в ту ячейку, где головка стоит сейчас, сдвинуться на одну ячейку влево, перейти в q3.

Команду выбирают по паре «состояние, прочитанный символ»: строка таблицы — состояние, столбец — символ. Команда 1, S, q2 сначала запишет единицу и только потом остановит машину: остановочный такт тоже меняет ленту и тоже считается.

Прочерк в таблице — пара, которая при правильном запуске не встретится. Это не команда остановки: если ты в неё попал, проверь начальное положение и предыдущие такты.

Что таблица задачи темы сделает со словом 10100?

За один такт машина выполняет одну клетку таблицы — ту, что стоит на пересечении текущего состояния и символа под головкой.

rules = {    ('q0', 'λ'): ('λ', 'L', 'q1'),    ('q1', 'λ'): ('λ', 'S', 'q1'),    ('q1', '0'): ('1', 'L', 'q1'),    ('q1', '1'): ('0', 'S', 'q1'),}tape = {0: '1', 1: '0', 2: '1', 3: '0', 4: '0'}pos, state = 5, 'q0'while True:    write, move, state = rules[(state, tape.get(pos, 'λ'))]    tape[pos] = write    if move == 'S':        break    pos += -1 if move == 'L' else 1print(tape[0] + tape[1] + tape[2] + tape[3] + tape[4])

def run_tm(word, rules, pos, state='q0'):    tape = {}    for i in range(len(word)):        tape[i] = word[i]    steps = 0    while True:        symbol = tape.get(pos, 'λ')        write, move, state = rules[(state, symbol)]        tape[pos] = write        steps += 1        if move == 'S':            break        if move == 'L':            pos -= 1        if move == 'R':            pos += 1    result = ''    for i in range(min(tape), max(tape) + 1):        result += tape.get(i, 'λ')    return result.strip('λ'), pos, steps

rules = {    ('q0', 'λ'): ('λ', 'L', 'q1'),    ('q1', 'λ'): ('λ', 'S', 'q1'),    ('q1', '0'): ('1', 'L', 'q1'),    ('q1', '1'): ('0', 'S', 'q1'),}print(run_tm('10100', rules, 5))

Головка шла справа налево, но результат читают как обычно — слева направо. Строка не переворачивается.

• Лентав ячейке один символ, λ — не 0
• Состояниережим работы; q0 — начало, не остановка
• Командазаписать → сдвинуться → состояние
• Sзаписать и остановиться; такт считается
• Прочеркпри правильном запуске не встретится
• Pythonrun_tm(word, rules, pos)