Неразрешимое вне программ: домино Поста, уравнения и усердные бобры

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

Как думаешь, разрешима ли головоломка

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

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

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

Конструкторы, из которых случайно собирается компьютер. Игра «Жизнь» Конвея, где клетки на бесконечной сетке рождаются и умирают по числу живых соседей, стрелки и вагонетки в детской железной дороге, правила коллекционной карточной игры - во всех этих системах люди строили работающие вычислительные устройства. Никто не закладывал туда универсальность; она появилась сама, как только деталей стало достаточно для памяти и условного перехода.

Как только в системе можно собрать компьютер, многие вопросы о системе становятся вопросами о программах. А про программы мы уже знаем, на что ответа нет.

Механизм: как головоломка наследует неразрешимость

Проблема соответствий Поста. Дан конечный набор костей; на кости i написаны верхняя строка tᵢ и нижняя bᵢ. Решение - непустая последовательность номеров i₁, i₂, …, iₖ, с повторами, для которой tᵢ₁ tᵢ₂ … tᵢₖ = bᵢ₁ bᵢ₂ … bᵢₖ: верхние строки костей ряда, приписанные одна к другой, дают ту же строку, что и нижние. Здесь i₁ - номер кости, стоящей в ряду первой. Вопрос: есть ли решение?

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

Идея доказательства - сведение проблемы останова. По машине M и входу w строят набор костей, в котором совпадение надписей возможно только одним способом: обе надписи выписывают историю работы M на w, конфигурацию за конфигурацией. Нижняя надпись всё время опережает верхнюю на одну конфигурацию: кости устроены так, что, дописывая сверху текущую конфигурацию, снизу приходится дописать следующую, по правилам таблицы M. Например, строке таблицы «в состоянии q на символе a записать b, сдвинуться вправо, перейти в r» отвечает кость с qa сверху и br снизу, а каждому символу ленты - кость с ним сверху и снизу. Начало ряда закрепляют за костью с начальной конфигурацией отдельным приёмом с разделителями. Машину заранее переделывают так, чтобы любая её остановка была принятием. Догнать нижнюю надпись верхняя может только тогда, когда появится принимающее состояние: для него есть особые кости, которые «съедают» разницу. Решение существует тогда и только тогда, когда M останавливается.

Дальше по цепочке. Проблема Поста удобна тем, что в ней нет ничего, кроме строк, и к строковым задачам она сводится легко. Стрелка ниже значит «сводится к»; три нижние задачи получаются из проблемы Поста каждая напрямую. В первой номера костей дописаны к надписи, чтобы строка помнила, из каких костей собрана; у одной строки два дерева, через A и через B, ровно тогда, когда один и тот же ряд костей даёт одинаковые надписи сверху и снизу.

проблема останова
   → проблема соответствий Поста
        → неоднозначность КС-грамматики
              грамматика: S → A | B;  A строит верхнюю надпись и следом
              номера костей задом наперёд, B - то же с нижней;
              два дерева у строки ⇔ есть решение
        → пустота пересечения двух КС-языков
        → равенство двух КС-грамматик

Так выполняются обещания главы о грамматиках: вопросы, названные там неразрешимыми, неразрешимы поэтому.

Уравнения в целых числах. Десятая проблема Гильберта, 1900 год: найти способ по многочлену с целыми коэффициентами от нескольких переменных определять, есть ли у него целые корни - наборы целых значений всех переменных, при которых многочлен равен нулю. У x² + y² − z² такой корень есть: 3, 4, 5. В 1970 году Юрий Матиясевич, завершив работу Дэвиса, Патнема и Робинсон, доказал, что способа нет: многочленами можно изобразить работу любой машины.

Невычислимые функции. Функция усердного бобра BB(n) - наибольшее число шагов, которое делает до остановки машина Тьюринга с n состояниями и двумя символами, запущенная на пустой ленте; машины, которые не останавливаются, не в счёт. Состояние остановки в n не входит, а пустая клетка считается нулём. В каждой из 2n клеток таблицы - символ, направление и одно из n + 1 состояний, поэтому машин (4(n + 1))²ⁿ: конечное число, для пяти состояний - около шестидесяти триллионов. Значит, BB(n) - вполне определённое число. Но вычислить его в общем случае нельзя: зная BB(n), можно было бы решать проблему останова для таких машин - выполнить BB(n) шагов и, если машина ещё работает, объявить, что она не остановится. А к машинам на пустой ленте сводится и общий случай: вход можно вписать в саму таблицу, добавив состояния, которые его печатают.

Правило

Проблема соответствий Поста - существует ли ряд костей с одинаковыми верхней и нижней надписями - распознаваема и неразрешима. К ней сводится проблема останова, а она сводится к вопросам об однозначности и равенстве КС-грамматик. Неразрешимо и существование целых корней у многочлена от нескольких переменных с целыми коэффициентами. Функция усердного бобра определена для каждого n, но не вычислима: её значения позволяли бы решать проблему останова.

Разбор: три набора костей и что говорит перебор

Кость - пара строк. Функция sobrat выкладывает ряд по номерам и возвращает обе надписи. Функция perebor перебирает все последовательности длины 1, потом 2 и так далее до заданной и возвращает первую подходящую, её надпись и число проверенных последовательностей.

def sobrat(domino, nomera):
    verh = ""
    niz = ""
    for k in nomera:
        verh = verh + domino[k][0]
        niz = niz + domino[k][1]
    return [verh, niz]

def perebor(domino, naibolshaya):
    provereno = 0
    for dlina in range(1, naibolshaya + 1):
        nomera = [0] * dlina
        est_eshchyo = True
        while est_eshchyo:
            provereno = provereno + 1
            p = sobrat(domino, nomera)
            if p[0] == p[1]:
                return [nomera, p[0], provereno]
            i = dlina - 1
            while i >= 0 and nomera[i] == len(domino) - 1:
                nomera[i] = 0
                i = i - 1
            if i < 0:
                est_eshchyo = False
            else:
                nomera[i] = nomera[i] + 1
    return [[], "", provereno]

pervyj = [["b", "ca"], ["a", "ab"], ["ca", "a"], ["abc", "c"]]
print(sobrat(pervyj, [1, 0, 2, 1, 3]))
print(perebor(pervyj, 5))
vtoroj = [["100", "1"], ["0", "100"], ["1", "00"]]
print(perebor(vtoroj, 6))
print(sobrat(vtoroj, [0, 2, 0, 0, 2, 1, 1]))
tretij = [["ab", "a"], ["b", "ab"]]
print(perebor(tretij, 8))

['abcaaabc', 'abcaaabc']
[[1, 0, 2, 1, 3], 'abcaaabc', 636]
[[], '', 1092]
['1001100100100', '1001100100100']
[[], '', 510]

Первый набор - четыре кости. Ряд из костей с номерами 1, 0, 2, 1, 3 (считая с нуля) даёт сверху и снизу abcaaabc; перебор находит его на 636-й проверке: рядов короче пяти костей 4 + 16 + 64 + 256 = 340, и нужный ряд - 296-й среди пятёрок: номера перебираются как разряды счётчика, и ряд 1, 0, 2, 1, 3, прочитанный как число в четверичной записи, - это 295.

Второй набор - три кости. Перебор до длины 6 проверил 1092 последовательности и ничего не нашёл. Решения нет? Есть: четвёртая строка вывода показывает ряд из семи костей, у которого надписи совпадают. Предел был на единицу меньше, чем нужно. В этом и состоит трудность: «не найдено до длины L» ничего не говорит о длине L + 1, а верхней границы на длину кратчайшего решения, которую можно было бы вычислить по набору, не существует - иначе задача была бы разрешима.

Третий набор - две кости, и до длины 8 решения нет. Здесь это можно доказать. Начать ряд можно только с первой кости: у второй верх b и низ ab расходятся с первой буквы. После первой кости сверху ab, снизу a: верх ушёл вперёд на b, и следующая кость должна начинаться снизу с b. Таких костей нет. Для этого набора рассуждение нашлось; общего способа находить такие рассуждения нет.

Разбор: усердные бобры

Машины-рекордсмены для одного, двух, трёх и четырёх состояний известны. Формат прежний, только состояния - буквы от A, остановка - H, а лента бесконечна в обе стороны и сначала заполнена нулями. Функция bobr выполняет машину и возвращает: остановилась ли, сколько шагов сделала, сколько единиц на ленте.

def bobr(opisanie, predel):
    tabl = {}
    for pravilo in opisanie.split(" "):
        tabl[pravilo[0] + pravilo[1]] = [pravilo[2], pravilo[3],
                                         pravilo[4]]
    lenta = {}
    poz = 0
    sostoyanie = "A"
    shagov = 0
    while sostoyanie != "H" and shagov < predel:
        simvol = "0"
        if poz in lenta:
            simvol = lenta[poz]
        hod = tabl[sostoyanie + simvol]
        lenta[poz] = hod[0]
        if hod[1] == "R":
            poz = poz + 1
        else:
            poz = poz - 1
        sostoyanie = hod[2]
        shagov = shagov + 1
    edinic = 0
    for k in lenta:
        if lenta[k] == "1":
            edinic = edinic + 1
    return [sostoyanie == "H", shagov, edinic]

odin = "A01RH"
dva = "A01RB A11LB B01LA B11RH"
tri = "A01RB A11RH B01LB B10RC C01LC C11LA"
chetyre = "A01RB A11LB B01LA B10LC C01RH C11LD D01RD D10RA"
pyat = "A01RB A11LC B01RC B11RB C01RD C10LE D01LA D11LD E01RH E10LA"
for m in [odin, dva, tri, chetyre]:
    print(bobr(m, 1000))
print(bobr(pyat, 5000))

[True, 1, 1]
[True, 6, 4]
[True, 21, 5]
[True, 107, 13]
[False, 5000, 87]

В каждой строке вывода - остановилась ли машина, число шагов и число единиц на ленте. Рекорды по числу шагов: 1, 6, 21, 107. Машина с четырьмя состояниями - восемь строк таблицы - останавливается через 107 шагов, и доказано, что никакая другая машина с четырьмя состояниями, останавливаясь, не работает дольше.

Пятая машина за пять тысяч шагов не остановилась. Она остановится - через 47 176 870 шагов; та же функция с пределом в пятьдесят миллионов до этого досчитала бы, но ждать пришлось бы долго. То, что это именно рекорд, было доказано только в 2024 году, совместной работой добровольцев, с проверкой доказательства компьютером: про каждую из огромного числа машин с пятью состояниями, которая не останавливается, пришлось это доказать. Для шести состояний известна лишь нижняя оценка, и она больше «башни» из пятнадцати десяток, возведённых одна в степень другой.

Функция BB, первые значения которой 1, 6, 21, 107, 47 176 870, не умещается ни под какую вычислимую функцию - это не «очень быстро», а выше всякой оценки, для которой есть программа. Иначе эту программу можно было бы использовать как предел шагов и решить проблему останова. Каждое следующее значение требует не вычисления, а новых доказательств, и доказано, что начиная с некоторого числа состояний значение вообще нельзя вывести из общепринятых аксиом математики.

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

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

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

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

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

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

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

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

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

Теперь сам

1. Набор костей: верх a, низ aa; верх aa, низ a. Есть ли решение?
2. Набор из одной кости: верх ab, низ abb. Есть ли решение и как это доказать?
3. Почему проблема соответствий Поста распознаваема?
4. Как, зная BB(4) = 107, выяснить, остановится ли данная машина с четырьмя состояниями на пустой ленте?
5. Кто-то перебрал все ряды до длины 30 и не нашёл решения. Что он доказал?