Состояния и фазы

Что сделает таблица из четырёх состояний со словом 101?

Головка начинает в ближайшей пустой ячейке слева, в q0.

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

q1 повторяется много тактов подряд, но цикла нет: головка каждый раз в новой ячейке, и до края слова всё ближе. Каждая фаза конечна, машина остановится.

Какое наибольшее число не больше 500 может получиться у этой таблицы?

Когда фазы названы, результат записывают для любой длины: здесь из слова длины k всегда получается 10, затем k единиц, затем 0. Цифры входа в первой фазе всё равно становятся единицами, поэтому результат зависит только от длины.

rules = {    ('q0', 'λ'): ('λ', 'R', 'q1'),    ('q1', 'λ'): ('0', 'L', 'q2'),    ('q1', '0'): ('1', 'R', 'q1'),    ('q1', '1'): ('1', 'R', 'q1'),    ('q2', 'λ'): ('0', 'L', 'q3'),    ('q2', '1'): ('1', 'L', 'q2'),    ('q3', 'λ'): ('1', 'S', 'q3'),}for k in range(1, 8):    result, pos, steps = run_tm('1' * k, rules, -1)    print(k, result, int(result, 2), steps)

Таблица проходит число вправо, не меняя цифр, пишет 1 справа, возвращается и пишет 1 слева. Что станет с числом 13?

Если цифры слова сохраняются, а на краях дописываются разряды, результат выражают через N и длину k, как в подтеме 3. Единица справа даёт 2N + 1, единица слева от слова длины k + 1 добавляет 2ᵏ⁺¹. Итог 2ᵏ⁺¹ + 2N + 1: 13 = 1101, k = 4, 32 + 27 = 59.

Таблица ниже дописывает к слову одну цифру. Какую — для слова 1011? Головка начинает на первой цифре, в q0.

Состояние может хранить свойство уже просмотренной части: здесь q0 — «единиц пока чётное число», q1 — «нечётное». Ноль состояние не меняет, единица переключает. На пустой ячейке машина пишет 0 при чётном числе единиц и 1 при нечётном. В 1011 три единицы: 10111.

Смысл состояния проверяют по командам, а не по названию: каждый ноль должен сохранять смысл, каждая единица — менять его на противоположный. Перебором слов (product) и функцией run_tm это легко проверить на коротких строках.

• Фазачто делает состояние и чем заканчивается
• Не циклто же состояние, но новая ячейка
• Любая длина10, k единиц, 0: важна только k
• Тактысумма тактов всех фаз: 2k + 4
• Края2ᵏ⁺¹ + 2N + 1 для 1 слева и справа
• Памятьсостояние хранит чётность и подобное