Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management

Guanyu Cui, Zhewei Wei, Kun He

Many works make the eye-catching claim that Transformers are Turing-complete. However, the literature often conflates two distinct settings: (i) a fixed Transformer system setting,…