Unicode's transliteration rules are Turing-complete

# Unicode's Transliteration Rules Are Turing-Complete Source: [https://seriot.ch/computation/uts35/](https://seriot.ch/computation/uts35/) ### Nicolas Seriot #### [Computation](https://seriot.ch/computation/)\> Unicode's Transliteration Rules Are Turing\-Complete *July 2026* Hacker News discussion:[https://news\.ycombinator\.com/item?id=48829797](https://news.ycombinator.com/item?id=48829797) See also:[Jira is Turing\-Complete](https://seriot.ch/computation/jira.html) **Table of Contents** 1. [Transliteration Rules](https://seriot.ch/computation/uts35/#1) 2. [2\-Tag Systems](https://seriot.ch/computation/uts35/#2) 3. [The Collatz Function](https://seriot.ch/computation/uts35/#3) 4. [Correctness and Universality](https://seriot.ch/computation/uts35/#4) 5. [ICU's Rewrite Guard](https://seriot.ch/computation/uts35/#5) 6. [Rule 110](https://seriot.ch/computation/uts35/#6) 7. [Prime Numbers](https://seriot.ch/computation/uts35/#7) 8. [Conclusion](https://seriot.ch/computation/uts35/#8) 9. [Appendix: Files](https://seriot.ch/computation/uts35/#9) 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](https://www.unicode.org/reports/tr35/tr35-general.html#Transforms), under their natural unbounded semantics, are not\. This is a result I haven't found published before\. These rules ship as[locale data](https://github.com/unicode-org/cldr/tree/main/common/transforms)in[ICU](https://icu.unicode.org/), 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](https://en.wikipedia.org/wiki/Halting_problem)\. ### 1\. Transliteration Rules A transliterator typically turns "é" into "e", using a list of ordered[rewrite rules](https://www.unicode.org/reports/tr35/tr35-general.html#Conversion_Rules): ``` L { x } R > y ; ``` The substring`x`is replaced by`y`when it sits between \(optional\) contexts`L`and`R`\. The[revisiting](https://www.unicode.org/reports/tr35/tr35-general.html#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](https://pypi.org/project/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](https://github.com/unicode-org/cldr/blob/main/common/transforms/Latin-Katakana.xml#L126-L127)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](https://en.wikipedia.org/wiki/Tag_system)\([Post, 1943](https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/n3/mode/2up)\) into transliteration rules, a model proven universal \([Cocke & Minsky, 1964](https://dl.acm.org/doi/10.1145/321203.321206)\)\. 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](https://doi.org/10.1016/j.tcs.2007.10.020)'s 2\-tag system for the[Collatz](https://en.wikipedia.org/wiki/Collatz_conjecture)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](https://www.unicode.org/reports/tr35/tr35-general.html#Transform_Syntax_Characters)table\)\. You can run this machine with[uts35\.py](https://seriot.ch/computation/uts35/uts35.py)—[collatz\.txt](https://seriot.ch/computation/uts35/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](https://en.wikipedia.org/wiki/Tag_system)page \(`aaa`,`abc`,`cbc`,`caaa`,`aaaaa`, \.\.\.\) with the values appearing as runs of`a`s\. The same rules also run with no Python at all, through ICU's stock`uconv`\([uts35\.sh](https://seriot.ch/computation/uts35/uts35.sh)\)\.[test\.sh](https://seriot.ch/computation/uts35/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 1. **At most one rule matches\.**There is exactly one marker\. The letter after it selects the rule\.`\(\[abc\]\*\)`captures all remaining letters\. 2. **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\. 3. **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](https://github.com/unicode-org/icu/blob/main/icu4c/source/i18n/rbt.cpp); the Java port has the[same guard](https://github.com/unicode-org/icu/blob/main/icu4j/main/translit/src/main/java/com/ibm/icu/text/RuleBasedTransliterator.java)\)\. 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](https://seriot.ch/computation/uts35/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](https://seriot.ch/computation/uts35/primes.txt)is Wolfram's real\-time prime\-generating cellular automaton \(*A New Kind of Science*,[p\. 640](https://www.wolframscience.com/nks/p640--computations-in-cellular-automata/)\); 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](https://seriot.ch/computation/uts35/collatz.txt)— the three\-rule Collatz machine \(one tag step per pass\) - [rule110\.txt](https://seriot.ch/computation/uts35/rule110.txt)— Rule 110 in 14 rules - [primes\.txt](https://seriot.ch/computation/uts35/primes.txt)— Wolfram's prime\-generating cellular automaton in 223 rules - [uts35\.py](https://seriot.ch/computation/uts35/uts35.py)— runner, PyICU - [uts35\.sh](https://seriot.ch/computation/uts35/uts35.sh)— runner, ICU's stock`uconv`, no Python - [test\.sh](https://seriot.ch/computation/uts35/test.sh)— self checks *Environment: ICU 78\.3, PyICU 2\.16\.2, macOS; also verified with ICU 72\.1 on Debian 12; July 2026*