Unicode's Transliteration Rules Are Turing-Complete
Nicolas Seriot
Computation > Unicode's Transliteration Rules Are Turing-Complete
🦄 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 ;<br>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<br>t = T.createFromRules("", "x > y|z; za > w;")<br>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 ;<br>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 ;<br>M b [abc] ([abc]*) > | M $1 a ;<br>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<br>ICU 78.3<br>0 - Maaa # 3<br>1 - Mabc<br>2 - Mcbc<br>3 - Mcaaa<br>4 - Maaaaa # 5<br>5 - Maaabc<br>6 - Mabcbc<br>7 - Mcbcbc<br>8 - Mcbcaaa<br>9 - Mcaaaaaa<br>10 - Maaaaaaaa # 8<br>11 - Maaaaaabc<br>12 - Maaaabcbc<br>13 - Maabcbcbc<br>14 - Mbcbcbcbc<br>15 - Mbcbcbca<br>16 - Mbcbcaa<br>17 - Mbcaaa<br>18 - Maaaa # 4<br>19 - Maabc<br>20 - Mbcbc<br>21 - Mbca<br>22 - Maa # 2<br>23 - Mbc<br>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 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...