Машина Тьюринга: лента, головка и таблица

Если ты проведёшь машину Тьюринга по короткой ленте, выписывая конфигурации, составишь таблицу для простого языка и назовёшь три исхода работы машины, - листай до «Теперь сам».

Как думаешь, чего не хватало стеку

Автомат со стеком не справился с aⁿbⁿcⁿ: сверяя b с a, он вынужден снимать то, что положил, и к буквам c приходит с пустыми руками.

Ответь себе до чтения: какую одну возможность нужно добавить, чтобы проверка получилась? Возможность вернуться к уже прочитанному и записанному, не уничтожая его. Не новый вид памяти и не второй стек с особыми правилами, а просто движение головки в обе стороны по тому, что написано. Оказывается, после этого добавлять больше нечего: всё, что вообще умеют вычислять программы, эта машина уже умеет.

На что это похоже

Человек с тетрадью в клетку, карандашом, ластиком и листком с инструкцией. Он смотрит на одну клетку, помнит, на каком пункте инструкции находится, и делает одно из простых действий: стереть и написать символ, перейти к соседней клетке, перейти к другому пункту. Тетрадь не кончается: понадобится ещё страница - она есть.

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

Механизм: шаг, конфигурация, три исхода

Машина Тьюринга состоит из конечного набора состояний, ленты и таблицы переходов.

Лента - ряд клеток, бесконечный вправо. В каждой клетке один символ. Сначала на ленте записан вход, дальше идут пустые клетки; пустую клетку обозначим _. Головка стоит на одной клетке, в начале - на самой левой.

Таблица переходов сопоставляет паре «состояние, символ под головкой» тройку:

( состояние, символ под головкой )
    →  ( что записать,  куда сдвинуться: L или R,  новое состояние )

L - влево, R - вправо.

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

Работа начинается в начальном состоянии; в программах ниже оно называется 0. Есть ещё два особых состояния - принимающее и отвергающее; попав в любое из них, машина останавливается. В программах ниже принимающее состояние называется да, а отвергающее задано неявно: если для пары «состояние, символ» в таблице нет строки, машина отвергает вход.

Конфигурация - полное описание момента: состояние, содержимое ленты и положение головки. Следующая конфигурация однозначно определяется текущей. В любой момент на ленте занято конечное число клеток: бесконечна не память, а её запас.

Три исхода. Машина, запущенная на входе, либо останавливается в принимающем состоянии, либо останавливается в отвергающем, либо не останавливается. У конечного автомата третьего исхода не было: он читал вход слева направо и заканчивал вместе с ним. Машина Тьюринга может ходить по ленте сколько угодно, и ничто не обязывает её закончить.

Язык машины - множество входов, которые она принимает. На остальных входах она может отвергать, а может работать вечно, и со стороны эти два случая различить непросто: пока машина работает, неизвестно, остановится ли она на следующем шаге или никогда.

Правило

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

Разбор: моделирование и две маленькие машины

Таблица - словарь: ключ склеен из состояния и символа, значение - список «что записать, куда, новое состояние». Функция zapusk выполняет шаги, пока машина не примет, не отвергнет или не исчерпает predel шагов, и возвращает исход, число шагов и ленту.

Первая машина прибавляет единицу к двоичному числу, записанному младшим разрядом вперёд: идёт вправо, заменяя единицы нулями, и первую же не-единицу заменяет единицей. Эта машина не распознаёт язык, а вычисляет: её ответ - лента после остановки, а «да» значит только «остановилась». Вторая идёт вправо, пока не встретит единицу.

def zapusk(tabl, vhod, predel):
    lenta = list(vhod)
    if len(lenta) == 0:
        lenta.append("_")
    sostoyanie = "0"
    poz = 0
    shagov = 0
    while sostoyanie != "да":
        klyuch = sostoyanie + lenta[poz]
        if klyuch not in tabl:
            return ["нет", shagov, "".join(lenta)]
        if shagov == predel:
            return ["не остановилась", shagov, "".join(lenta)]
        hod = tabl[klyuch]
        lenta[poz] = hod[0]
        if hod[1] == "R":
            poz = poz + 1
            if poz == len(lenta):
                lenta.append("_")
        elif poz > 0:
            poz = poz - 1
        sostoyanie = hod[2]
        shagov = shagov + 1
    return ["да", shagov, "".join(lenta)]

plyus = {}
plyus["01"] = ["0", "R", "0"]
plyus["00"] = ["1", "R", "да"]
plyus["0_"] = ["1", "R", "да"]
for vhod in ["0", "1", "1101", "111"]:
    print(vhod, zapusk(plyus, vhod, 1000))

vpravo = {}
vpravo["00"] = ["0", "R", "0"]
vpravo["0_"] = ["_", "R", "0"]
vpravo["01"] = ["1", "R", "да"]
print(zapusk(vpravo, "0001", 1000)[:2], zapusk(vpravo, "0000", 1000)[:2])

0 ['да', 1, '1_']
1 ['да', 2, '01_']
1101 ['да', 3, '0011']
111 ['да', 4, '0001_']
['да', 4] ['не остановилась', 1000]

Число 11 записано как 1101 (младший разряд слева: 1 + 2 + 8), результат 0011 - это 4 + 8, то есть 12. Конфигурации по шагам, головка в квадратных скобках:

состояние 0:   [1] 1  0  1          единица → ноль, вправо
состояние 0:    0 [1] 0  1          единица → ноль, вправо
состояние 0:    0  0 [0] 1          ноль → единица, принять
итог:           0  0  1  1

У числа 111 перенос доходит до пустой клетки, и машина дописывает разряд: лента выросла. Символ _ в конце напечатанной ленты - пустая клетка, на которую головка успела встать.

Вторая машина на входе 0001 принимает за четыре шага. На входе 0000 она проходит нули, выходит на пустые клетки и идёт по ним вправо: для пары «состояние 0, пустая клетка» в таблице есть строка, и она ведёт в то же состояние. Моделирование остановил предел в тысячу шагов - не машина. Ответа «нет» машина не дала и не даст.

Разбор: aⁿbⁿcⁿ вычёркиванием

План: заменить самую левую a на X, найти первую b и заменить на Y, найти первую c и заменить на Z, вернуться к X и повторить. Когда буквы a кончились, проверить, что остались только Y и Z.

состояние и его работа  что делает с символом под головкой
0  ищем очередную a:    a → X, вправо, в 1;   Y → вправо, в 4;
                        пусто → принять
1  идём к первой b:     a и Y пропускаем;     b → Y, вправо, в 2
2  идём к первой c:     b и Z пропускаем;     c → Z, влево, в 3
3  возвращаемся:        всё пропускаем влево; X → вправо, в 0
4  проверяем хвост:     Y и Z пропускаем;     пусто → принять

«Пропускаем» значит: символ переписывается самим собой, головка идёт дальше (вправо в состояниях 1, 2 и 4), состояние прежнее. В таблице это строка вида t["1a"] = ["a", "R", "1"].

def zapusk(tabl, vhod, predel):
    lenta = list(vhod)
    if len(lenta) == 0:
        lenta.append("_")
    sostoyanie = "0"
    poz = 0
    shagov = 0
    while sostoyanie != "да":
        klyuch = sostoyanie + lenta[poz]
        if klyuch not in tabl:
            return ["нет", shagov, "".join(lenta)]
        if shagov == predel:
            return ["не остановилась", shagov, "".join(lenta)]
        hod = tabl[klyuch]
        lenta[poz] = hod[0]
        if hod[1] == "R":
            poz = poz + 1
            if poz == len(lenta):
                lenta.append("_")
        elif poz > 0:
            poz = poz - 1
        sostoyanie = hod[2]
        shagov = shagov + 1
    return ["да", shagov, "".join(lenta)]

t = {}
t["0a"] = ["X", "R", "1"]
t["0Y"] = ["Y", "R", "4"]
t["0_"] = ["_", "R", "да"]
t["1a"] = ["a", "R", "1"]
t["1Y"] = ["Y", "R", "1"]
t["1b"] = ["Y", "R", "2"]
t["2b"] = ["b", "R", "2"]
t["2Z"] = ["Z", "R", "2"]
t["2c"] = ["Z", "L", "3"]
for simvol in "abYZ":
    t["3" + simvol] = [simvol, "L", "3"]
t["3X"] = ["X", "R", "0"]
t["4Y"] = ["Y", "R", "4"]
t["4Z"] = ["Z", "R", "4"]
t["4_"] = ["_", "R", "да"]
for vhod in ["abc", "aabbcc", "aabbc", "abcc", "aabcc", "acb"]:
    print(vhod, zapusk(t, vhod, 100000))
for n in [2, 4, 8, 16, 32]:
    print(n, zapusk(t, "a" * n + "b" * n + "c" * n, 100000)[:2])

abc ['да', 8, 'XYZ__']
aabbcc ['да', 23, 'XXYYZZ__']
aabbc ['нет', 13, 'XXYYZ_']
abcc ['нет', 7, 'XYZc']
aabcc ['нет', 9, 'XXYZc']
acb ['нет', 1, 'Xcb']
2 ['да', 23]
4 ['да', 77]
8 ['да', 281]
16 ['да', 1073]
32 ['да', 4193]

Ленты после работы показывают, что машина успела вычеркнуть к моменту остановки; подчёркивания в конце - пустые клетки, до которых дошла головка. В aabbc на втором проходе не нашлось буквы c: состояние 2 дошло до пустой клетки, строки в таблице для неё нет. В abcc вычёркивание прошло, а проверка хвоста наткнулась на лишнюю c. В aabcc второй проход не нашёл второй буквы b: состояние 1 упёрлось в c. В acb то же случилось на первом же проходе.

Пять рабочих состояний (не считая «да») и семнадцать строк таблицы решают задачу, недоступную никакому автомату со стеком. Последние пять строк вывода - число шагов при n от 2 до 32: при удвоении n оно растёт почти вчетверо, 4193 / 1073 ≈ 3,9. Проходов n, и каждый идёт через всю ленту длиной 3n: порядка n² шагов. Программа на обычном языке проверила бы то же самое за один проход. Машина Тьюринга не быстрая, и быстрой быть не должна: она нужна, чтобы очертить, что вычислимо в принципе.

Что ломается без этого

«Не остановилась» принято за «отвергла». Отвергнуть - значит остановиться с ответом «нет». Машина, которая работает вечно, ответа не даёт, и пользователь её не дождётся. Язык машины от этого не меняется, а польза от неё - очень.

Бесконечную ленту понимают как бесконечную память. В любой момент исписано конечное число клеток. Бесконечность означает только то, что машине никогда не скажут «место кончилось».

Машину считают моделью железа. Она модель вычисления по правилам. Настоящий процессор устроен иначе и работает быстрее, но не умеет ничего сверх - об этом следующий урок.

Медленная значит слабая. Квадрат вместо линии - цена простоты модели. Слабость модели - это задачи, которые она не решает вовсе; у машины Тьюринга такие есть - им посвящена следующая глава, - но те же задачи не решает и ни одна из известных моделей.

Зачем это в работе

Точное слово «алгоритм». Чтобы доказать, что алгоритма для задачи не существует, нужно определение, под которое подпадают все алгоритмы сразу. Машина Тьюринга - это определение: достаточно простое, чтобы о нём можно было доказывать теоремы.

Слово «тьюринг-полный». Так говорят о языке или системе, в которой можно смоделировать машину Тьюринга, а значит, записать любой алгоритм. Тьюринг-полными оказываются вещи, от которых этого не ждали: формулы электронных таблиц с пользовательскими функциями, SQL с рекурсивными запросами, шаблоны C++ - если не ограничивать им память и глубину. Для них это и возможность, и предупреждение: программа на тьюринг-полном языке может не остановиться, и заранее этого не узнать.

Единица измерения. Время и память алгоритма в теории сложности определяют через шаги и клетки машины Тьюринга; классы P и NPРазбирается в разделе 21, глава «P, NP, сведения и NP-полнота»: Класс NP: решение легко проверить, даже когда трудно найти из пятой главы - утверждения о ней.

Теперь сам

1. Проведи машину plyus по ленте 011: выпиши конфигурации и результат.
2. Что сделает машина для aⁿbⁿcⁿ на входе aabbcc за первый проход? Запиши ленту после него.
3. Какие три исхода возможны у машины Тьюринга на данном входе?
4. В таблице нет строки для пары «состояние 2, символ a». Что произойдёт, если машина окажется в такой ситуации?
5. Почему вторая машина первого разбора не останавливается на входе 0000 и как изменить одну строку таблицы, чтобы она отвергала такой вход?