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

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:

... continue reading