尼古拉斯·塞里奥Nicolas Seriot【计算】/【计算】 Unicode 音译规则具备图灵完备性_2026 年 7 月_Hacker News 讨论链接https://news.ycombinator.com/item?id48829797另见【Jira 具备图灵完备性】(https://seriot.ch/computation/jira.html)【目录】音译规则2-标签系统考拉兹函数正确性与通用性ICU 的重写保护机制规则 110质数结论附录文件一段时间以来一直在思索 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)。【音译规则】音译器通常会运用一系列有序的【重写规则】(https://www.unicode.org/reports/tr35/tr35-general.html#Conversion_Rules)把 “é” 转换为 “e”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 Tt T.createFromRules(, x y|z; za w;)print(t.transliterate(xa)) # yw以下是【拉丁字母 - 片假名】(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-标签系统】为证明 UTS #35 的通用性将【2-标签系统】(https://en.wikipedia.org/wiki/Tag_system)【波斯特Post1943 年】(https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/n3/mode/2up)编译为音译规则。2-标签系统已被证明具有通用性【科克Cocke和明斯基Minsky1964 年】(https://dl.acm.org/doi/10.1145/321203.321206)。2-标签系统为每个字母定义一条产生式规则。每一步会移除前两个字母并追加第一个字母的产生式。当剩余字母少于两个时系统停止运行。【考拉兹函数】示例是【利斯贝斯·德·莫尔Liesbeth De Mol】(https://doi.org/10.1016/j.tcs.2007.10.020) 为【考拉兹】(https://en.wikipedia.org/wiki/Collatz_conjecture) 函数偶数 n → n/2奇数 n → (3n 1)/2设计的 2-标签系统a → bcb → ac → 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、另一个字母然后捕获其余部分。替换操作会生成下一个配置并将光标移回标记之前以便立即触发下一步操作。![一次规则应用](uts35.png)字符类、捕获组和 $1、量词和光标都是标准的规则语法规范中的【转换语法字符】(https://www.unicode.org/reports/tr35/tr35-general.html#Transform_Syntax_Characters) 表。可以使用【uts35.py】(uts35.py) 运行这个机器 —— 【collatz.txt】(collatz.txt) 是上述规则去掉 | 后的版本这样每次运行正好执行一个标签步骤。从 aaa 开始运行会重现维基百科【标签系统】(https://en.wikipedia.org/wiki/Tag_system) 页面上的示例aaaabccbccaaaaaaaa...值以连续的 a 形式呈现。同样的规则也可以不使用 Python通过 ICU 自带的 uconv 运行【uts35.sh】(uts35.sh)。【test.sh】(test.sh) 会检查机器的输出是否符合预期。% python3 uts35.py collatz.txt aaaICU 78.30 - Maaa # 31 - Mabc2 - Mcbc3 - Mcaaa4 - Maaaaa # 55 - Maaabc6 - Mabcbc7 - Mcbcbc8 - Mcbcaaa9 - Mcaaaaaa10 - Maaaaaaaa # 811 - Maaaaaabc12 - Maaaabcbc13 - Maabcbcbc14 - Mbcbcbcbc15 - Mbcbcbca16 - Mbcbcaa17 - Mbcaaa18 - Maaaa # 419 - Maabc20 - Mbcbc21 - Mbca22 - Maa # 223 - Mbc24 - Ma # 1【正确性与通用性】最多只有一条规则匹配只有一个标记。标记后面的字母决定了匹配的规则。([abc]*) 捕获所有剩余的字母。一次重写恰好对应一个标签步骤字母 x 的规则只有在标记面对 x 以及至少一个其他字母时才会匹配。替换操作会构建下一个配置。停机情况对应每条规则都要求标记后面至少有两个字母因此 Ma 和 M 是不动点。转换操作恰好会在标签系统停止时终止。综合以上几点通过归纳法可以得出经过 _k_ 次重写后字符串恰好是 M 后面跟着标签系统经过 _k_ 步后的字符串并且转换操作恰好会在标签系统停止时达到不动点。这里的内容并不局限于考拉兹函数。为每个字母编写一条规则可以编译 _任何_ 2-标签系统因此一个通用的 2-标签系统可以生成一个固定的规则文件用于模拟任何图灵机初始字符串对图灵机进行编码。【ICU 的重写保护机制】ICU 会在每个 transliterate() 调用中对每个输入代码点进行 16 次重写后停止【rbt.cpp】(https://github.com/unicode-org/icu/blob/main/icu4c/source/i18n/rbt.cpp) 中的 loopLimit span 4Java 版本也有【相同的保护机制】(https://github.com/unicode-org/icu/blob/main/icu4j/main/translit/src/main/java/com/ibm/icu/text/RuleBasedTransliterator.java)。不过规范本身并没有设置限制。这个保护机制是 ICU 为防止无限计算而采取的实用措施因为停机问题是不可判定的。在这里每次重写都执行一个完整的标签步骤因此迭代直到字符串稳定是安全的。【规则 110】运行器并不局限于标签系统。任何规则文件都可看作一个程序。【rule110.txt】(rule110.txt) 用 14 条规则实现了规则 110 元胞自动机。元胞用 .0和 *1表示。一个 “头” 携带前两个元胞并就地重写每个元胞。一次运行对应一代。每一代消耗一个 “燃料” g转化为 s当燃料耗尽时运行会自动停止。python3 uts35.py rule110.txt ggggggggg*ICU 78.30 - Mggggggggg*1 - Mggggggggs**.2 - Mgggggggss***..3 - Mggggggsss**.*...4 - Mgggggssss*****....5 - Mggggsssss**...*.....6 - Mggggssssss***..**......7 - Mgggsssssss**.*.***.......8 - Mgssssssss*******.*........9 - Msssssssss**.....***.........【质数】【primes.txt】(primes.txt) 是沃尔弗拉姆Wolfram的实时质数生成元胞自动机《一种新科学》【第 640 页】(https://www.wolframscience.com/nks/p640--computations-in-cellular-automata/)有 16 种状态0 - f和 223 条转换规则。燃料后面的第一个元胞在质数时刻恰好为 0。% python3 uts35.py primes.txt gggggggggggg0a048ICU 78.30 - Mgggggggggggg0a0481 - Mgggggggggggs9604d72 - Mggggggggggss06f5d803 - Mgggggggggsss0ad3d8704 - Mggggggggssss96fc0d7005 - Mgggggggsssss0adb0080006 - Mggggggssssss96fad0870007 - Mgggggsssssss0a960f8700008 - Mggggssssssss9af6f017000009 - Mgggsssssssss9adad01800000010 - Mggssssssssss96f60f18700000011 - Mgsssssssssss0a06f0287000000012 - Mssssssssssss96fad02d700000000【结论】音译规则原本是为将 “é” 转换为 “e” 而设计的。仅仅三行规则就可以计算考拉兹函数。带有重新访问光标的无边界重写是实现通用性的经典方法。令人惊讶的是这种方法存在于区域设置文件的数据格式中并且每个操作系统都包含了这种格式但其规范却未提及这种可能性。上述讨论表明音译规则文件不仅仅是数据它实际上是一个程序。如果从外部接受转换规则就相当于接受了代码应该对其进行审查并在运行时设置边界就像 ICU 已经做的那样。【附录文件】【collatz.txt】(collatz.txt) —— 三规则的考拉兹机器每次运行执行一个标签步骤【rule110.txt】(rule110.txt) —— 用 14 条规则实现的规则 110【primes.txt】(primes.txt) —— 用 223 条规则实现的沃尔弗拉姆质数生成元胞自动机【uts35.py】(uts35.py) —— 运行器使用 PyICU【uts35.sh】(uts35.sh) —— 运行器使用 ICU 自带的 uconv无需 Python【test.sh】(test.sh) —— 自我检查_环境ICU 78.3PyICU 2.16.2macOS在 Debian 12 上使用 ICU 72.1 也进行了验证2026 年 7 月_