Unicode's transliteration rules are Turing-complete
18 hours ago
- #Transliteration
- #Unicode
- #Computation
- Unicode UTS #35 transliteration rules, under their natural unbounded semantics, allow universal computation, a result not previously published.
- These rules are used in locale data in ICU, a widely used Unicode/globalization library, and termination on a given input is undecidable.
- Transliteration rules include features like contexts, capture groups, quantifiers, and a revisiting cursor, enabling complex rewriting operations.
- A 2-tag system can be compiled into transliteration rules, proving universality by simulating models like the Collatz function.
- ICU implements a loop limit to prevent infinite computation, but the specification itself does not define such a limit.
- Examples demonstrate that transliteration rule files can act as programs, computing functions like Rule 110 cellular automaton and prime generation.
- The unbounded rewriting capability in locale data formats poses security implications, as accepting transform rules is akin to accepting code.