Efficient Turing Machine Simulation with Transformers
arXiv:2512.00003v2 Announce Type: replace-cross 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…
