Правила транслитерации Unicode (UTS #35) оказались тьюринг-полными. Это неочевидный факт: основные алгоритмы Unicode (нормализация, регистр, bidi, коллация) заведомо ограничены, но транслитерация с естественной неограниченной семантикой — нет. Такой результат раньше не публиковали. Эти правила живут в ICU — библиотеке интернационализации, встроенной почти во все ОС, браузеры, рантаймы и базы данных.
Транслитератор обычно превращает «é» в «e» через упорядоченные правила вида L { x } R > y — подстрока x заменяется на y, когда она стоит между контекстами L и R. Ключевая фича — курсор | в замене: он возвращает позицию внутрь нового текста, чтобы дополнительные правила сработали повторно. Пример: правило x > y | z превращает xa → y|za, затем za → w, итог — yw. В ICU это легко проверить через PyICU.
Чтобы доказать универсальность, автор компилирует 2-тег-систему (Пост, 1943) — модель, которая, как известно, может симулировать любую машину Тьюринга. Берётся система Лизбет де Мол для функции Коллатца: a→bc, b→a, c→aaa, на слове из букв a. В начало ставится маркер M. Правила для каждой буквы: M a [abc] ([abc]*) > | M $1 b c — захватывают маркер, первую букву, ещё одну, и всё остальное в группу. Замена пишет следующую конфигурацию, а курсор возвращается перед маркером, запуская следующий шаг. Классы символов, квантификаторы, захват и $1 — всё стандартный синтаксис.
Запуск через uts35.py или ICU-утилиту uconv даёт точную последовательность шагов тег-системы. Проверка: Maaa → Mabc → Mcbc → Mcaaa → … вплоть до финального Ma — остановка. Корректность доказывается по индукции: после k перезаписей строка равна маркеру плюс слово тег-системы. Ничего специфичного для Коллатца — одна пара правил на каждую букву позволяет скомпилировать любую 2-тег-систему, а значит и любую машину Тьюринга.
В ICU есть защита: каждый вызов transliterate() ограничен 16 перезаписями на входной кодпоинт (loopLimit = span << 4). Спецификация такого лимита не задаёт — это прагматичное решение, ведь завершение неразрешимо. Для тег-систем достаточно итераций, пока строка не стабилизируется.
Этим же подходом можно запускать Rule 110 (14 правил) и даже клеточный автомат Вольфрама для генерации простых чисел (223 правила, 16 состояний). Например, primes.txt ставит 0 на тактах, соответствующих простым числам.
Вывод: файл правил транслитерации — не просто данные, а программа. Если вы принимаете правила извне, вы принимаете код, который нужно проверять и ограничивать на уровне runtime — как это уже делает ICU.