Showing 2025Show all
2 papers · 1 filter
cs.CC2025
Efficient Turing Machine Simulation with Transformers
Qian Li, Yuyi Wang
Constant bit-size Transformers are known to be Turing complete, but existing constructions require chain-of-thought (CoT) steps per simulated Turing machine (TM) step, le…
cs.CC2025
Constant Bit-size Transformers Are Turing Complete
Qian Li, Yuyi Wang
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…