Researcher shows Unicode's UTS #35 transliteration rules are Turing complete, computes Collatz in stock ICU
- Nicolas Seriot proves that UTS #35 transliteration rules, the rewrite rule language used for Unicode transliteration, are Turing complete under their natural unbounded semantics.
- The proof compiles a 2-tag system (Post, 1943, proven universal by Cocke and Minsky in 1964) into just 3 transliteration rules that compute the Collatz function on a unary string of 'a's.
- The demo runs unmodified through PyICU and also through stock ICU's uconv command line tool with no Python involved, using files like collatz.txt and uts35.sh.
- Since whether a given UTS #35 rule file halts on a given input is undecidable (the halting problem), custom rule sets could in principle loop forever, though shipped transliterators like Latin-Katakana are designed to always terminate and ICU caps rewrite counts in practice.
- ICU, the library implementing these rules, ships inside most operating systems, browsers, runtimes, and databases as locale data, making this an obscure but widespread Turing-complete subsystem.
Hacker News opinions
I've been wondering for a while if anything in Unicode could accidentally compute, turns out UTS #35 transliteration rules are Turing complete, showed Collatz with just 3 rewrite rules on stock ICU.
Waiting for someone to vibe a compiler targeting Unicode transliteration rules at this point lol.
This reminds me of Word's autocorrect being turing complete, there's a fun video about it.
Honestly it feels harder these days to design a format that CAN'T compute than one that can.
Who actually implements these transliteration rules, is it the OS or text renderers? Someone answered: it's the ICU library, so ubiquitous you can barely avoid it if you touch human text.
Does the Latin-Katakana example mean some input could make it not terminate? Answer: no, standard transliterators are designed to terminate, ICU also caps the number of rewrites even though the spec doesn't require it.
Could I post untransliterated text in a comment and make your browser run these computations? Someone tested with Japanese text and said most browsers don't auto-transliterate arbitrary text like that, and even Lynx uses iconv not UTS #35 rules.
Also reminds me of the PowerPoint Turing Machine video.
An AI-generated wall of text argued this shows text infrastructure needs guardrails like bounded input, max passes, timeouts. Someone else just called it out as unhelpful AI noise contributing nothing.
This isn't as interesting as 'DNS parsing is Turing complete' since nobody can just send you a file and force an infinite loop, it's a DSL for library implementers similar to Mathematica, and whoever writes the rules is responsible for not looping forever.
Counterpoint: it's still weird that the spec is this unrestricted, you could craft input that triggers worst case runtime even in a straightforward implementation, there was a real CPython issue like this recently.
Also, a dev's job is basically 'prove this halting problem instance you're being paid to solve today is decidable' lol.
From a CS view it's spooky but not surprising, rewrite rule systems are almost always Turing complete once you get self reference going, you have to actively work to keep a complex system decidable.
With 7200 languages and stuff like bidi text, ligatures, contextual shaping, it would honestly be more surprising if Unicode's formatting DIDN'T end up Turing complete.
Reminds me of that Llama.ttf project, a font that's also an LLM.