Insider Brief
- Large language models (LLMs) can function as universal computers, capable of simulating a Turing machine without external intervention or modifications, using autoregressive decoding, according to a study.
- Researchers demonstrated that the LLM gemini-1.5-pro-001 can apply 2,027 production rules, effectively simulating a universal Turing machine, highlighting the computational potential of these models beyond text generation.
- This finding suggests that LLMs could perform complex tasks typically reserved for classical computers, with implications for industries using these models in optimization, automation, and problem-solving.
A new study posted on arXiv suggests that large language models (LLMs), like the one used in the experiment, are capable of performing universal computation without requiring external intervention or modifications to their underlying structure. This finding could have significant implications for understanding the true computational power of LLMs, which are widely used in applications ranging from chatbots to code generation.
According to the study, these models, when used in a particular way, can simulate a universal Turing machine — a theoretical construct that underpins all computational systems.
The research team, which included scientists from Google Deep Mind and the University of Alberta, investigated a method called autoregressive decoding, a process where a language model generates outputs one token at a time, with each new token being influenced by the sequence that came before it. In most practical applications, autoregressive decoding has been limited by the context window, meaning the model can only consider a fixed-length sequence of text at any one time. However, this study takes the concept further by generalizing autoregressive decoding to handle much longer input sequences—potentially without limits.
Universal Computation and the Turing Machine
At the heart of this research is the concept of a Turing machine, a theoretical device that can perform any computation given enough time and resources. Named after British mathematician Alan Turing, the machine consists of a tape (representing memory), a head that reads and writes symbols on the tape, and a set of rules that determine how it moves and what it writes. Turing machines can, in theory, solve any problem that can be broken down into a sequence of simple steps.
In computational theory, a universal Turing machine is a special kind of Turing machine that can simulate any other Turing machine. This is essentially the basis for modern computers. The researchers sought to prove that a large language model could perform the same task. The idea that a language model, often thought of as simply a tool for generating text, might have the same computational power as a universal Turing machine is a key finding of the paper.
The researchers used a specific language model called gemini-1.5-pro-001. By leveraging a process known as extended autoregressive decoding, they showed that this model could simulate a universal Turing machine with a set of 2,027 production rules, which are instructions that dictate how the model processes inputs and generates outputs. The model was prompted with a specific set of instructions (referred to as a “system-prompt”) and then performed what is known as greedy decoding—a deterministic way of generating text by always choosing the most likely next token. This configuration allowed the model to simulate the operations of a universal Turing machine.
What Are Lag Systems?
To understand how this is possible, the researchers introduce the concept of a Lag system — an early computational model proposed in the 1960s. A Lag system operates on memory in a circular queue, where the memory content is rotated in cycles. This is important because it allows the system to access and update memory in a way that mimics the operations of a Turing machine. In the study, the researchers show that a large language model’s autoregressive decoding process can be viewed as a Lag system, which has long been known to be computationally universal. This means that, in principle, a Lag system can simulate any computational process, including a Turing machine.
By setting up the model to operate like a Lag system, the researchers were able to demonstrate that it can control memory access and update sequences in a manner that is functionally equivalent to a Turing machine. This finding bridges the gap between theoretical models of computation and practical applications of large language models.
Implications of the Study: Unaided Universal Computation
One of the broader implications of the study is the idea that language models might be more than just tools for generating text. The paper suggests that LLMs, like the gemini-1.5-pro-001 used in the experiment, could perform general-purpose computation—effectively acting as computers in their own right. While these models have already shown remarkable abilities in fields like natural language processing and code generation, the discovery that they can simulate a universal Turing machine could open up new possibilities.
This capability might allow language models to perform complex tasks without needing specialized external systems. In previous research, large language models have required external memory or additional control mechanisms to simulate advanced computational processes, but this study shows that the model can achieve computational universality unaided.
Practical Applications and Future Work
Although this study is largely theoretical, it could have practical applications in the future. For instance, companies currently using LLMs for tasks like automated customer service, code generation, or text analysis might find new ways to leverage these models for more computationally intensive tasks, such as solving complex optimization problems or running simulations.
This could make LLMs even more valuable across various industries.
However, the researchers also acknowledge that their findings are just the beginning. While the study shows that this specific language model is computationally universal, the researchers believe that many other models could also have this capability. Verifying this for other models, both open-source and proprietary, will require further work. Moreover, the study suggests that the current rule set used to simulate a Turing machine could be simplified, which might make it easier to verify the universality of other models in the future.
The research team included Dale Schuurmans, of Google DeepMind and the University of Alberta; Hanjun Dai1, of Google DeepMind and Francesco Zanini, of the University of Alberta.
