Unicode の文字変換ルール、チューリング完全性を持つ—任意の計算が可能に

要約

Unicode の標準化記述である UTS #35 の文字変換ルール (transliteration rules) がチューリング完全であることが確認された。これは OS・ブラウザ・データベースで広く使われる ICU ライブラリがロケールデータとして実装する仕様であり、停止問題は決定不可能である。著者は 2-tag システム (Post, 1943) をこのルール形式にコンパイルしてコラッツ関数を実装、さらに Rule 110 セルオートマトンと素数生成オートマトンも動作実証した。