Unicode 的转写规则是图灵完备的

# Unicode 的转写规则是图灵完备的 来源：https://seriot.ch/computation/uts35/ ### Nicolas Seriot #### 计算（https://seriot.ch/computation/）> Unicode 的转写规则是图灵完备的 *2026 年 7 月* Hacker News 讨论：https://news.ycombinator.com/item?id=48829797 另见：Jira 是图灵完备的（https://seriot.ch/computation/jira.html） **目录** 1. 转写规则（https://seriot.ch/computation/uts35/#1） 2. 2‑标记系统（https://seriot.ch/computation/uts35/#2） 3. Collatz 函数（https://seriot.ch/computation/uts35/#3） 4. 正确性与通用性（https://seriot.ch/computation/uts35/#4） 5. ICU 的重写限制（https://seriot.ch/computation/uts35/#5） 6. 规则 110（https://seriot.ch/computation/uts35/#6） 7. 素数（https://seriot.ch/computation/uts35/#7） 8. 结论（https://seriot.ch/computation/uts35/#8） 9. 附录：文件（https://seriot.ch/computation/uts35/#9） 我一直在想 Unicode 是否支持通用计算。核心的 Unicode 算法（规范化、大小写转换、双向排版、排序）刻意设定了范围，但 UTS #35 转写规则（https://www.unicode.org/reports/tr35/tr35-general.html#Transforms）在其自然无界的语义下却并非如此。这是我之前未发现已发表的结果。 这些规则以语言环境数据的形式（https://github.com/unicode-org/cldr/tree/main/common/transforms）打包在 ICU（https://icu.unicode.org/）中——ICU 是广泛使用的 Unicode/全球化库，用于大多数操作系统、浏览器、运行时和数据库。给定规则文件在给定输入上是否终止是**不可判定的**（https://en.wikipedia.org/wiki/Halting_problem）。 ### 1. 转写规则 转写器通常将 "é" 转换为 "e"，使用一组有序的**重写规则**（https://www.unicode.org/reports/tr35/tr35-general.html#Conversion_Rules）： `` L { x } R > y ; `` 当子串 `x` 位于（可选的）上下文 `L` 和 `R` 之间时，被替换为 `y`。**重访**（https://www.unicode.org/reports/tr35/tr35-general.html#Revisiting）特性允许在替换中使用 `|`，这会将光标放置在新文本内部，从而使新写入的内容可以触发更多规则。 示例： `` x > y | z ; za > w ; `` `xa` 重写为 `y|za`（光标在 `z` 之前）。引擎重新扫描，`za` 匹配，产生 `yw`。 使用 Python 的 PyICU（https://pypi.org/project/pyicu/）模块： `` from icu import Transliterator as T t = T.createFromRules("", "x > y|z; za > w;") print(t.transliterate("xa")) # 输出 yw `` 这是 Latin‑Katakana（https://github.com/unicode-org/cldr/blob/main/common/transforms/Latin-Katakana.xml#L126-L127）变换。它使用了上下文、捕获组、量词和光标。在 `i` 或 `e` 之前，`c` 重写为 `s`，并且光标回退，使 `s` 的规则重新触发。与上述相同的重访技巧，已用于生产环境中的语言环境数据。 `` c } i → | s ; c } e → | s ; `` ### 2. 2‑标记系统 为了证明 UTS #35 的通用性，我们将一个**2‑标记系统**（https://en.wikipedia.org/wiki/Tag_system）（Post, 1943（https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/n3/mode/2up））编译为转写规则——这是一个已被证明通用（Cocke & Minsky, 1964（https://dl.acm.org/doi/10.1145/321203.321206））的模型。 一个 2‑标记系统中每个字母有一条产生式。每步移除前两个字母，并追加第一个字母的产生式。当剩余字母少于两个时停机。 ### 3. Collatz 函数 我们的示例是 Liesbeth De Mol（https://doi.org/10.1016/j.tcs.2007.10.020）为**Collatz**（https://en.wikipedia.org/wiki/Collatz_conjecture）函数（偶数 n → n/2，奇数 n → (3n+1)/2）设计的 2‑标记系统：`a → bc`，`b → a`，`c → aaa`，初始一元词为 `aaa...a`。我们在词前面加上一个读取标记 `M`，它把机器固定在前端。当 `M` 处没有规则匹配时，任何地方都不会匹配。 该构造为每个字母使用一条规则： `` 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`、量词与光标都是标准规则语法（参见规范的**变换语法字符**（https://www.unicode.org/reports/tr35/tr35-general.html#Transform_Syntax_Characters）表）。 你可以使用 uts35.py（https://seriot.ch/computation/uts35/uts35.py）运行这个机器——collatz.txt（https://seriot.ch/computation/uts35/collatz.txt）是上述规则（已删除 `|`），因此每次传递恰好执行一个标记步骤。从 `aaa` 开始，运行结果复现了 Wikipedia 标记系统（https://en.wikipedia.org/wiki/Tag_system）页面上的工作示例（`aaa`、`abc`、`cbc`、`caaa`、`aaaaa`……），其中数值以连续 `a` 的形式出现。同样的规则也可以在完全不用 Python 的情况下，通过 ICU 自带的 `uconv` 运行（uts35.sh（https://seriot.ch/computation/uts35/uts35.sh））。test.sh（https://seriot.ch/computation/uts35/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. **最多一条规则匹配。** 标记唯一存在。它后面的字母选择规则。`([abc]*)` 捕获所有剩余的字母。 2. **一次重写恰好是一个标记步骤。** 字母 `x` 的规则仅当标记后面至少有 `x` 加上至少一个字母时才匹配。替换构造下一个配置。 3. **停机对应。** 每条规则都需要标记后有两个字母，因此 `Ma` 和 `M` 是固定点。变换恰好当标记系统停机时终止。 综合起来，通过归纳：经过 *k* 次重写后，字符串恰好是 `M` 后跟标记系统经过 *k* 步后的词，并且变换恰好当标记系统停机时达到固定点。这里没有任何针对 Collatz 的特殊之处。每个字母一条规则可以编译*任何* 2‑标记系统，因此一个通用的 2‑标记系统会产生一个固定的规则文件，该文件可以模拟任意图灵机（编码在初始词中）。 ### 5. ICU 的重写保护 ICU 在每个 `transliterate()` 调用中，每输入代码点最多进行 16 次重写后停止（`loopLimit = span << 4` 在 rbt.cpp（https://github.com/unicode-org/icu/blob/main/icu4c/source/i18n/rbt.cpp）中；Java 移植版有相同的保护（https://github.com/unicode-org/icu/blob/main/icu4j/main/translit/src/main/java/com/ibm/icu/text/RuleBasedTransliterator.java））。然而，规范本身并未定义限制。这个保护是 ICU 为防止无限计算而添加的实用措施，因为终止性是不可判定的。本例中，每次重写执行一个完整的标记步骤，因此迭代直到字符串稳定是安全的。 ### 6. 规则 110 运行器不仅限于标记系统。任何规则文件都是一个程序。rule110.txt（https://seriot.ch/computation/uts35/rule110.txt）用 14 条规则实现了规则 110 元胞自动机。细胞用 `.`（0）和 `*`（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（https://seriot.ch/computation/uts35/primes.txt）是 Wolfram 的实时素数生成元胞自动机（*A New Kind of Science*，第 640 页（https://www.wolframscience.com/nks/p640--computations-in-cellular-automata/））；16 种状态（`0`‑`f`）和 223 条变换规则。燃料后的第一个细胞在素数的滴答时恰好是 `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. 结论 转写规则原本是为了将 "é" 转换为 "e" 而设计的。其中三行规则就能计算 Collatz 函数。 无界的重写加上可重访光标是实现通用性的老配方。令人惊讶的是，它存在于一种用于语言环境文件的数据格式中，并随每个操作系统一同发布，而其规范并未提及这种可能性。 上述讨论表明，一个转写规则文件不仅仅是数据，它是一个程序。如果你接受来自外部的变换规则，你就是在接受代码，这应当被审查并在运行时加以限制——正如 ICU 已经做的那样。 ### 附录：文件 - collatz.txt（https://seriot.ch/computation/uts35/collatz.txt）—— 三条规则的 Collatz 机器（每次传递一个标记步骤） - rule110.txt（https://seriot.ch/computation/uts35/rule110.txt）—— 14 条规则的规则 110 - primes.txt（https://seriot.ch/computation/uts35/primes.txt）—— 223 条规则的 Wolfram 素数生成元胞自动机 - uts35.py（https://seriot.ch/computation/uts35/uts35.py）—— 运行器，依赖 PyICU - uts35.sh（https://seriot.ch/computation/uts35/uts35.sh）—— 运行器，使用 ICU 自带的 `uconv`，无需 Python - test.sh（https://seriot.ch/computation/uts35/test.sh）—— 自检脚本 *环境：ICU 78.3，PyICU 2.16.2，macOS；同时在 Debian 12 上使用 ICU 72.1 验证；2026 年 7 月*