Unicodeの文字転写ルールはチューリング完全である

ニコラス・セリオ 計算 > Unicodeの文字転写ルールはチューリング完全である 🦄 Unicodeの文字転写ルールはチューリング完全である 2026年7月 関連情報: Jiraはチューリング完全である 目次 文字転写ルール 2-タグシステム コラッツ関数 正確性と普遍性 ICUのリライトガード ルール110 素数 結論 付録: ファイル 私はしばらくの間、Unicodeが普遍的な計算を可能にするかどうか疑問に思っていました。コアのUnicodeアルゴリズム（正規化、大文字小文字、bidi、照合）は意図的に制限されていますが、UTS #35の文字転写ルールは、その自然な無制限のセマンティクス下ではそうではありません。これは、私がまだ公開されていないと見つけた結果です。これらのルールは、ほとんどのオペレーティングシステム、ブラウザ、ランタイム、データベースで使用されている広く普及しているUnicode/グローバリゼーションライブラリであるICUのロケールデータとして提供されています。特定のルールファイルが特定の入力で終了するかどうかは決定不能です。 1. 文字転写ルール 文字転写子は通常、「é」を「e」に変換します。順序付けられたリライトルールのリストを使用します。 L { x } R > y ; ここで、xという部分文字列は、オプションのコンテキストLとRの間に配置されている場合にyに置き換えられます。リビジティング機能は、置換内に|を許可します。これはカーソルを新しいテキストの内部に配置するため、新しく書かれたマテリアルがさらなるルールをトリガーする可能性があります。 例：x > y | z ; za > w ; xa は y|za にリライトされます（カーソルはzの前）。エンジンは再スキャンし、zaが一致して yw を生成します。 PythonのPyICUモジュールを使用します。 from icu import Transliterator as T t = T.createFromRules("", "x > y|z; za > w;") print(t.transliterate("xa")) # yw これはラテン-カ夕カナ変換です。コンテキスト、キャプチャグループ、量指定子、カーソルを使用します。iまたはeの前に、cはsにリライトされ、カーソルが戻るため、sルールが再発火します。上記の同じリビジティングトリックは、本番のロケールデータに含まれています。 c } i → | s ; c } e → | s ; 2. 2-タグシステム UTS #35の普遍性を証明するために、普遍的であることが証明されているモデル（Cocke & Minsky, 1964）である2-タグシステム（Post, 1943）を文字転写ルールにコンパイルします。2-タグシステムは、文字ごとに1つのプロダクションを持ちます。各ステップは最初の2文字を削除し、最初の文字のプロダクションを付加します。2文字未満になると停止します。 3. コラッツ関数 私たちの例は、コラッツ関数（偶数 n → n/2、奇数 n → (3n+1)/2）のためのLiesbeth De Molによる2-タグシステムです。a → bc、b → a、c → aaa。これは、unaryワードaaa...aに対して行われます。読み取りマーカーMを単語の前に付け、マシンを先頭に固定します。Mでルールが一致しない場合、どこでもルールは一致しません。この構築は、文字ごとに1つのルールを使用します。 M a [abc] ([abc]*) > | M $1 b c ; M b [abc] ([abc]*) > | M $1 a ; M c [abc] ([abc]*) > | M $1 a a a ; 最初のルールはマーカー、文字a、さらに1文字に一致し、残りのすべての文字をキャプチャします。置換は次の構成を書き込み、カーソルをマーカーの前に戻すため、次のステップがすぐに発火します。文字クラス、キャプチャグループと$1、量指定子、カーソルは標準的なルール構文です（仕様のTransform Syntax Charactersテーブル）。 このマシンはuts35.pyで実行できます。collatz.txtは、|が削除された上記のリライトルールであり、各パスは正確に1つのタグステップを実行します。aaaから、実行はWikipediaのタグシステムページ（aaa、abc、cbc、caaa、aaaaa、...）の作業例を、値がaの連続として現れるように複製します。同じルールは、Pythonなしでも、ICUの標準uconv（uts35.sh）を通じて実行されます。test.shは、期待される出力に対してマシンをチェックします。 % python3 uts35.py collatz.txt aaa ICU 78.3 0 - Maaa # 3 1 - Mabc 2 - Mcbc 3 - Mcaaa 4 - Maaaaa # 5 5 - Maaabc 6 - Mabcbc 7 - Mcbcbc 8 - Mcbcaaa 9 - Mcaaaaaa 10 - Maaaaaaaa # 8 11 - Maaaaaabc 12 - Maaaabcbc 13 - Maabcbcbc 14 - Mbcbcbcbc 15 - Mbcbcbca 16 - Mbcbcaa 17 - Mbcaaa 18 - Maaaa # 4 19 - Maabc 20 - Mbcbc 21 - Mbca 22 - Maa # 2 23 - Mbc 24 - Ma # 1 4. 正確性と普遍性 最大で1つのルールが一致します。マーカーは正確に1つです。その後の文字がルールを選択します。([abc]*)は残りのすべての文字をキャプチャします。1つのリライトは正確に1つのタグステップです。文字xのルールは、マーカーがxと少なくとも1つの追加の文字に直面している場合にのみ一致します。置換は次の構成を構築します。停止は対応します。すべてのルールはマーカーの後に2文字を必要とするため、MaとMは不動点です。変換は、タグシステムが停止するときにのみ終了します。帰納法により、k回の書き換えの後、文字列は正確にMとkステップ後のタグシステムの単語になり、変換はタグシステムが停止するときにのみ不動点に達します。ここにあるものはコラッツに特有のものではありません。文字ごとの1つのルールは任意の2-タグシステムをコンパイルするため、普遍的なものは任意のチューリングマシンをシミュレートする固定ルールファイルをもたらし、初期単語にエンコードされます。 5. ICUのリライトガード ICUは、各transliterate()呼び出しをコードポイントあたり16リライト後に停止します（rbt.cppのloopLimit = span << 4; Javaポートも同じガードを持っています）。ただし、仕様自体は制限を定義していません。ガードは、終了が決定不能であるため、無限計算を防ぐためのICUの実用的な追加です。ここでは、各リライトは完全なタグステップを実行するため、文字列が安定するまで反復することは安全です。 6. ルール110 ランナーはタグシステムに限定されません。任意のルールファイルはプログラムです。rule110.txtは14ルールでルール110セルオートマトンを実装しています。セルは.（0）と*（1）で書かれます。ヘッドは前の2つのセルを運び、各セルをその場で書き換えます。1回のパスは1世代です。世代ごとに1つの燃料gがsに費やされ、燃料がなくなると実行は自己停止します。 % python3 uts35.py rule110.txt "ggggggggg*" ICU 78.3 0 - Mggggggggg* 1 - Mggggggggs**. 2 - Mgggggggss***.. 3 - Mggggggsss**.*... 4 - Mgggggssss*****.... 5 - Mggggsssss**...*..... 6 - Mgggssssss***..**...... 7 - Mggsssssss**.*.***....... 8 - Mgssssssss*******.* 9 - Msssssssss**.....***......... 7. 素数 primes.txtは、Wolframのリアルタイム素数生成セルオートマトン（A New Kind of Science, p. 640）です。16状態（0-f）と223変換ルールがあります。燃料の後の最初のセルは、素数のティックで正確に0になります。 8. 結論 文字転写ルールは、「é」を「e」に変換するために設計されました。そのうちの3行でコラッツ関数を計算できます。リビジティングカーソルによる無制限のリライトは、普遍性のための古いレシピです。驚くべきことは、それがすべてのOSに出荷されているロケールファイルのデータ形式に存在し、その仕様ではその可能性について言及されていないことです。上記の議論は、文字転写ルールファイルが単なるデータではなく、プログラムであることを示しています。外部から変換ルールを受け入れる場合、コードを受け入れていることになります。これは、ICUがすでに実行しているように、実行時にレビューおよび制限されるべきです。 付録: ファイル collatz.txt — 3ルールコラッツマシン（パスあたり1つのタグステップ） rule110.txt — 14ルールでのルール110 primes.txt — 223ルールでのWolframの素数生成セルオートマトン uts35.py — ランナー、PyICU uts35.sh — ランナー、ICUの標準uconv、Pythonなし test.sh — 自己チェック 環境: ICU 78.3, PyICU 2.16.2, macOS; Debian 12上のICU 72.1でも検証済み; 2026年7月