{"id":52947,"date":"2026-08-19T16:47:33","date_gmt":"2026-08-19T20:47:33","guid":{"rendered":"https:\/\/mjtsai.com\/blog\/?p=52947"},"modified":"2026-08-19T16:47:33","modified_gmt":"2026-08-19T20:47:33","slug":"sudoku-in-turing-complete-unicode-transliteration-rules","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2026\/08\/19\/sudoku-in-turing-complete-unicode-transliteration-rules\/","title":{"rendered":"Sudoku in Turing-Complete Unicode Transliteration Rules"},"content":{"rendered":"

Nicolas Seriot<\/a> (Hacker News<\/a>, Reddit<\/a>):<\/p>\n

\n

The core Unicode algorithms (normalization, casing, bidi, collation) are deliberately bounded, but UTS #35 transliteration rules<\/a>, under their natural unbounded semantics, are not. This is a result I haven’t found published before.<\/p>\n

These rules ship as locale data<\/a> in ICU<\/a>, the Unicode library shipped in operating systems, browsers, runtimes, and databases. Whether a given rule file terminates on a given input is undecidable<\/a>.<\/p>\n

[…]<\/p>\n

To prove UTS #35 universality, we compile 2-tag systems<\/a> (Post, 1943<\/a>), a model proven universal (Cocke & Minsky, 1964<\/a>), into transliteration rules.<\/p>\n

[…]<\/p>\n

Transliteration rules were designed to turn “é” into “e”. Three lines of them can compute the Collatz function.<\/p>\n<\/blockquote>\n\n

KT_Music<\/a>:<\/p>\n

\n

Inspired by this,\nI tried creating an implementation that “solves #Sudoku” using only UTS#35 transformation rules 😎<\/p>\n<\/blockquote>\n\n

Previously:<\/p>\n