Unicode's Transliteration Rules Are Turing-Complete

Nicolas Seriot Computation > Unicode's Transliteration Rules Are Turing-Complete

July 2026 See also: Jira is Turing-Complete Table of Contents

Transliteration Rules 2-Tag Systems The Collatz Function Correctness and Universality ICU's Rewrite Guard Rule 110 Prime Numbers Conclusion Appendix: Files

I've been wondering for a while whether Unicode allows universal computation. The core Unicode algorithms (normalization, casing, bidi, collation) are deliberately bounded, but UTS #35 transliteration rules, under their natural unbounded semantics, are not. This is a result I haven't found published before. These rules ship as locale data in ICU, the widely used Unicode/globalization library used in most operating systems, browsers, runtimes, and databases. Whether a given rule file terminates on a given input is undecidable. 1. Transliteration Rules A transliterator typically turns "é" into "e", using a list of ordered rewrite rules: L { x } R > y ;

The substring x is replaced by y when it sits between (optional) contexts L and R. The revisiting feature allows | in the replacement, which places the cursor inside the new text so that newly written material can trigger further rules. Example: x > y | z ; za > w ;

xa rewrites to y|za (cursor before z). The engine rescans and za matches, producing yw. Using the Python PyICU module: from icu import Transliterator as T t = T.createFromRules("", "x > y|z; za > w;") print(t.transliterate("xa")) # yw

Here is the Latin-Katakana transform. It uses contexts, capture groups, quantifiers and the cursor. Before i or e, c rewrites to s and the cursor backs up so the s rules re-fire. Same revisiting trick as above, shipped in production locale data. c } i → | s ; c } e → | s ;

2. 2-Tag Systems To prove UTS #35 universality, we compile a 2-tag system (Post, 1943) into transliteration rules, a model proven universal (Cocke & Minsky, 1964).

A 2-tag system has one production per letter. Each step removes the first two letters and appends the production of the first one. It halts when fewer than two letters remain. 3. The Collatz Function Our example is Liesbeth De Mol's 2-tag system for the Collatz function (even n → n/2, odd n → (3n+1)/2): a → bc, b → a, c → aaa, on the unary word aaa...a. We prefix the word with a read marker M, which pins the machine to the front. When no rule matches at M, no rule matches anywhere. The construction 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 first rule matches the marker, the letter a, one more letter, then captures everything else. The replacement writes the next configuration and puts the cursor back before the marker so the next step fires immediately.

The character class, the capturing group and $1, the quantifier and the cursor are standard rule syntax (the spec's Transform Syntax Characters table). You can run this machine with uts35.py — collatz.txt is the rules above with the | deleted, so each pass performs exactly one tag step. From aaa, the run replicates the worked example on the Wikipedia tag system page (aaa, abc, cbc, caaa, aaaaa, ...) with the values appearing as runs of as. The same rules also run with no Python at all, through ICU's stock uconv (uts35.sh). test.sh checks the machine against expected outputs. % python3 uts35.py collatz.txt aaa ICU 78.3 0 - Maaa # 3 1 - Mabc 2 - Mcbc 3 - Mcaaa 4 - Maaaaa # 5 5 - Maaabc 6 - Mabcbc 7 - Mcbcbc 8 - Mcbcaaa 9 - Mcaaaaaa

10 - Maaaaaaaa # 8 11 - Maaaaaabc 12 - Maaaabcbc 13 - Maabcbcbc 14 - Mbcbcbcbc 15 - Mbcbcbca 16 - Mbcbcaa 17 - Mbcaaa 18 - Maaaa # 4 19 - Maabc 20 - Mbcbc 21 - Mbca 22 - Maa # 2 23 - Mbc 24 - Ma # 1

4. Correctness and Universality

At most one rule matches. There is exactly one marker. The letter after it selects the rule. ([abc]*) captures all remaining letters. One rewrite is exactly one tag step. The rule for letter x matches precisely when the marker faces x plus at least one more letter. The replacement constructs the next configuration. Halting corresponds. Every rule requires two letters after the marker, so Ma and M are fixed points. The transform terminates exactly when the tag system halts.

Together, by induction: after k rewrites the string is exactly M followed by the tag system's word after k steps, and the transform reaches a fixed point exactly when the tag system halts. Nothing here is specific to Collatz. One rule per letter compiles any 2-tag system, so a universal one yields a fixed rule file that simulates any Turing machine, encoded in the initial word. 5. ICU's Rewrite Guard ICU stops each transliterate() call after 16 rewrites per input code point (loopLimit = span << 4 in rbt.cpp; the Java port has the same guard). However, the specification itself defines no limit. The guard is ICU's pragmatic addition to prevent infinite computation, as termination is undecidable. Here, each rewrite performs a full tag step, so iterating until the string stabilizes is safe. 6. Rule 110 The runner is not limited to tag systems. Any rule file is a program. rule110.txt implements the Rule 110 cellular automaton in 14 rules. Cells are written . (0) and * (1). A head carries the previous two cells and rewrites each cell in place.

One pass is one generation. One fuel g per generation, spent into s; the run halts by itself when the fuel is out. python3 uts35.py rule110.txt "ggggggggg*" ICU 78.3 0 - Mggggggggg* 1 - Mggggggggs**. 2 - Mgggggggss***.. 3 - Mggggggsss**.*... 4 - Mgggggssss*****.... 5 - Mggggsssss**...*..... 6 - Mgggssssss***..**...... 7 - Mggsssssss**.*.***....... 8 - Mgssssssss*******.*........ 9 - Msssssssss**.....***.........

7. Prime Numbers primes.txt is Wolfram's real-time prime-generating cellular automaton (A New Kind of Science, p. 640); 16 states (0-f) and 223 transform rules. The first cell after the fuel is 0 exactly at prime ticks. % python3 uts35.py primes.txt gggggggggggg0a048 ICU 78.3 0 - Mgggggggggggg0a048 1 - Mgggggggggggs9604d7 2 - Mggggggggggss06f5d80 3 - Mgggggggggsss0ad3d870 4 - Mggggggggssss96fc0d700 5 - Mgggggggsssss0adb008000 6 - Mggggggssssss96fad087000 7 - Mgggggsssssss0a960f870000 8 - Mggggssssssss9af6f01700000 9 - Mgggsssssssss9adad018000000

10 - Mggssssssssss96f60f187000000 11 - Mgsssssssssss0a06f02870000000 12 - Mssssssssssss96fad02d700000000

8. Conclusion Transliteration rules were designed to turn "é" into "e". Three lines of them can compute the Collatz function. Unbounded rewriting with a revisiting cursor is an old recipe for universality. The surprise is that it lives in a data format for locale files, shipped in every OS, whose specification doesn't mention the possibility. The above discussion demonstrates that a transliteration rule file is not just data, it's a program. If you accept transform rules from outside, you are accepting code, which should be reviewed and bound at runtime, as ICU already does. Appendix: Files

collatz.txt — the three-rule Collatz machine (one tag step per pass) rule110.txt — Rule 110 in 14 rules primes.txt — Wolfram's prime-generating cellular automaton in 223 rules uts35.py — runner, PyICU uts35.sh — runner, ICU's stock uconv, no Python test.sh — self checks

Environment: ICU 78.3, PyICU 2.16.2, macOS; also verified with ICU 72.1 on Debian 12; July 2026