Unicode Transliteration Rules Are Turing-Complete

Nicolas Seriot has demonstrated that Unicode's UTS #35 transliteration rules, as implemented in ICU (the International Components for Unicode library), are Turing-complete. The result, published in July 2026, shows that a three-rule file can simulate the Collatz function, and a general compilation from 2-tag systems proves universality. ICU ships these rules as locale data in most operating systems, browsers, runtimes, and databases.

Transliteration Rules: More Than Text Replacement

Transliterators convert characters between scripts, e.g., turning "é" into "e". The rules use ordered rewrites with contexts and a revisiting cursor:

L { x } R > y ;

The substring x is replaced by y when between optional contexts L and R. The | in the replacement moves the cursor inside the new text, enabling further rule application. Example:

x > y | z ;
za > w ;

xa rewrites to y|za (cursor before z), then za matches and produces yw. This revisiting mechanism is key to universality.

Compiling 2-Tag Systems

To prove Turing-completeness, Seriot compiles a 2-tag system (Post, 1943) into transliteration rules. A 2-tag system has one production per letter. Each step removes the first two letters and appends the production of the first. It halts when fewer than two letters remain.

For the Collatz function (even n → n/2, odd n → (3n+1)/2), De Mol's 2-tag system uses: a → bc, b → a, c → aaa, on a unary word aaa...a. The construction prefixes the word with a read marker M and uses one rule per letter:

M a [abc] ([abc]*) > | M $1 b c ;
M b [abc] ([abc]*) > | M $1 a ;
M c [abc] ([abc]*) > | M $1 a a a ;

The character class captures the next letter, and $1 captures the rest. The cursor goes before M so the next step fires immediately. Running this with ICU 78.3 on input aaa reproduces the expected sequence:

% python3 uts35.py collatz.txt aaa
ICU 78.3
0 - Maaa         # 3
1 - Mabc
2 - Mcbc
3 - Mcaaa
4 - Maaaaa       # 5
...
24 - Ma           # 1

Correctness and Universality

At most one rule matches per step. The marker ensures the correct production. Each rewrite corresponds exactly to one tag step. Halting aligns: Ma and M are fixed points when the tag system halts. Since any 2-tag system can be compiled (one rule per letter), a universal 2-tag system yields a fixed rule file that simulates any Turing machine, encoded in the initial word.

ICU's Rewrite Guard

ICU limits each transliterate() call to 16 rewrites per input code point (loopLimit = span << 4 in rbt.cpp; Java port has the same). The specification itself defines no limit—this guard is ICU's pragmatic addition to prevent infinite loops, as termination is undecidable. Seriot's runner iterates until the string stabilizes, bypassing the guard for multi-step simulation.

Beyond Tag Systems: Rule 110 and Prime Numbers

Seriot also implements Rule 110 cellular automaton in 14 rules and Wolfram's prime-generating automaton (223 rules, 16 states). The prime automaton outputs 0 at prime ticks:

% python3 uts35.py primes.txt gggggggggggg0a048
ICU 78.3
0 - Mgggggggggggg0a048
1 - Mgggggggggggs9604d7
...
12 - Mssssssssssss96fad02d700000000

Implications for Developers

Transliteration rules are not just data—they are programs. If you accept transform rules from untrusted sources, you are accepting code that should be reviewed and bounded at runtime, as ICU already does. The specification (UTS #35) doesn't mention this computational power, making it a hidden attack surface in every ICU deployment.

Conclusion

Seriot's work demonstrates that unbounded rewriting with a revisiting cursor is a recipe for universality, buried in a data format for locale files. Developers should treat transliteration rules with the same caution as executable code. The full code and rule files are available on the author's site.