利用思维链 Transformer 高效表示算法

尽管思维链（CoT）模型被证明可模拟图灵机，但图灵机在算法分析中效率低下。本文探讨 CoT Transformer 能否高效模拟更抽象的 Word RAM 模型算法。研究证实，在有限精度及连续、混合架构下，CoT 仅需多对数级开销即可高效模拟任意 Word RAM 算法（如排序或 Dijkstra 算法）。相比之下，传统图灵机模拟需二次方开销。该结果确立了 CoT 在复杂算法执行上的理论高效性。