HN 日本語サマリー

← 一覧へ戻る
科学・技術

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

Unicode's transliteration rules are Turing-complete (seriot.ch)

106 pointsby beefburger30 コメント

要約

Unicodeの文字転写ルール(UTS #35)は、自然な無制限のセマンティクス下でチューリング完全であることが発見されました。これは、オペレーティングシステム、ブラウザ、ランタイム、データベースで広く使用されているICUライブラリに含まれるロケールデータとして提供されています。この発見は、文字転写ルールファイルが単なるデータではなく、実行時にレビューおよび制限されるべきプログラムコードである可能性を示唆しています。

全文翻訳

🦄 Unicodeの文字変換ルールはチューリング完全である

Nicolas Seriot
計算 > Unicodeの文字変換ルールはチューリング完全である

2026年7月

関連項目: Jiraはチューリング完全

主張: 仕様通り、UTS #35の文字変換ルール言語はチューリング完全である。これは、アルゴリズムが意図的に制限され、常に終了することが保証されているUnicodeにおいては例外である。この仕様は、書き換え制限のない再帰カーソルを定義している。ICUの実装は呼び出しごとの上限を実装しているが、仕様自体にはない。

更新 2026-07-11: @neoclassic_tech がICUの文字変換ルールで数独ソルバーをプログラミングした。

目次

  1. 文字変換ルール
  2. 証明: 2-タグシステム
  3. コラッツ関数
  4. 正当性と普遍性
  5. ICUの書き換えガード
  6. デモンストレーション: ルール110
  7. デモンストレーション: 素数生成器
  8. セキュリティに関する注記
  9. 結論
  10. 付録: ファイル

私はしばらくの間、Unicodeが普遍的な計算を許容するかどうか疑問に思っていた。コアとなるUnicodeアルゴリズム(正規化、大文字小文字変換、双方向テキスト、照合順序)は意図的に制限されているが、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

Latin-Katakana変換の一部を以下に示す。i または e の前では、c は s に書き換えられ、カーソルが後退するため s のルールが再発火する。上記の再帰トリックと同じもので、本番のロケールデータに出荷されている。

c } i → | s ;
c } e → | s ;
2. 証明: 2-タグシステムコンパイル

2-タグシステムは、文字ごとに1つのプロダクションを持つ。各ステップで最初の2文字が削除され、最初の文字のプロダクションが追加される。2文字未満になると終了する。

2-タグシステム(Post, 1943)は普遍的であることが証明されている(Cocke & Minsky, 1964)。したがって、UTS #35の普遍性を証明するために、2-タグシステムを文字変換ルールにコンパイルする。

3. コラッツ関数

私たちの例は、Liesbeth De Mol によるコラッツ関数(偶数 n → n/2、奇数 n → (3n+1)/2)のための2-タグシステムである。これは、単項ワード aaa...a に対して a → bc、b → a、c → aaa というルールを持つ。ワードの先頭に読み取りマーカー 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文字に一致し、残りのすべてをキャプチャする。置換は次の構成を書き込み、カーソルをマーカーの前に戻すため、次のステップがすぐに発火する。

[画像: One rule application]

文字クラス、キャプチャグループと $1、量指定子、カーソルは標準的なルール構文である(仕様の変換構文文字テーブル)。

このマシンはPythonのuts35.pyで実行できる。collatz.txt は上記のルールから | を削除したもので、各パスで正確に1つのタグステップを実行する。aaa からの実行は、Wikipediaのタグシステムページの作業例(aaa、abc、cbc、caaa、aaaaa、...)を、a の連続として現れる値で再現する。同じルールは、ICUの標準 uconv(uts35.sh)でも、Pythonなしで実行できる。

% 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つのルールが一致する。 マーカーは1つだけ存在する。その後の文字がルールを選択する。([abc]*) は残りのすべての文字をキャプチャする。
  2. 1回の書き換えは正確に1つのタグステップである。 文字 x のルールは、マーカーが x と少なくとももう1文字に直面した場合にのみ一致する。置換は次の構成を構築する。
  3. 終了が対応する。 すべてのルールはマーカーの後に2文字を必要とするため、Ma と M は不動点である。変換はタグシステムが終了するときに正確に終了する。

これらを合わせて、帰納法により、k 回の書き換えの後、文字列は正確に k ステップ後のタグシステムのワードに M を付けたものになり、タグシステムが終了するときに変換は不動点に達する。ここにあるものはコラッツに特有のものではない。文字ごとの1つのルールは、アルファベット Σ とプロダクション P を持つ任意の 2-タグシステムをコンパイルする。

M x [Σ] ([Σ]*) > | M $1 P(x) ;

したがって、普遍的な2-タグシステムは、マシンとその入力を初期ワードにエンコードして、任意のチューリングマシンをシミュレートする不動のルールファイルを提供する。

5. ICUの書き換えガード

ICUは、各 transliterate() 呼び出しを、UTF-16コードユニットあたり16回の書き換えで停止させる(rbt.cppのloopLimit = span << 4;Javaポートには同じガードがある)。しかし、仕様自体は制限を定義していない。このガードは、各呼び出しを常に制限された状態に保つためのICUの実用的な追加機能である。ここでは、各書き換えは完全なタグステップであるため、ガードはステップ間でのみ中断できる。文字列が変わらなくなるまで transliterate() を繰り返し呼び出すことは何も失わない。(これらのマシンでは、変更されない文字列はルールが一致しなかったことを意味する。一般に、終了しないシステムは同じ文字列にサイクルバックする可能性があるため、等価性だけでは終了テストにならない。)

6. デモンストレーション: ルール110

上記の還元は普遍性を確立する。このセクションと次のセクションの構成は、主要な証明の一部ではない。これらは、言語が最小限のエンコーディングを超えて快適にプログラミング可能であることを示している。

ルール言語はタグシステムに限定されない。rule110.txt は、14のルールでルール110セルオートマトンを実装している。セルは . (0) と * (1) で表される。ヘッドは前の2つのセルを運び、各セルをその場で書き換える。1回のパスが1世代であり、各世代は1つの燃料セル g を消費して s を残し、燃料がなくなると実行は自己終了する。

ルール110自体は普遍的であることが証明されている(Cook, 2004)。したがって、ここで実装されている更新ルールは、原理的には必要な計算能力すべてであるが、この燃料制限付きプログラムは指定された世代数だけ実行されるため、デモンストレーションであり、2番目の証明ではない。

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の変換ルールを持つ。入力ワードは、燃料とオートマトンの初期構成 0a048 である。燃料の後の最初のセルは、素数のティック(t > 1)で正確に 0 になる。

% python3 uts35.py primes.txt gggggggggggg0a048
ICU 78.3
  0 - Mgggggggggggg0a048
  1 - Mgggggggggggs9604d7
  2 - Mggggggggggss06f5d80
  3 - Mgggggggggsss0ad3d870
  4 - Mggggggggssss96fc0d700
  5 - Mgggggggsssss0adb008000
  6 - Mggggggssssss96fad087000
  7 - Mgggggsssssss0a960f870000
  8 - Mggggssssssss9af6f01700000
  9 - Mgggsssssssss9adad018000000
 10 - Mggssssssssss96f60f187000000
 11 - Mgsssssssssss0a06f02870000000
 12 - Mssssssssssss96fad02d700000000
8. セキュリティに関する注記

これは計算可能性に関する結果であり、セキュリティ開示ではない。これらのいずれも通常のUnicodeテキストを実行可能にするものではない。標準のICUは各 transliterate() 呼び出しをコードポイントあたり16回の書き換えでキャップするため、単一の呼び出しは常に返る。ここで普遍的なのは、無制限の再呼び出しで駆動されるカスタムルールファイルである。

したがって、表面積は狭い。信頼できないソースからルールファイルを受け入れることは、信頼できないプログラムを受け入れることである。リスクは非終端とリソース枯渇である。ICUの呼び出しごとのガードはすでに非終端を抑制しているが、単一の制限付き呼び出しでもコストがかかる場合がある。しかし、再実装は常にガードを引き継ぐとは限らない。ICU4Xの実験的なRust transliteriteratorとTwitterのRuby twitter-cldrは、どちらも再帰カーソルを実装しており、書き換え制限なしで反復処理する。

9. 結論

文字変換ルールは「é」を「e」に変換するために設計された。それらの3行でコラッツ関数を計算できる。

再帰カーソルによる無制限の書き換えは、普遍性のための古いレシピである。驚くべきは、それがUnicode仕様の一角に存在することであり、そのコアアルゴリズムはすべて意図的に制限されており、その可能性については決して言及されていない。

10. 付録: ファイル
  • 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。ICU 72.1 on Debian 12でも検証済み。2026年7月