Теория вычислений для всех: автоматы, машина Тьюринга и что нельзя вычислить

В статье https://courses.digitable.life/post/computer-science/01-what-is-computation/ мы выяснили, что вообще значит «вычислить»: механически преобразовать символы по конечному набору правил. Там же появилась машина Тьюринга и знаменитая проблема остановки. Но машина Тьюринга — это самый мощный инструмент в целом семействе. Ниже неё есть машины попроще: слабее, зато настолько простые, что про них можно строго доказывать, что они умеют, а чего — нет. И именно эти «игрушечные» машины живут внутри вашего кода прямо сейчас: в регулярных выражениях, в парсерах, в разборе сетевых протоколов, в валидации ввода.

Теория вычислений отвечает на три разных вопроса, которые новички часто путают в один:

• Что можно вычислить в принципе? — граница вычислимости (разрешимо / неразрешимо).
• Какая машина нужна, чтобы решить эту задачу? — иерархия автоматов и языков.
• Как быстро это можно вычислить? — теория сложности (P, NP и далее).

Эта статья — про первые два, с мостиком к третьему. Мы поднимемся по «лестнице машин» снизу вверх, поймём, где у каждой ступени стена, и увидим, зачем инженеру знать, что HTML нельзя разобрать регуляркой, а идеального линтера не бывает в принципе. Глубже сложность и алгоритмы — в https://courses.digitable.life/post/computer-science/10-algorithms-and-complexity/ и в отдельном треке https://courses.digitable.life/post/algorithms/00-overview/.

Задача как язык: почему теоретики говорят про множества строк

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

• Алфавит $\Sigma$ — конечное множество символов, например $\lbrace 0, 1 \rbrace$ или буквы ASCII.
• Строка — конечная последовательность символов алфавита.
• Язык $L$ — какое-то (возможно бесконечное) множество строк над $\Sigma$.

Теперь любая задача-распознавание — это язык. «Является ли строка корректным email?» — язык всех корректных email. «Делится ли двоичное число на 3?» — язык всех двоичных записей чисел, кратных трём. «Является ли текст синтаксически верной программой на Python?» — язык всех валидных программ. Машина решает задачу, если она принимает ровно те строки, что лежат в языке, и отвергает все остальные.

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

Ступень 1. Конечный автомат: машина вообще без памяти

Самая слабая полезная машина — конечный автомат (finite automaton, DFA). У него есть только конечное число состояний, и он читает вход слева направо по одному символу, на каждом символе перескакивая из состояния в состояние по фиксированной таблице переходов. Никакой дополнительной памяти: всё, что автомат «помнит» о прочитанном, — это в каком из конечного числа состояний он сейчас находится.

Разберём конкретный автомат: принимает двоичные строки, в которых чётное число единиц. Достаточно двух состояний — «чётно» и «нечётно», — и единицы переключают между ними, а нули ничего не меняют.

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

def even_ones(s: str) -> bool:
    # Состояние — единственная переменная памяти: True = чётно, False = нечётно.
    state_even = True
    for ch in s:                 # один проход слева направо
        if ch == "1":
            state_even = not state_even   # единица переключает чётность
        # ноль ничего не меняет
    return state_even            # принимаем, если закончили в «чётном» состоянии

# O(n) по времени, O(1) по памяти — независимо от длины входа.

Ключевое здесь — O(1) по памяти. Сколько бы ни была длинна строка — миллион символов, миллиард, — автомату хватает одной переменной. Это и сила, и приговор: раз память фиксирована, автомат физически не может «сосчитать» что-то неограниченное.

Регулярные языки = регулярные выражения

Языки, которые распознают конечные автоматы, называются регулярными. И вот факт, который стоит знать каждому, кто хоть раз писал grep: теорема Клини утверждает, что регулярные языки — это ровно те, что описываются регулярными выражениями. Конечный автомат и регулярка — два лица одного и того же класса. Когда движок компилирует ^a*b+$, он в буквальном смысле строит конечный автомат и прогоняет по нему вход за один линейный проход. Поэтому «настоящие» регулярки так быстры и предсказуемы: O(n), без возвратов.

Конечные автоматы вездесущи именно потому, что они дёшевы и доказуемо корректны:

• лексеры компиляторов режут исходник на токены конечным автоматом (см. https://courses.digitable.life/post/computer-science/07-from-code-to-execution/);
• состояния TCP-соединения (SYN-SENT, ESTABLISHED, CLOSE-WAIT…) — это конечный автомат (см. https://courses.digitable.life/post/computer-science/11-networking-basics/);
• светофор, турникет, меню банкомата, разбор протокола — всё это конечные автоматы.

Стена конечного автомата: он не умеет считать

А теперь фундаментальный предел. Рассмотрим язык сбалансированных скобок: (), (()), (()()) — верны, а (() или ()) — нет. Или его чистую версию $L = \lbrace a^n b^n \mid n \geq 0 \rbrace$ — сначала $n$ букв a, потом ровно столько же b.

Конечный автомат этого не может. Интуиция простая: чтобы проверить, что закрывающих скобок ровно столько же, сколько открывающих, нужно запомнить их число — а оно неограниченно. Автомат же имеет конечное число состояний, скажем $k$. Подайте ему строку с $k+1$ открывающими скобками — по принципу Дирихле он дважды окажется в одном и том же состоянии, то есть «забудет» разницу и начнёт путать длины. Формально это доказывает лемма о накачке (pumping lemma): в любой достаточно длинной строке регулярного языка есть кусок, который можно повторять («накачивать») сколько угодно раз, оставаясь в языке. Для aⁿbⁿ такого куска нет — значит, язык не регулярен.

Отсюда — самый цитируемый практический вывод всей теории:

Регулярным выражением нельзя разобрать HTML, JSON, сбалансированные скобки или любую вложенную структуру.

Вложенность может быть произвольной глубины, а у конечного автомата памяти на «глубину» нет. Знаменитый ответ на Stack Overflow про «regex и HTML» — это не шутка и не снобизм, это теорема Клини. Если вам кажется, что регулярка парсит вложенность, — либо ваш движок на самом деле уже не регулярный (см. ниже про backreferences), либо вы проверяете лишь ограниченную глубину.

Ступень 2. Магазинный автомат: добавим стек

Что нужно добавить конечному автомату, чтобы он осилил вложенные скобки? Память, но особого вида — стек (LIFO). Такая машина называется магазинным автоматом (pushdown automaton, PDA): конечное управление плюс неограниченный стек, куда можно класть и откуда снимать по одному символу.

Со стеком скобки берутся элементарно: открывающую — кладём на стек, закрывающую — снимаем; если в конце стек пуст и мы ни разу не сняли с пустого — строка сбалансирована.

def balanced(s: str) -> bool:
    stack = []                       # неограниченная память-стек
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in "([{":
            stack.append(ch)         # push при открывающей
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:  # pop и проверка пары
                return False
    return not stack                 # верно, только если стек в конце пуст

# O(n) по времени, O(n) по памяти в худшем случае (глубина вложенности).

Языки, которые распознают магазинные автоматы, называются контекстно-свободными (context-free) и задаются контекстно-свободными грамматиками — теми самыми правилами вида выражение → выражение "+" выражение, которые вы видели в BNF/EBNF. Это ровно тот класс, что описывает синтаксис языков программирования: вложенные блоки, скобки, арифметические выражения с приоритетами. Поэтому все настоящие парсеры внутри используют стек — явный или неявный (через рекурсию, которая живёт на стеке вызовов). Разбор выражения a * (b + c) — это работа магазинного автомата.

Но и у стека есть потолок. Язык $\lbrace a^n b^n c^n \mid n \geq 0 \rbrace$ — равное число a, b и c подряд — контекстно-свободным уже не является. Стек позволяет сопоставить две группы (снял ровно столько, сколько положил), но не три: сопоставив a c b, вы опустошили стек и вам нечем считать c. Нужна ещё более гибкая память.

Ступень 3. Машина Тьюринга: неограниченная лента

Замените стек на бесконечную ленту, по которой можно двигаться в обе стороны и свободно перезаписывать ячейки, — и вы получите машину Тьюринга, вершину лестницы (её устройство мы подробно разобрали в https://courses.digitable.life/post/computer-science/01-what-is-computation/). Лента — это неограниченная память с произвольным доступом, и её хватает на всё: aⁿbⁿcⁿ, арифметику, сортировку, компиляцию — любую вычислимую задачу.

Вот вся лестница на одной картинке: одно и то же конечное управление, но с разной памятью.

Разницу между ступенями удобно записать как «управление + память»:

Каждая следующая ступень строго мощнее предыдущей: она умеет всё, что нижняя, и ещё что-то сверх. Это и есть иерархия Хомского — классификация языков (и порождающих их грамматик), которую Ноам Хомский предложил ещё в 1956 году, изучая… естественные языки.

Иерархия языков: карта того, что какая машина осилит

Между контекстно-свободными языками и полной машиной Тьюринга есть ещё промежуточный слой (контекстно-зависимые языки — там aⁿbⁿcⁿ уже помещается), но для «большой картины» важнее общая вложенность. Соберём всё в одну карту — от самых слабых машин снаружи к самым мощным задачам внутри.

Строгая вложенность (каждый класс — подмножество следующего) — не случайность, а прямое следствие того, что верхняя машина умеет симулировать нижнюю. А вот два верхних слоя — «разрешимые» и «распознаваемые» — стоит разобрать отдельно: разница между ними и есть сердце теории вычислимости.

Разрешимо vs распознаваемо: две разные силы одной машины

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

• Язык разрешим (decidable / recursive), если есть машина, которая на любом входе за конечное время останавливается и говорит «да» или «нет». Это то, что мы обычно и называем «алгоритмом»: он всегда завершается.
• Язык распознаваем (recognizable / recursively enumerable), если есть машина, которая на строках из языка останавливается и говорит «да», но на строках не из языка имеет право зациклиться навсегда, так и не ответив.

Разница огромная. Распознавание — это «если ответ „да“, ты рано или поздно это узнаешь; если „нет“ — можешь ждать вечно и не понять, ждать ли дальше». Классический пример: ищем доказательство теоремы перебором всех цепочек вывода. Если теорема доказуема — переборщик когда-нибудь наткнётся на доказательство и скажет «да». Если недоказуема — он будет искать бесконечно, и вы никогда не будете уверены, что доказательства правда нет.

Проблема остановки — распознаваема, но не разрешима: если программа и правда останавливается, мы это узнаем, просто её запустив и дождавшись; но если она зацикливается, никакой универсальный метод не подтвердит это за конечное время. А дополнение проблемы остановки («зациклится ли программа?») — не распознаваемо вовсе. Так три верхних слоя карты — разрешимые, распознаваемые, все языки — оказываются строго разными.

Как доказывают неразрешимость: сведения

Проблему остановки и её неразрешимость мы разобрали в https://courses.digitable.life/post/computer-science/01-what-is-computation/ через самоприменение (диагональный аргумент). Но как показать, что неразрешима другая задача, не повторяя каждый раз хитрый парадокс? Главный инструмент — сведение (reduction).

Идея зеркальна той, что используют программисты каждый день («сведу новую задачу к уже решённой библиотечной»), только с обратным знаком. Если бы я умел решать задачу B, я бы с её помощью решил заведомо неразрешимую задачу A — значит, B тоже неразрешима, иначе противоречие.

Так, одно за другим, «заражаются» неразрешимостью десятки практических вопросов:

• Эквивалентны ли две программы (дают ли одинаковый результат на всех входах)? Неразрешимо.
• Достижима ли эта строка кода при каком-нибудь входе? В общем случае неразрешимо.
• Соответствие Поста (Post correspondence problem) — безобидная головоломка про домино с надписями — неразрешимо.
• Совпадают ли языки двух контекстно-свободных грамматик? Неразрешимо (хотя каждая грамматика по отдельности разрешима!).

Кульминация — теорема Райса: любое нетривиальное свойство того, что программа вычисляет (а не того, как она написана), неразрешимо. «Всегда ли возвращает положительное число», «вычисляет ли она квадрат», «содержит ли вирусное поведение» — всё это, в общем виде, невычислимо. Не потому что мы не придумали алгоритм, а потому что его не существует.

От «можно» к «быстро»: намёк на сложность

Разрешимость отвечает «можно ли вообще?». Но инженеру важнее второй вопрос: «можно ли за разумное время?». Задача может быть идеально разрешимой и при этом практически безнадёжной.

• P — задачи, разрешимые за полиномиальное время (сортировка, поиск, кратчайший путь). Это «практически быстро».
• NP — задачи, где проверить готовый ответ можно быстро, а вот найти его известными методами — перебором, экспоненциально дорого (задача коммивояжёра, выполнимость формул SAT, раскраска графа).
• Вопрос P = NP? — открыт: никто не доказал ни что быстрые алгоритмы для NP-задач существуют, ни что их нет. Это самая знаменитая нерешённая проблема информатики (премия 1 000 000 USD от Clay Institute).

Все NP-трудные задачи лежат внутри разрешимых — они вычислимы, просто дорого. На этом разрыве «легко проверить, трудно решить» держится вся современная криптография (см. https://courses.digitable.life/post/computer-science/16-security-basics/). Big-O-интуицию и классы сложности мы разбираем в https://courses.digitable.life/post/computer-science/10-algorithms-and-complexity/, а глубоко — в https://courses.digitable.life/post/algorithms/00-overview/.

Полезно держать в голове всю «карту силы» разом:

Где эта теория протекает в реальный код

Может показаться, что автоматы и ленты — забава для учебника. На деле граница между ступенями лестницы протекает в инженерную практику постоянно.

• «Регулярки», которые уже не регулярны. Как только в движок добавляют backreferences (\1) — например, (.+)\1 для поиска повторов, — язык перестаёт быть регулярным, а движок теряет гарантию O(n). Отсюда катастрофический бэктрекинг: невинное выражение вроде (a+)+$ на строке из сорока a и одной b заставляет движок перебирать экспоненциальное число вариантов и вешает сервер. Это реальная категория уязвимостей — ReDoS. Движки вроде RE2 (Google) сознательно запрещают backreferences, чтобы остаться настоящими конечными автоматами и гарантировать линейность.
• Не парсите вложенное регуляркой. HTML, JSON, языки программирования, конфиги с вложенностью — это контекстно-свободные структуры. Им нужен парсер (магазинный автомат), а не регулярка. Попытка «дожать регуляркой» ломается на первом же неожиданном вложении.
• Правильный уровень для задачи. Выбор инструмента — это выбор ступени лестницы. Список простых токенов — регулярка. Вложенные выражения — грамматика и парсер. Общая логика — обычный код. Не берите машину мощнее, чем нужно: чем слабее модель, тем больше про неё можно доказать и тем предсказуемее она работает.
• Осторожно с тьюринг-полнотой в конфигах. Стоит дать языку шаблонов или правил произвольные циклы — и он становится тьюринг-полным, а вопрос «завершится ли обработка этого конфига» — неразрешимым (теорема Райса). Часто осознанно оставляют язык слабым (без произвольной рекурсии), чтобы про конфиг можно было доказывать свойства и гарантировать остановку.
• Идеального линтера и антивируса не бывает. «Точно ли этот код зациклится / имеет гонку / содержит вредонос» — нетривиальные свойства поведения, а по Райсу они неразрешимы. Поэтому реальные анализаторы всегда выбирают между консервативностью (иногда ложно ругаются) и неполнотой (иногда пропускают). Третьего, «идеального», варианта не существует — и это доказано, а не «пока не сделали».

Мини-итог

• Любую да/нет-задачу удобно видеть как язык — множество строк; машина решает задачу, если принимает ровно этот язык.
• Машины выстраиваются в лестницу по памяти: конечный автомат (нет памяти) → магазинный автомат (стек) → машина Тьюринга (лента). Каждая ступень строго мощнее.
• Им соответствует иерархия языков: регулярные ⊂ контекстно-свободные ⊂ разрешимые ⊂ распознаваемые ⊂ все языки. Регулярки не считают, поэтому не парсят вложенность; стек справляется с синтаксисом; лента — со всем вычислимым.
• Разрешимо (всегда останавливается) ≠ распознаваемо (останавливается только на «да»). Проблема остановки — распознаваема, но неразрешима; её дополнение — даже не распознаваемо.
• Неразрешимость доказывают сведением; теорема Райса делает неразрешимым любое нетривиальное свойство поведения программ.
• «Вычислимо» ≠ «быстро»: разрешимые задачи делятся на дешёвые (P) и, по-видимому, дорогие (NP), и вопрос P = NP до сих пор открыт.
• Всё это протекает в практику: ReDoS, «регуляркой не разобрать HTML», выбор парсера, неразрешимость валидации конфигов и невозможность идеального линтера.

Источники

• Michael Sipser. Introduction to the Theory of Computation — золотой стандарт: автоматы, вычислимость, сложность.
• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation.
• Noam Chomsky. Three models for the description of language (1956) — исток иерархии Хомского.
• Russ Cox. Regular Expression Matching Can Be Simple And Fast — почему настоящие регулярки линейны, а backreferences нет: https://swtch.com/~rsc/regexp/regexp1.html
• Классический ответ про «regex и HTML» на Stack Overflow (как иллюстрация теоремы Клини): https://stackoverflow.com/a/1732454
• Stanford Encyclopedia of Philosophy, The Church–Turing Thesis: https://plato.stanford.edu/entries/church-turing/

Что дальше

Мы увидели, что некоторые вопросы неразрешимы в принципе, а другие — разрешимы, но экспоненциально дороги. Второе, как ни странно, оказывается не проблемой, а фундаментом безопасности: вся современная криптография держится на задачах, которые легко проверить и (предположительно) невозможно быстро решить. Как из этого разрыва вырастают шифрование, аутентификация и защита от угроз — в следующей статье.

Основы безопасности: угрозы, шифрование, аутентификация