Правила транслитерации Unicode оказались тьюринг-полными

Автор задался вопросом, допускает ли Unicode универсальные вычисления. Базовые алгоритмы Unicode, нормализация, приведение регистра, обработка двунаправленного текста (bidi), сортировка (collation), сознательно ограничены и всегда завершаются. Но правила транслитерации из технического стандарта UTS #35, если использовать их штатную, ничем не урезанную семантику, таким свойством не обладают: вопрос, остановится ли конкретный файл правил на конкретном входе, оказывается алгоритмически неразрешимым. По словам автора, этот результат раньше нигде не публиковался. Правила UTS #35, не абстракция: они поставляются как данные локали внутри ICU, широко используемой библиотеки для Unicode и глобализации (интернационализации), которая работает в большинстве операционных систем, браузеров, рантаймов и баз данных.

Обычно транслитератор всего лишь превращает «é» в «e» по упорядоченному списку правил переписывания вида L { x } R > y ;, подстрока x заменяется на y, если стоит между (необязательными) контекстами L и R. Но у формата есть механизм «повторного прохода»: символ | в правой части правила ставит курсор внутрь только что записанного текста, и это позволяет свежезаписанному фрагменту заново запускать другие правила. Игрушечный пример из материала: правила x > y|z; и za > w; превращают строку «xa» сначала в «y|za» (курсор перед z), движок пересматривает результат, находит совпадение «za», и получает «yw». Это не только теоретическая возможность: в реальных production-данных локалей ICU тот же приём уже используется, например, в преобразовании латиница→катакана буква c перед i или e заменяется на s, а курсор откатывается назад, чтобы заново сработали правила для s.

Чтобы доказать полноту по Тьюрингу, автор компилирует в правила транслитерации так называемую 2-тег-систему (Post, 1943), модель вычислений, доказанно универсальную (Cocke & Minsky, 1964). В 2-тег-системе на каждую букву алфавита приходится одно правило-продукция; на каждом шаге у слова удаляются первые две буквы, а к его концу дописывается продукция первой из удалённых букв; система останавливается, когда в слове остаётся меньше двух букв. В качестве примера взята 2-тег-система Лисбет Де Мол (Liesbeth De Mol), вычисляющая функцию Коллатца (для чётного n, n/2, для нечётного, (3n+1)/2): продукции a→bc, b→a, c→aaa на слове в унарной записи. Слово дополнительно снабжено маркером-«считывателем» M, который жёстко привязывает точку работы машины к началу строки: если у маркера не находится подходящего правила, не находится ни одного правила вообще. Вся конструкция укладывается всего в три правила транслитерации, по одному на каждую из букв a, b, c.

Автор запускает эту машину собственным скриптом uts35.py с файлом правил collatz.txt на входном слове «aaa» (унарная запись числа 3) и получает пошаговую трассировку, которая в точности воспроизводит хрестоматийный пример вычисления функции Коллатца для 2-тег-систем из Википедии: последовательность значений 3, 5, 8, 4, 2, 1 (в виде числа повторов буквы a). Те же самые правила запускаются и вовсе без Python, напрямую через штатную консольную утилиту ICU uconv (скрипт uts35.sh), а корректность проверяется скриптом test.sh, сверяющим вывод с ожидаемыми результатами. По индукции доказывается: после k шагов переписывания строка в точности равна M плюс слово тег-системы после k шагов, а сам транслитератор достигает неподвижной точки (перестаёт меняться) ровно тогда, когда останавливается тег-система. Демонстрация не привязана конкретно к функции Коллатца, по одному правилу на букву можно скомпилировать любую 2-тег-систему, а значит, зашив в правила универсальную 2-тег-систему, можно получить единственный фиксированный файл правил транслитерации, способный эмулировать произвольную машину Тьюринга.

Отдельно разобран практический нюанс: сама ICU ограничивает каждый вызов функции transliterate() 16 проходами переписывания на входной кодпоинт (константа loopLimit = span << 4 в файле rbt.cpp; в Java-порте библиотеки, тот же лимит). Но сам стандарт UTS #35 никакого предела не устанавливает, это ограничение ICU ввела сама, из практических соображений, именно потому что остановка неразрешима в общем случае. В построенной автором конструкции каждый проход переписывания, это ровно один шаг тег-системы, поэтому многократный вызов transliterate() подряд, пока строка не стабилизируется, беспрепятственно обходит защитный лимит одного вызова.

Построенный «раннер» не ограничен тег-системами, любой файл правил является программой. Файл rule110.txt в 14 правилах реализует клеточный автомат «Правило 110» (клетки обозначены символами «.», ноль и «*», единица; «голова» хранит два предыдущих значения клетки и переписывает каждую клетку на месте; один проход правил, одно поколение автомата; вычисление ограничено счётчиком «топлива» на поколение и останавливается само, когда топливо заканчивается). Ещё один файл, primes.txt, воспроизводит клеточный автомат Вольфрама (Stephen Wolfram) для генерации простых чисел в реальном времени из книги «A New Kind of Science» (стр. 640): 16 состояний (0, f) и 223 правила преобразования; первая клетка после «топлива» равна нулю ровно в те такты, которые соответствуют простым числам. Автор приводит трассировки вывода для обоих примеров, полученные тем же движком ICU 78.3.

Вывод автора: правила транслитерации создавались для задач вроде превращения «é» в «e», но всего трёх строк таких правил достаточно, чтобы вычислить функцию Коллатца. Сама идея, неограниченное переписывание с курсором повторного прохода как рецепт универсальности, не нова, но неожиданно то, что она обнаруживается в формате данных для файлов локализации, который поставляется в составе практически любой операционной системы, а его собственная спецификация даже не упоминает такую возможность. Отсюда прямой вывод для безопасности: файл правил транслитерации, это не просто данные, а программа. Если система принимает правила преобразования текста откуда-то извне, она тем самым принимает исполняемый код, который следует проверять и ограничивать во время выполнения, как это уже делает сама ICU.

Результаты автор проверил в двух окружениях: ICU 78.3 с PyICU 2.16.2 на macOS, а также отдельно на ICU 72.1 в Debian 12 (материал датирован июлем 2026 года). На Hacker News пост набрал 62 голоса и 21 комментарий; автор также ссылается на смежный по духу более ранний материал о тьюринг-полноте Jira («Jira is Turing-Complete») как на пример подобных находок.

Ключевые факты

• Правила транслитерации Unicode (UTS #35) в библиотеке ICU оказались тьюринг-полными и алгоритмически неразрешимыми по остановке, в отличие от других базовых алгоритмов Unicode (нормализация, регистр, bidi, коллация), которые заведомо ограничены и всегда завершаются.
• Доказательство, компиляция доказанно универсальной (Cocke & Minsky, 1964) 2-тег-системы Поста (1943) всего в три правила транслитерации, реализующие 2-тег-систему Лисбет Де Мол для функции Коллатца на числе в унарной записи.
• Автор запустил конструкцию на входе «aaa» (число 3) и получил трассировку 3→5→8→4→2→1, совпадающую с эталонным примером; те же правила работают и без Python, напрямую через штатную утилиту ICU uconv, а проверяются отдельным скриптом test.sh.
• Сама ICU ограничивает один вызов transliterate() 16 проходами на кодпоинт (константа loopLimit в rbt.cpp), но это ограничение, решение самой ICU, а не требование спецификации UTS #35; повторные вызовы этот лимит обходят, поскольку каждый проход, ровно один шаг вычисления.
• Тем же движком автор реализовал клеточный автомат «Правило 110» и генератор простых чисел Вольфрама из «A New Kind of Science», и делает вывод для безопасности: файл правил транслитерации, это исполняемый код, а не просто данные, и принимать такие правила извне нужно с той же осторожностью, что и любой чужой код.

Почему это важно

Находка переворачивает интуицию: правила транслитерации в Unicode задумывались как простой механизм замены символов (например, снять диакритику, «é» → «e»), а соседние базовые алгоритмы Unicode вроде нормализации или сортировки строго ограничены и всегда завершаются. Автор показывает, что у транслитератора, если использовать его штатную, ничем не урезанную семантику (в частности, механизм «повторного прохода» с курсором |), скрыт статус полноценного языка программирования: вопрос об остановке конкретного файла правил на конкретном входе алгоритмически неразрешим, а значит правила можно заставить эмулировать что угодно, вплоть до клеточного автомата и функции Коллатца. Это не абстрактная теория: правила UTS #35 поставляются как данные локали внутри ICU, библиотеки для Unicode и глобализации, используемой в большинстве операционных систем, браузеров, рантаймов и баз данных, а сам автор утверждает, что раньше нигде не встречал этот результат опубликованным.

Кому это важно

Прежде всего, самой ICU и сопровождающим спецификацию UTS #35: сейчас она никак не оговаривает возможность неограниченных вычислений внутри «простого» формата данных локали. Дальше, разработчикам операционных систем, браузеров, рантаймов языков программирования и баз данных, которые используют ICU для интернационализации и где-либо в своём коде допускают загрузку кастомных правил транслитерации, в том числе от пользователя или из внешнего источника. Наконец, специалистам по безопасности и всем, кто оценивает риски работы с «просто данными» конфигурации: находка, конкретный пример того, как безобидный на вид формат конфигурации оказывается полноценным исполняемым кодом.

Как это применить

Автор выложил рабочий, воспроизводимый код: uts35.py, раннер на Python/PyICU, файлы правил collatz.txt (функция Коллатца через 2-тег-систему), rule110.txt (клеточный автомат «Правило 110», 14 правил) и primes.txt (генератор простых чисел Вольфрама, 16 состояний и 223 правила), а также uts35.sh, версия без единой строчки Python, через штатную консольную утилиту ICU uconv, и test.sh, скрипт проверки вывода. Практический вывод для инженеров: если система хоть где-то принимает правила транслитерации или трансформации текста из внешнего источника (от пользователя, из конфигурации, из плагина), к ним стоит относиться как к исполняемому коду, просматривать перед использованием и ограничивать во время выполнения, а не доверять как обычным настроечным данным; штатный лимит ICU в 16 проходов на кодпоинт, это подсказка о самой угрозе, а не полноценная защита, поскольку он не мешает выполнить сколь угодно много шагов через повторные вызовы.

Можно ли доверять

Это не спекуляция, а конструктивное доказательство: автор берёт модель вычислений, тег-систему Поста (1943), чья универсальность строго доказана (Cocke & Minsky, 1964), и явно компилирует её в три правила транслитерации, а затем запускает получившуюся машину на реальном, действующем ПО, ICU версии 78.3 с PyICU 2.16.2 на macOS, и отдельно перепроверяет результат на ICU 72.1 в Debian 12. Важно, что конструкция работает не только через Python-обвязку, но и через штатную консольную утилиту uconv, которая идёт в комплекте с самой ICU, то есть это свойство самого движка и, как утверждает автор, самой спецификации (она предела не задаёт), а не побочный эффект конкретной библиотеки-обёртки. Выходные трассировки для всех трёх примеров (функция Коллатца, «Правило 110», генератор простых чисел) совпадают с ожидаемыми, эталонными последовательностями, что служит проверяемым подтверждением. При этом сама публикация, личный технический блог-пост, а не рецензируемая статья; формальной внешней экспертизы результата в тексте не упомянуто.

Риски и подводные камни

Главный практический риск, в безопасности: раз остановка файла правил формально неразрешима, специально построенный файл транслитерации можно использовать для отказа в обслуживании (зависание или чрезмерно долгое вычисление) там, где система принимает такие правила из непроверенного источника. Штатный лимит ICU (16 проходов переписывания на кодпоинт за один вызов) риск снижает лишь частично: он не установлен самой спецификацией UTS #35, действует только на один вызов transliterate() и, как показывает автор, обходится, если вызывать функцию повторно, пока строка не стабилизируется. С другой стороны, стоит понимать масштаб: находка носит по большей части фундаментальный, теоретический характер, в тексте нет ни готового эксплойта, ни номера уязвимости (CVE), ни описания конкретного взломанного продукта; реальная опасность зависит от того, насколько часто где-либо в экосистеме ICU (в операционных системах, браузерах, рантаймах, базах данных) внешние правила транслитерации в принципе принимаются без проверки.

«Правила транслитерации создавались, чтобы превращать «é» в «e». Три строки таких правил способны вычислить функцию Коллатца.»

— автор материала на seriot.ch