The string you validated no longer exists

Three transliteration rules compute the Collatz function. That is the result at the center of a July 2026 analysis of UTS #35, the Unicode spec that defines how locale data rewrites text. Starting from the unary word aaa, ICU’s stock uconv steps through Maaa, Mabc, Mcbc, Mcaaa, Maaaaa, and on down, with each Collatz value showing up as a run of as. No Python and no custom engine, just rewrite rules and the library that already ships in your operating system, browser, runtime, and database.

The claim underneath is stronger. As specified, the UTS #35 transliteration-rule language is Turing-complete. That is an odd place to find universal computation. Unicode’s core algorithms (normalization, casing, bidi, collation) are deliberately bounded and always terminate. Transliteration is the exception the spec never flags, and whether a given rule file halts on a given input is undecidable.

A transliterator turns “é” into “e” with ordered rewrite rules. The form is L { x } R > y ;, meaning replace x with y when it sits between optional contexts L and R. Its whole job is to replace one string with another, so whatever you validated on the way in is gone by the time the rules finish.

The feature that makes it universal is the revisiting cursor. A | in the replacement drops the cursor back inside the text you just wrote, so freshly written material can trigger more rules. With x > y | z ; and za > w ;, the input xa rewrites to y|za with the cursor before z, the engine rescans, za matches, and you get yw. This is not an obscure corner feature. The Latin-Katakana transform ships the same move: before i or e, c rewrites to s and the cursor backs up so the s rules re-fire. The revisiting cursor runs in production locale data.

From there the proof is short. 2-tag systems are universal (Post 1943; Cocke and Minsky 1964), so compiling one into rules is enough. Liesbeth De Mol’s 2-tag system for Collatz is a → bc, b → a, c → aaa, run on a unary word prefixed with a read marker M. 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 ;

Each rule matches the marker, the letter it fires on, one more letter, then captures everything left over. The replacement writes the next configuration and puts the cursor back before the marker so the next step fires at once. Character classes, the capturing group and $1, the quantifier, and the cursor are all standard syntax from the spec’s Transform Syntax Characters table.

Three properties make it a proof rather than a demo. At most one rule matches, because there is one marker and the letter after it selects the rule. One rewrite is exactly one tag step. Halting corresponds, since every rule needs two letters after the marker, so Ma and M are fixed points and the transform terminates exactly when the tag system does. None of it is specific to Collatz: M x [Σ] ([Σ]*) > | M $1 P(x) ; compiles any 2-tag system, and a universal one gives you a fixed rule file that simulates any Turing machine with the program encoded in the starting word.

The analysis carries it past the minimum. Rule 110, itself universal (Cook 2004), fits in 14 rules. Wolfram’s prime-generating cellular automaton (A New Kind of Science, p. 640) takes 16 states and 223 rules, with the first cell after the fuel reading 0 exactly on prime ticks.

For anyone operating these systems, this is a computability result and not a disclosure. Ordinary text does not become executable. Stock ICU caps every transliterate() call at 16 rewrites per input UTF-16 code unit (loopLimit = span << 4 in rbt.cpp, and the Java port carries the same guard), so a single call always returns. The universality needs a custom rule file driven under repeated invocation. In the Collatz machine each rewrite is one full tag step, so the per-call guard only ever interrupts between steps, and looping transliterate() until the string stops changing loses nothing.

The exposed surface is narrow but real. Accepting a rule file from an untrusted source is accepting an untrusted program, and the failure mode is nontermination and resource exhaustion. ICU’s per-call guard contains the nontermination, though one bounded call can still be costly. That guard is ICU’s own addition; the specification sets no limit. Reimplementations that follow the spec do not all copy it. ICU4X’s experimental Rust transliterator and Twitter’s Ruby twitter-cldr both implement the revisiting cursor and iterate with no rewrite bound.

So if you consume transliteration rule files from anywhere you do not control, treat them as code, cap the iteration yourself, and do not lean on a change-detection loop as a halting test. A nonhalting rule set can cycle back to a string it already produced, so equality between passes does not prove it is done. And if you depend on a non-ICU implementation, check whether it bounds the rewrite loop at all before you feed it anything you did not write.