Sudoku in Turing-Complete Unicode Transliteration Rules
Nicolas Seriot (Hacker News, Reddit):
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.
[…]
To prove UTS #35 universality, we compile 2-tag systems (Post, 1943), a model proven universal (Cocke & Minsky, 1964), into transliteration rules.
[…]
Transliteration rules were designed to turn “é” into “e”. Three lines of them can compute the Collatz function.
Inspired by this, I tried creating an implementation that “solves #Sudoku” using only UTS#35 transformation rules 😎
Previously:
