Unicode's transliteration rules are Turing-complete
3 days ago
- #Transliteration
- #Unicode
- #Computation
- Unicode UTS #35 音译规则在其无界自然语义下允许通用计算，这一结果此前尚未公开发表。
- 这些规则被广泛应用于 ICU 这一常见的 Unicode/全球化库的区域设置数据中，其在给定输入上的终止问题是不可判定的。
- 音译规则包含上下文、捕获组、量词和游标回访等功能，从而支持复杂的重写操作。
- 通过模拟科拉茨函数等模型，可以将二标签系统编译为音译规则，从而证明其通用性。
- ICU 实现了循环限制以防范无限计算，但规范本身并未定义此类限制。
- 实例表明音译规则文件可以作为程序运行，能够计算诸如规则 110 元胞自动机与素数生成等功能。
- 区域设置数据格式中无界重写能力带来了安全隐患，因为接受转换规则等同于接受代码执行。