Варианты машины и тезис Чёрча-Тьюринга: почему модель одна

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

Как думаешь, сильнее ли машина с двумя лентами

Одна лента - очевидное неудобство: чтобы сравнить два куска входа, головка бегает туда и обратно. Дадим машине вторую ленту со своей головкой: на одну можно переписать кусок, по другой идти и сверять.

Ответь себе до чтения: появятся ли языки, которые двухленточная машина принимает, а одноленточная - нет? Не появятся. Одноленточная машина может записать содержимое обеих лент на свою единственную, пометить, где стоят головки, и выполнять шаги двухленточной по одному, каждый раз проходя по всей записи. Это медленнее, но ответ тот же. С автоматами было иначе: стек добавил языков. Здесь добавлять уже нечего.

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

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

Языки отличаются удобством и скоростью, а не тем, что на них возможно. Модели вычислений - тоже.

Механизм: моделирование и что оно стоит

Сравнивают модели так. Модель A моделирует модель B, если для каждой машины из B можно построить машину из A, которая на каждом входе даёт тот же исход: принимает, отвергает или не останавливается. Если моделирование есть в обе стороны, модели равносильны: языки у них одни и те же.

Варианты машины Тьюринга и цена их перевода в исходную модель:

вариант                  как моделируется одной лентой    цена по времени
лента, бесконечная       сложить пополам:                 того же порядка
в обе стороны            в клетке пара символов
k лент со своими         все ленты подряд,                t шагов →
головками                головки помечены                 порядка t²
память с доступом        адреса и содержимое              многочлен от t
по адресу                записаны на ленте
недетерминированная      перебор всех вариантов           t шагов →
машина                   шага в ширину                    порядка bᵗ

Здесь t - число шагов исходной машины, b - наибольшее число вариантов одного шага. Считаем, что t не меньше длины входа: машине с адресами дальняя клетка входа доступна за шаг, а ленточной до неё надо дойти.

Что стоит за строками таблицы. Ленту без левого края складывают по клетке 0: в клетке i новой ленты лежат два символа, из клеток i и −i старой, а состояние помнит, по какой половине идёт головка; на левой половине направления меняются местами. У машины с k лентами один шаг читает по символу с каждой ленты и для каждой говорит, что записать и куда сдвинуть головку. Память с доступом по адресу - это пронумерованные ячейки с числами, как список в Python; одна лента хранит пары «адрес, содержимое» и ищет нужную ячейку просмотром. Многочлен в этой строке получается, пока числа в ячейках не слишком длинны: длина их записи растёт не быстрее многочлена от размера входа.

Недетерминированная машина определена как раньше: в таблице на пару «состояние, символ» может быть несколько строк; машина принимает вход, если хотя бы одна последовательность выборов ведёт в принимающее состояние; отвергает, если все последовательности останавливаются и ни одна не принимает; иначе не останавливается. Детерминированная машина моделирует её, обходя дерево конфигураций в ширину: уровень i - все конфигурации, достижимые за i шагов. Обход в глубину не годится: он может уйти в ветку, которая не останавливается, и не дойти до принимающей. Угадывание, как и у конечных автоматов, не добавляет языков. Но у автоматов оно стоило экспоненты в числе состояний, а здесь - экспоненты во времени, и можно ли обойтись многочленом, неизвестно: это вопрос о P и NPРазбирается в разделе 21, глава «P, NP, сведения и NP-полнота»: Класс NP: решение легко проверить, даже когда трудно найти из пятой главы.

Другие определения. В 1930-е годы вычислимость определяли несколько человек, независимо и совсем по-разному: Чёрч - через подстановку в выражения с функциями, Гёдель и Клини - через функции на числах, построенные рекурсией, Пост и Тьюринг - через машины. Все определения оказались равносильны: каждое моделирует каждое. Позже добавились машины с регистрами, клеточные автоматы, языки программирования - с тем же результатом.

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

Правило

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

Разбор: лента из двух стеков

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

Функция na_stekah выполняет ту же таблицу для aⁿbⁿcⁿ, что и в прошлом уроке, не имея ленты вовсе.

def na_stekah(tabl, vhod, predel):
    levyj = []
    pravyj = []
    for i in range(len(vhod) - 1, -1, -1):
        pravyj.append(vhod[i])
    sostoyanie = "0"
    shagov = 0
    while sostoyanie != "да":
        if len(pravyj) == 0:
            pravyj.append("_")
        klyuch = sostoyanie + pravyj[-1]
        if klyuch not in tabl:
            return ["нет", shagov]
        if shagov == predel:
            return ["не остановилась", shagov]
        hod = tabl[klyuch]
        pravyj.pop()
        if hod[1] == "R":
            levyj.append(hod[0])
        else:
            pravyj.append(hod[0])
            if len(levyj) > 0:
                pravyj.append(levyj.pop())
        sostoyanie = hod[2]
        shagov = shagov + 1
    return ["да", shagov]

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"]:
    print(vhod, na_stekah(t, vhod, 100000))
for n in [2, 4, 8, 16, 32]:
    print(n, na_stekah(t, "a" * n + "b" * n + "c" * n, 100000))

abc ['да', 8]
aabbcc ['да', 23]
aabbc ['нет', 13]
abcc ['нет', 7]
2 ['да', 23]
4 ['да', 77]
8 ['да', 281]
16 ['да', 1073]
32 ['да', 4193]

Исходы и число шагов совпали с прошлым уроком до единицы: 8, 23, 13 и 7 на коротких входах; 23, 77, 281, 1073 и 4193 на длинных. Моделирование здесь точное, шаг в шаг.

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

Разбор: что стоит перевод между моделями

Возьмём машину с двумя лентами, которая делает t шагов. Одноленточная машина хранит обе ленты подряд через разделитель и помечает клетки, где стоят головки:

лента 1:   a  b [a] b            одна лента:    a  b  a° b  #  X  Y° _
лента 2:   X [Y] _               кружок - «здесь стоит головка»

Один шаг двухленточной машины превращается в проход: дойти до обеих пометок, прочитать символы под ними, вернуться и исправить запись. Если первой ленте нужна новая клетка, хвост записи сдвигают на клетку вправо - это ещё один проход того же порядка. За t шагов головки уходят не дальше чем на t клеток; если вход не длиннее t, вся запись занимает порядка t клеток, поэтому проход стоит порядка t шагов, а всё моделирование - порядка t · t = t². Тысяча шагов на двух лентах - не больше порядка миллиона на одной.

С недетерминизмом иначе. Пусть на каждом шаге у машины не больше двух вариантов и она работает t шагов. Дерево её вычислений имеет до 2ᵗ листьев, и обход в ширину просматривает их все:

шагов t                      10        20         50          100
конфигураций на уровне t     1024      10⁶        10¹⁵        10³⁰

Сто шагов угадывания превращаются в 10³⁰ конфигураций. Языки те же, но такое моделирование практически невыполнимо уже на маленьких входах.

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

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

«Тезис доказан». Он не может быть доказан: одна из его сторон - неформальное понятие. Доказаны теоремы о равносильности конкретных моделей, и их много; тезис - обобщение этих теорем.

«Квантовый компьютер вычисляет то, что обычному недоступно». По части того, что вычислимо, - нет: квантовую машину можно смоделировать обычной, с экспоненциальным замедлением. Вопрос только в скорости, и он разобран в последней главе разделаРазбирается в разделе 21, глава «Квантовая модель - кубит, интерференция, алгоритм Шора»: Алгоритм Шора и границы: что квантовый компьютер ускоряет, а что нет.

«Раз модели равны, скорость не важна». Равны классы вычислимого. Квадратичное замедление на практике отличает работающую программу от неработающей; теория пренебрегает им сознательно, чтобы её выводы не зависели от модели.

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

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

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

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

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

Теперь сам

1. Машина с тремя лентами делает 500 шагов. Оцени сверху порядок числа шагов одноленточной машины, которая её моделирует.
2. Недетерминированная машина делает 40 шагов, на каждом у неё до двух вариантов. Сколько конфигураций может оказаться на последнем уровне дерева?
3. Как в модели из двух стеков сдвинуть головку влево?
4. Почему тезис Чёрча-Тьюринга нельзя доказать, но можно было бы опровергнуть?
5. Кто-то предлагает модель «машина Тьюринга с двумерной лентой». Что нужно сделать, чтобы показать, что она не сильнее обычной?