Unicode's transliteration rules are Turing-complete
Unicode's transliteration system (UTS #35) defines rules for converting text between different scripts. This article demonstrates that these rules are powerful enough to simulate any arbitrary computation, achieving Turing completeness.
背景メモ
- Unicodeの「UTS #35（ロケールデータマークアップ言語, LDML）」が定義する文字列の翻字（transliteration）ルール体系が、**チューリング完全（Turing-complete）** であることが示された。つまり、理論上あらゆる計算を翻字ルールだけで実行できる。
- 著者はセキュリティ研究者のNicolas Seriot。UTS #35のルールには変数、条件分岐、ループに相当する仕組みが含まれており、これらを組み合わせて「Rule 110」（一次元セル・オートマトン、それ自体がチューリング完全）をシミュレートした。
- 影響：Unicodeの翻字ルールは世界中のソフトウェア（ICUライブラリ経由でOSやプログラミング言語に組み込まれている）でテキスト処理に使われる。悪意のあるルールを仕込めば、翻字処理の際に予期しない計算（例：無限ループや情報漏洩）が発生する可能性がある。
- 背景：UTS #35は主にロケール（地域化）データとカレンダー・通貨フォーマットを定義する仕様。翻字機能はその付属的な位置づけだが、かつてICUにはリモートからルールを読み込む機能があり、セキュリティ問題として注目された経緯がある。