July 2026
See also: Jira is Turing-Complete
Table of Contents
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 Unicode library shipped in operating systems, browsers, runtimes, and databases. Whether a given rule file terminates on a given input is undecidable.
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 an excerpt of the Latin-Katakana transform. 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 ;
To prove UTS #35 universality, we compile 2-tag systems (Post, 1943), a model proven universal (Cocke & Minsky, 1964), 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 one. It halts when fewer than two letters remain.
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).
% 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
([abc]*) captures all remaining letters.x matches precisely when the marker faces x plus at least one more letter. The replacement constructs the next configuration.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 with alphabet Σ and productions P:
M x [Σ] ([Σ]*) > | M $1 P(x) ;
A universal 2-tag system therefore yields a fixed rule file that simulates any Turing machine, with the machine and its input encoded in the initial word.
ICU stops each transliterate() call after 16 rewrites per input UTF-16 code unit (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 keep every call bounded. Here, each rewrite is a full tag step, so the guard can only interrupt between steps — calling transliterate() repeatedly until the string stops changing loses nothing. (For these machines an unchanged string means no rule matched; in general a nonhalting system can cycle back to the same string, so equality alone is not a halting test.)
The reduction above establishes universality. The constructions in this section and the next are not part of the main proof; they show the language is comfortably programmable beyond the minimal encoding.
The rule language is not limited to tag systems. 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; each generation consumes one fuel cell g, leaving an s, and the run halts by itself when the fuel is out.
Rule 110 is itself proven universal (Cook, 2004), so the update rule implemented here is, in principle, all the computational power one needs — but this fuel-bounded program runs a prescribed number of generations, so it is a demonstration, not a second proof.
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**.....***.........
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 input word is the fuel followed by the automaton's initial configuration, 0a048. The first cell after the fuel is 0 exactly at prime ticks (t > 1).
% 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
This is a result about computability, not a security disclosure. None of it makes ordinary Unicode text executable: stock ICU caps every transliterate() call at 16 rewrites per code point, so a single call always returns. What is universal here is a custom rule file driven under unbounded re-invocation.
The surface is therefore narrow. Accepting a rule file from an untrusted source is accepting an untrusted program. The risk is nontermination and resource exhaustion. ICU's per-call guard already contains the nontermination, though a single bounded call can still be costly. Reimplementations, however, do not always carry the guard over: ICU4X's experimental Rust transliterator and Twitter's Ruby twitter-cldr both implement the revisiting cursor and iterate with no rewrite bound.
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 one corner of the Unicode specification, whose core algorithms are all deliberately bounded, and which never mentions the possibility.
uconv, no PythonEnvironment: ICU 78.3, PyICU 2.16.2, macOS; also verified with ICU 72.1 on Debian 12; July 2026