Unicode’s Transliteration Rules Are Turing-Complete

I’ve been wondering for a while whether Unicode allows universal computation. The core Unicode algorithms (normalization, casing, bidi, collation) are deliberately bounded, but UTS #35 transliteration rules, under their natural unbounded semantics, are not. This is a result I haven’t found published before. These rules ship as locale data in ICU, the widely used Unicode/globalization library used in most operating systems, browsers, runtimes, and databases. Whether a given rule file terminates on a given input is undecidable.

我一直很好奇 Unicode 是否允许通用计算。Unicode 的核心算法（规范化、大小写转换、双向算法、排序）都是刻意有界限的，但 UTS #35 的音译规则（Transliteration Rules）在其自然的无界语义下并非如此。这是一个我此前未曾发现有相关发表的结论。这些规则作为区域设置数据（locale data）内置于 ICU 中，而 ICU 是大多数操作系统、浏览器、运行时环境和数据库中广泛使用的 Unicode/全球化库。给定一个规则文件在特定输入下是否会终止，在数学上是不可判定的。

1. Transliteration Rules

A transliterator typically turns “é” into “e”, using a list of ordered rewrite rules: L { x } R > y ; The substring x is replaced by y when it sits between (optional) contexts L and R. The revisiting feature allows | in the replacement, which places the cursor inside the new text so that newly written material can trigger further rules.

1. 音译规则

音译器通常使用一系列有序的重写规则将 “é” 转换为 “e”：L { x } R > y ;。当子字符串 x 位于（可选的）上下文 L 和 R 之间时，它会被替换为 y。重访功能允许在替换中使用 |，它将光标置于新文本内部，以便新写入的内容可以触发后续规则。

Example: x > y | z ; za > w ; xa rewrites to y|za (cursor before z). The engine rescans and za matches, producing yw.

示例：x > y | z ; za > w ;，xa 会被重写为 y|za（光标位于 z 之前）。引擎重新扫描后 za 匹配成功，最终产生 yw。

2. 2-Tag Systems

To prove UTS #35 universality, we compile a 2-tag system (Post, 1943) into transliteration rules, a model proven universal (Cocke & Minsky, 1964). A 2-tag system has one production per letter. Each step removes the first two letters and appends the production of the first one. It halts when fewer than two letters remain.

2. 2-Tag 系统

为了证明 UTS #35 的通用性，我们将 2-tag 系统（Post, 1943）编译为音译规则，这是一种已被证明具有通用性的模型（Cocke & Minsky, 1964）。2-tag 系统中每个字母对应一个产生式。每一步操作都会移除前两个字母，并在末尾追加第一个字母对应的产生式。当剩余字母少于两个时，系统停止。

3. The Collatz Function

Our example is Liesbeth De Mol’s 2-tag system for the Collatz function (even n → n/2, odd n → (3n+1)/2): a → bc, b → a, c → aaa, on the unary word aaa...a. We prefix the word with a read marker M, which pins the machine to the front. When no rule matches at M, no rule matches anywhere.

3. Collatz 函数

我们的示例是 Liesbeth De Mol 为 Collatz 函数（偶数 n → n/2，奇数 n → (3n+1)/2）设计的 2-tag 系统：a → bc, b → a, c → aaa，作用于一元字符串 aaa...a。我们在字符串前加上一个读取标记 M，将机器固定在开头。当 M 处没有规则匹配时，任何地方都不会有规则匹配。

4. Correctness and Universality

At most one rule matches. There is exactly one marker. The letter after it selects the rule. ([abc]*) captures all remaining letters. One rewrite is exactly one tag step. The rule for letter x matches precisely when the marker faces x plus at least one more letter. The replacement constructs the next configuration. Halting corresponds.

4. 正确性与通用性

最多只有一条规则匹配。标记只有一个。标记后的字母决定了所选规则。([abc]*) 捕获所有剩余字母。一次重写恰好对应一个 tag 步骤。字母 x 的规则仅在标记面对 x 且后面至少还有一个字母时匹配。替换操作构建出下一个配置。停止条件是一致的。

5. ICU’s Rewrite Guard

ICU stops each transliterate() call after 16 rewrites per input code point (loopLimit = span << 4 in rbt.cpp; the Java port has the same guard). However, the specification itself defines no limit. The guard is ICU’s pragmatic addition to prevent infinite computation, as termination is undecidable.

5. ICU 的重写保护

ICU 会在每个输入码点进行 16 次重写后停止 transliterate() 调用（rbt.cpp 中的 loopLimit = span << 4；Java 移植版也有相同的保护机制）。然而，规范本身并未定义限制。该保护机制是 ICU 为了防止无限计算而添加的实用措施，因为终止性是不可判定的。

6. Rule 110

The runner is not limited to tag systems. Any rule file is a program. rule110.txt implements the Rule 110 cellular automaton in 14 rules. Cells are written . (0) and * (1). A head carries the previous two cells and rewrites each cell in place. One pass is one generation.

6. 规则 110

运行器不仅限于 tag 系统。任何规则文件都是一个程序。rule110.txt 用 14 条规则实现了规则 110 元胞自动机。单元格表示为 . (0) 和 * (1)。一个头部携带前两个单元格的状态并原地重写每个单元格。一次扫描即为一代。

7. Prime Numbers

primes.txt is Wolfram’s real-time prime-generating cellular automaton (A New Kind of Science, p. 640); 16 states (0-f) and 223 transform rules. The first cell after the fuel is 0 exactly at prime ticks.

7. 素数

primes.txt 是 Wolfram 的实时素数生成元胞自动机（《一种新科学》，第 640 页）；包含 16 个状态 (0-f) 和 223 条转换规则。燃料后的第一个单元格恰好在素数时刻变为 0。