Universal computation is intrinsic to language model decoding
This addresses a foundational debate in AI about the computational limits of language models, showing their inherent universality, which is not incremental but a theoretical breakthrough.
The paper proves that autoregressive language models, even when randomly initialized, are intrinsically capable of universal computation, meaning they can simulate any algorithm on any input, with training primarily improving programmability rather than computational expressiveness.
Language models now provide an interface to express and often solve general problems in natural language, yet their ultimate computational capabilities remain a major topic of scientific debate. Unlike a formal computer, a language model is trained to autoregressively predict successive elements in human-generated text. We prove that chaining a language model's autoregressive output is sufficient to perform universal computation. That is, a language model can simulate the execution of any algorithm on any input. The challenge of eliciting desired computational behaviour can thus be reframed in terms of programmability: the ease of finding a suitable prompt. Strikingly, we demonstrate that even randomly initialized language models are capable of universal computation before training. This implies that training does not give rise to computational expressiveness -- rather, it improves programmability, enabling a natural language interface for accessing these intrinsic capabilities.