Efficient Turing Machine Simulation with Transformers
Abstract
Constant bit-size Transformers are known to be Turing complete, but existing constructions require $\Omega(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.
Cite
Text
Li and Wang. "Efficient Turing Machine Simulation with Transformers." International Conference on Learning Representations, 2026.Markdown
[Li and Wang. "Efficient Turing Machine Simulation with Transformers." International Conference on Learning Representations, 2026.](https://mlanthology.org/iclr/2026/li2026iclr-efficient-d/)BibTeX
@inproceedings{li2026iclr-efficient-d,
title = {{Efficient Turing Machine Simulation with Transformers}},
author = {Li, Qian and Wang, Yuyi},
booktitle = {International Conference on Learning Representations},
year = {2026},
url = {https://mlanthology.org/iclr/2026/li2026iclr-efficient-d/}
}