Constant Bit-size Transformers Are Turing Complete
This provides a theoretical foundation for understanding the computational limits of transformers, showing they are Turing complete without scaling precision or parameters, which is foundational for AI/ML.
The paper proves that constant bit-size transformers can simulate any Turing machine on arbitrary-length inputs with a sufficiently long context window, establishing that the complexity class SPACE[s(n)] exactly characterizes their expressive power.
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.