固定位宽的Transformer可模拟任意长度输入的图灵机。
Constant Bit-size Transformers Are Turing Complete
- 用队列机制的Post机器模拟变压器行为，实现恒定位宽计算
- 在足够长上下文窗口下，可处理任意长度输入的计算任务
- 为理解Transformer推理能力提供新视角，适合理论研究者
我们证明，只要上下文窗口足够长，任何运行于任意长度输入上的图灵机均可被固定位宽的Transformer模拟。这优于以往工作，后者需随输入增长提高模型精度或参数量。此外，我们证明复杂度类SPACE[s(n)]精确刻画了上下文窗口长度为s(n)的固定位宽Transformer的表达能力。方法基于对一种图灵完备计算模型——Post机器的模拟。Post机器可建模为带队列的自动机，其计算行为与Transformer天然契合。两者行为相似性可能为理解Transformer推理机制提供新洞见。
原文摘要 · Abstract (English)
We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer, as long as the context window is sufficiently long. This improves previous works, which require scaling up either the model's precision or the number of parameters on longer inputs. Furthermore, we prove that the complexity class SPACE$[s(n)]$ exactly characterizes the expressive power of a constant bit-size transformer with a context window of length $s(n)$. Our approach relies on simulating Post machines, a Turing-complete computational model. Post machines can be modeled as automata equipped with a queue, exhibiting computational behaviors naturally aligned with those of transformers. The behavioral similarity between transformers and Post machines may offer new insights into the mechanisms underlying the reasoning abilities of transformers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。