用更少推理步骤实现高效图灵机模拟，提升Transformer计算效率。
Efficient Turing Machine Simulation with Transformers
- 通过多队列图灵机构建高效模拟桥梁，减少推理步数。
- 每步模拟仅需O(s(n)^c)次思维链操作，且上下文窗口为O(s(n))。
- 证明稀疏注意力加固定几何偏移即可实现通用计算，适合理论研究者。
已知常量位宽的Transformer具有图灵完备性，但现有构造在模拟每个图灵机步骤时需Ω(s(n))次思维链（CoT）步骤，导致推理长度不切实际。本文通过证明任意(t(n),s(n))有界多带图灵机可被常量位宽Transformer以最优的O(s(n))长上下文窗口、仅O(s(n)^c)次CoT步骤/图灵机步骤进行模拟，其中c>0可通过增大Transformer头层乘积任意缩小。此外，我们的构造表明：固定几何偏移的稀疏注意力足以实现高效通用计算。证明的核心技术是利用多队列图灵机作为桥梁，提出一种更高效的多带图灵机同步多队列模拟方法，在更严格模型假设下同时优化时间和空间复杂度。
原文摘要 · Abstract (English)
Constant bit-size Transformers are known to be Turing complete, but existing constructions require $Ω(s(n))$ chain-of-thought (CoT) steps per simulated Turing machine (TM) step, leading to impractical reasoning lengths. In this paper, we significantly reduce this efficiency gap by proving that any $(t(n),s(n))$-bounded multi-tape TM can be simulated by a constant bit-size Transformer with an optimal $O(s(n))$-long context window and only $O(s(n)^c)$ CoT steps per TM step, where $c>0$ can be made arbitrarily small by letting the Transformers' head-layer product sufficiently large. In addition, our construction shows that sparse attention with fixed geometric offsets suffices for efficient universal computation. Our proof leverages multi-queue TMs as a bridge. The main technical novelty is a more efficient simulation of multi-tape TMs by synchronous multi-queue TMs, improving both time and space complexity under stricter model assumptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。