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
xmatches precisely when the marker facesxplus at least one more letter. The replacement constructs the next configuration. - Halting corresponds. Every rule requires two letters after the marker, so
MaandMare 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