Универсальная машина: программа как данные, разрешимое и распознаваемое

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

Как думаешь, сколько нужно машин

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

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

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

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

Следствие, которое легко пропустить: ноты можно переписывать, сравнивать, сокращать, как любой текст. И можно написать музыку, в которой исполнитель читает ноты другой пьесы.

Механизм: описание машины, универсальная машина, два вида ответа

Описание машины. Таблица переходов - конечный набор строк, каждая из пяти частей: состояние, символ, что записать, куда сдвинуться, новое состояние. Запишем их подряд - получится строка символов. Любой алфавит можно закодировать нулями и единицами, поэтому описание любой машины - двоичная строка. Обозначим описание машины M как ⟨M⟩.

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

Универсальная машина U получает на ленте пару ⟨M⟩ и w, записанных через разделитель - символ, которого нет в описаниях, - и моделирует работу M на входе w: хранит на ленте текущую конфигурацию M, на каждом шаге находит в описании подходящую строку таблицы и применяет её. Если M принимает w - принимает и U; отвергает - отвергает; не останавливается - не останавливается и U. Функция zapusk из первого урока главы и была такой машиной, только записанной на Python; по тезису из прошлого урока всё, что так записано, переводится в настоящую таблицу переходов. Оговорка одна: предел шагов в ней поставлен, чтобы программа урока завершалась, а настоящая универсальная машина моделирует без предела. Одна программа, любая таблица на входе.

Разрешимый и распознаваемый. Теперь, когда машина может не остановиться, у слова «машина для языка» два смысла.

машина распознаёт язык L   на строках из L останавливается и принимает;
                           на остальных отвергает ИЛИ не останавливается
машина разрешает язык L    на каждой строке останавливается:
                           на строках из L принимает,
                           на остальных отвергает

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

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

Универсальная машина распознаёт язык всех пар ⟨M⟩, w, в которых M принимает w. Разрешает ли? Если M на w не останавливается, U тоже работает вечно, так что сама U - нет. Может быть, есть машина хитрее - на это отвечает следующая глава.

Правило

Описание машины Тьюринга - строка, и существует универсальная машина, которая по описанию ⟨M⟩ и входу w моделирует M на w. Язык разрешим, если его принимает машина, останавливающаяся на всех входах, и распознаваем, если его принимает хоть какая-то машина. Если распознаваемы язык и его дополнение, язык разрешим.

Разбор: одна программа для всех таблиц

Описание машины - строка: правила через пробел, в каждом пять символов - состояние, читаемый символ, записываемый, направление, новое состояние; принимающее состояние обозначено +. Формат рассчитан на маленькие машины: имя состояния и символ ленты - по одному знаку. Для больших машин имена кодируют числами одинаковой длины; суть от этого не меняется. Функция universalnaya разбирает описание в таблицу и выполняет её. Функция v_bity кодирует любой текст из восьми используемых символов нулями и единицами, по три бита на символ.

def universalnaya(opisanie, vhod, predel):
    tabl = {}
    for pravilo in opisanie.split(" "):
        tabl[pravilo[0] + pravilo[1]] = [pravilo[2], pravilo[3],
                                         pravilo[4]]
    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]
        if shagov == predel:
            return ["не остановилась", shagov]
        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]

def v_bity(tekst):
    alfavit = "012_+RL "
    bity = ""
    for simvol in tekst:
        nomer = 0
        while alfavit[nomer] != simvol:
            nomer = nomer + 1
        bity = (bity + str(nomer // 4) + str(nomer // 2 % 2)
                + str(nomer % 2))
    return bity

plyus = "010R0 001R+ 0_1R+"
chyot = "000R0 011R1 100R1 110R0 0__R+"
vpravo = "000R0 0__R0 011R+"
for para in [[plyus, "1101"], [chyot, "1101"], [chyot, "1001"]]:
    print(universalnaya(para[0], para[1], 1000))
kod = v_bity(chyot)
print(len(chyot), len(kod), kod[:24])
print(universalnaya(chyot, kod, 1000),
      universalnaya(chyot, v_bity(vpravo), 1000))
print(universalnaya(vpravo, v_bity(vpravo), 1000),
      universalnaya(vpravo, "0000", 1000))

['да', 3]
['нет', 4]
['да', 5]
29 87 000000000101000111000001
['да', 88] ['нет', 51]
['да', 10] ['не остановилась', 1000]

Три машины - три строки. plyus прибавляет единицу, vpravo идёт вправо до первой единицы; обе знакомы по первому уроку. chyot принимает строки с чётным числом единиц: состояние 0 - «пока чётно», состояние 1 - «пока нечётно», и пустая клетка принимается только из состояния 0. Первые три строки вывода - обычные запуски: plyus на 1101 принимает за три шага; в 1101 три единицы, ответ «нет»; в 1001 две, ответ «да».

Четвёртая строка: описание chyot занимает 29 символов и 87 бит - по три бита на символ; дальше напечатаны первые 24 бита, то есть восемь символов 000R0 01. Эти 87 бит можно прочитать как одно двоичное число: машина записана числом.

Пятая строка - главное. Машина chyot получает на вход двоичный код описания машины - сначала своего собственного, потом чужого. В её собственном коде единиц чётное число, 34, и она себя принимает; в коде vpravo их 19, ответ «нет». Ничего парадоксального не произошло: описание - обычная строка, и машина, работающая со строками, работает и с ней.

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

Разбор: предел шагов не делает решателя

Решателем дальше для краткости называется разрешающая машина, распознавателем - распознающая.

Напрашивается способ превратить распознающую машину в разрешающую: моделировать не больше N шагов и, если ответа нет, ответить «нет». Посмотрим на программу, про которую неизвестно, всегда ли она останавливается. Берём число; чётное делим на два, нечётное умножаем на три и прибавляем единицу; повторяем, пока не получится единица.

def do_edinicy(n, predel):
    shagov = 0
    while n != 1:
        if shagov == predel:
            return "не знаю"
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        shagov = shagov + 1
    return shagov

for predel in [20, 120, 200]:
    otvety = []
    for n in [6, 7, 27, 97, 871]:
        otvety.append(do_edinicy(n, predel))
    print(predel, otvety)

20 [8, 16, 'не знаю', 'не знаю', 'не знаю']
120 [8, 16, 111, 118, 'не знаю']
200 [8, 16, 111, 118, 178]

При пределе 20 для чисел 27, 97 и 871 ответ «не знаю». При пределе 120 два из них получили ответ: 111 и 118 шагов. Число 871 дождалось только предела 200: ему нужно 178 шагов.

Каждое «не знаю» в этой таблице оказалось «да, остановится, просто позже». Заменить его на «нет» было бы ошибкой, и никакой заранее выбранный предел от неё не страхует: для любого N найдётся вход, которому нужно больше: степень двойки 2ᴺ⁺¹ делится пополам ровно N + 1 раз. Остановится ли эта программа для каждого положительного начального числа, не знает никто: это открытая задача с 1937 года, гипотеза Коллатца, проверенная компьютером для всех чисел до 2⁶⁸ и дальше.

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

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

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

«Не ответила за минуту - значит зациклилась». Это предположение, а не вывод. Программа могла быть на шаг от ответа.

«Не знаю» превращено в «нет». Проверяющая система, которая по тайм-ауту объявляет «ошибок нет» или «совпадений нет», врёт ровно в тех случаях, ради которых её запускали.

Распознаваемое принято за разрешимое. Перебор, который находит ответ, когда он есть, - это распознаватель. Если ответа нет, он не остановится, и это свойство задачи, а не недоработка кода.

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

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

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

Самоприменение. Компилятор, написанный на том языке, который он компилирует; интерпретатор Python, выполняющий интерпретатор Python; программа, печатающая собственный текст. Всё это законно, потому что программа - данные. И это же делает возможным рассуждение следующей главы, в котором машину спрашивают о ней самой.

Теперь сам

1. Что универсальная машина получает на вход и что возвращает?
2. Машина на входе w работает уже миллион шагов. Что ты можешь сказать о том, принадлежит ли w её языку?
3. Язык и его дополнение оба распознаваемы. Как построить машину, которая разрешает язык?
4. Запиши в формате этого урока машину, которая принимает строки из нулей и единиц, начинающиеся с единицы.
5. Чем ответ «не знаю» при пределе 20 отличается от ответа «нет»?