Тьюринг-полнота и выразительность: чему учит brainfuck

Любой алгоритм, который вычисляет Python, вычисляет и brainfuck. По вычислительной мощности — по классу функций, которые они способны посчитать, — эти два языка неотличимы: оба покрывают ровно вычислимые по Тьюрингу функции, ни одной больше, ни одной меньше. Оговорка одна и честная: речь о чистом вычислении, а не о Python как среде — файлы, сеть, время, сторонние библиотеки к вопросу о мощности не относятся. И вот при равной мощности на brainfuck не пишут ничего сложнее «Hello, world», а «Hello, world» на нём — сотня символов нечитаемого месива.

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

В статье

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

Что такое brainfuck

Урбан Мюллер придумал brainfuck в 1993 году с одной инженерной целью: сделать язык, компилятор которого будет как можно меньше (его первый компилятор занимал чуть больше двухсот байт). Получилась машина с лентой байтовых ячеек, указателем на текущую ячейку и восемью командами:

команда	что делает
> <	сдвинуть указатель вправо / влево
+ -	увеличить / уменьшить текущую ячейку на 1
. ,	вывести ячейку / прочитать байт в ячейку
[ ]	цикл: [ прыгает за ], если ячейка равна нулю; ] прыгает обратно на [, если не ноль

Всё. Ни имён, ни чисел-литералов, ни функций, ни типов. Чтобы получить в ячейке число 72 (код H), его набивают восемью-девятью плюсами в цикле-умножении. Программа «сложить два введённых числа и вывести результат» — это уже головоломка на десяток минут.

Важно не спутать минимализм с поломанностью. Brainfuck не «сломанный язык» — он намеренно минимальный. И именно минимальность делает его интересным теоретически.

Тьюринг-полнота — это ровно вот это

Тьюринг-полнота — свойство системы вычислять всё, что вычислимо в принципе (формально — всё, что вычисляет машина Тьюринга). Звучит внушительно, но требований у неё до обидного мало:

1. Неограниченная память — лента, которую можно наращивать сколько нужно.
2. Последовательное выполнение — команды идут одна за другой.
3. Условное повторение — возможность зациклиться в зависимости от данных.

Сопоставьте с brainfuck: лента ячеек (память), команды подряд (последовательность), [ ... ] — цикл, пока ячейка не ноль (условное повторение). Это и есть машина Тьюринга, чуть переодетая. Удивительно тут не то, что brainfuck тьюринг-полон, а как мало для этого понадобилось: инкремент, декремент, сдвиг и один условный переход по нулю.

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

Обратная сторона: brainfuck как универсальная мишень

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

• одна инструкция x86 mov — «mov is Turing-complete» Стивена Долана, а компилятор movfuscator переводит Си в поток из одних mov;
• система типов C++ (шаблоны) (Велдхьюзен, 2003) и TypeScript (полнота показана на демонстрации в issue #14833);
• Magic: The Gathering — колодой и правилами кодируется машина Тьюринга (Churchill, Biderman, Herrick, FUN 2021);
• клеточный автомат «Жизнь» Конвея — в нём собрана универсальная машина Тьюринга (Ренделл);
• формулы Excel — после LAMBDA (2021) в них можно писать рекурсию, и язык формул стал тьюринг-полным (Microsoft Research).

Это не курьёзы ради курьёзов. Каждый такой факт означает: система, которую проектировали как «описание данных» или «набор правил», на деле умеет исполнять произвольные программы. А у произвольных программ есть свойство, которое ниже окажется главным.

Мощность — это не выразительность

Вернёмся к исходному парадоксу. Brainfuck по мощности равен Python — и совершенно непригоден для работы. Значит, пригодность даёт не мощность. Что тогда?

Ответ: выразительность — способность языка называть вещи и переиспользовать их. У brainfuck её нет вовсе. Нет имён переменных — есть безымянные ячейки, которые надо держать в голове по номерам. Нет функций — любую повторяющуюся логику набиваешь заново. Нет типов, нет абстракций. Даже элементарные операции превращаются в идиомы, которые приходится узнавать в лицо: [-] — «обнулить ячейку», [->+<] — «переложить значение в соседнюю». Код не называет эти операции — их опознаёт только тот, кто уже знает.

Тут легко ошибиться и решить, что дело в длине: раз выразительности нет, код должен раздуваться. Стенд к статье это проверил и опроверг. Сложить два байта на brainfuck — это ,>,[-<+>]<., одиннадцать символов; идиоматичный Go с чтением и обработкой ошибок — вчетверо длиннее. На арифметике brainfuck выходит короче. Разрыв не в длине — он в том, что в этих одиннадцати символах ноль имён: не «сложить a и b», а «занулить соседа, перекладывая единицы», и прочитать их можно, только исполнив в голове. Коротко не значит понятно.

И вот ключевой поворот. Вычислимость Тьюринг закрыл ещё в 1936 году: что можно посчитать, а что нельзя, — вопрос решённый и от языка не зависящий. Всё, что языки программирования изобретали последующие девяносто лет, — переменные, функции, типы, модули, объекты, дженерики — не добавляло мощности ни на йоту. Оно добавляло выразительности: возможности назвать намерение, спрятать деталь, собрать сложное из простого. Язык нужен не чтобы посчитать — считать умеет и лента с инкрементом, — а чтобы сделать интересное лёгким.

Алан Перлис в 1982 году сформулировал это афоризмом, который с тех пор так и зовут — тьюрингова трясина (Turing tarpit): «everything is possible but nothing of interest is easy» (всё возможно, но ничего интересного не даётся легко). Brainfuck — предельная точка этой трясины: возможно в нём действительно всё, а легко — ничего.

Почему это должно волновать инженера

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

Причина — в фундаментальном ограничении. Как только язык становится тьюринг-полным, про программы на нём в общем случае перестаёт быть разрешимой практически любая содержательная проверка. Остановится ли программа? — неразрешимо (проблема остановки, Тьюринг, 1936). Любое ли нетривиальное свойство её поведения? — неразрешимо (теорема Райса). Речь именно об общем случае: конкретную программу разобрать может и удастся, невозможно — ручательство сразу за все.

Отсюда — вполне заземлённые следствия:

• Конфиги и форматы данных. Если язык конфигурации тьюринг-полон, о нём в общем случае нельзя статически гарантировать нетривиальные свойства — завершится ли обработка, эквивалентны ли два конфига, во что развернётся любой из них. Конкретный конфиг вы, конечно, вычислите и получите результат; невозможно именно общее ручательство. Это случай Nix: его язык выражений тьюринг-полон, и вычисление конфигурации может не завершиться в принципе. Другие языки идут противоположным путём намеренно: Dhall гарантированно завершается (он не тьюринг-полон by design), а Starlark в Bazel запрещает рекурсию и допускает только циклы по конечным структурам — чтобы сборку можно было анализировать и воспроизводить. Для конфига неумение зациклиться — не ущербность, а гарантия: невозможность вычислить здесь и есть фича.
• Системы типов. Тьюринг-полные типы (шаблоны C++, типы TypeScript, имплиситы Scala) означают, что проверка типов в пределе неразрешима, а компилятор в принципе может зависнуть на корректной программе.
• Безопасность. Тьюринг-полный вход — это вход, который нельзя проанализировать до конца. Language-theoretic security (LangSec) строится ровно на этом наблюдении: парсер сложного формата — это де-факто интерпретатор, а вредонос — программа для него («странные машины», weird machines). Чем выразительнее формат, который вы принимаете снаружи, тем ближе он к тьюринг-полноте и тем меньше вы способны о нём доказать.

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

Стенд

Стенд lang/brainfuck заземляет главный тезис — про разрыв выразительности — в измерение, а первый показывает вживую интерпретатором. Тьюринг-полноту brainfuck он не измеряет и не доказывает: он даёт универсальную машину для этой модели и меряет цену её мощности.

Интерпретатор brainfuck на Go, около ста десяти строк: лента, указатель, восемь команд, парные скобки просчитаны заранее для прыжков за O(1). Это универсальная машина размером с один экран: одна программа исполняет любой brainfuck. Тьюринг-полнота самого brainfuck — отдельный результат (в его команды сводится машина Тьюринга); стенд на него опирается, а не доказывает его — он показывает универсальную машину для этой модели вживую.

Замер разрыва выразительности. Каждая задача решена дважды — на brainfuck и на Go, — и тест прогоняет обе на одном входе, сверяя вывод: пока он совпадает, версии эквивалентны по вычислению, и сравнивать их честно. Числа не вписаны руками — команды brainfuck считаются по программе, а размер и «именованность» Go меряются парсером прямо по исходнику, так что замеряется ровно тот код, что исполнялся:

задача	bf-команд	Go-символов	bf / Go	Go имён	bf имён
эхо ввода (cat)	5	30	0.17	9	0
удвоить байт (a → 2a)	10	100	0.10	13	0
сложить два байта (a,b → a+b)	11	107	0.10	13	0
напечатать «Hello World!\n»	106	51	2.08	8	0

Таблица опровергает напрашивающееся «brainfuck многословен»: на трёх задачах из четырёх он короче Go — тому нужны строки на обработку ошибок и работу с байтами. Раздувается brainfuck только на «Hello World», и по частной причине: строку-константу в нём собирают арифметикой байтов, а не пишут литералом. Разрыв — не в столбце длины, а в последнем. Столбец «имён» — грубый прокси: он считает все идентификаторы в Go-функции, включая служебные (err, ReadFull, Write), так что абсолютное число тут ни о чём не говорит. Говорит контраст: у Go имена есть — восемь ли, тринадцать, — а у brainfuck их ноль во всех строках, и не по бедности примера, а потому что назвать в нём нечем: ни ячейку, ни операцию. Это и есть та выразительность, которой brainfuck лишён по устройству, — огрублённая до одной колонки.

Первоисточники

• Alan Turing, «On Computable Numbers…» (1936) — определение вычислимости и проблема остановки.
• Оригинальное описание brainfuck на esolangs.
• Alan Perlis, «Epigrams on Programming» (1982) — тьюрингова трясина.
• Теорема Райса — неразрешимость нетривиальных свойств программ.
• Stephen Dolan, «mov is Turing-complete» + movfuscator К. Домаса — полнота одной инструкции mov.
• Churchill, Biderman, Herrick, «Magic: The Gathering is Turing Complete» (FUN 2021).
• Dhall (total, не тьюринг-полон by design) и Starlark (без рекурсии) — конфиг-языки, намеренно отказавшиеся от полноты.
• LangSec — language-theoretic security и «странные машины».

Смежное на сайте: «Дженерики, шаблоны, erasure»готовится, с 15 сентября — выразительность как отдельная ось и тьюринг-полные шаблоны C++; «Secure coding: инъекции»Скоро — тот же LangSec-принцип «данные против кода» с практической стороны; «Тестирование в разных языках» — из той же серии сравнений между языками.