Ask, and it shall be given: On the Turing completeness of prompting

Authors: Ruizhong Qiu, Zhe Xu, Wenxuan Bao, Hanghang Tong
Primary area: learning theory
Keywords: Prompting, Large Language Model, Transformer, Expressive Power

Abstract:
Since the success of GPT, large language models (LLMs) have revolutionized machine learning and have initiated the so-called *LLM prompting* paradigm. In the era of LLMs, people train a single general-purpose LLM and provide the LLM with different *prompts* to perform different tasks. However, such empirical success largely lacks theoretical understanding. Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge. In this work, we show that prompting is in fact Turing-complete: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function. Furthermore, we show that even though we use only a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers. Overall, our result reveals that prompting can enable a single finite-size Transformer to be efficiently universal, which establishes a theoretical underpinning for prompt engineering in practice.

Decision: accept (poster)
Reviewer scores: 6, 5, 5, 6

Reviews and discussion:
<thread>
creation date:
1729898054115

thread_type:
official_review

<thread_object>
creator: reviewer_cbcs

<content>
summary:
This paper establishes and proves that prompting is Turing-complete: there exists a finite-size Transformer such that, for any computable function, there is a corresponding prompt that enables the Transformer to compute that function.
Additionally, the paper demonstrates that prompting is efficiently universal, meaning a single finite-size Transformer can approximate the computational complexity of the entire class of unbounded-size Transformers.

To support this, the authors introduce two-tape Post–Turing machines (2-PTMs) as a basis for constructing the prompt, chain-of-thought (CoT), input tokenizer, and Transformer model. They further prove that 2-PTMs are Turing-complete and nearly as efficient as standard Turing machines (TMs). Specifically, 2-PTM is able to compute from input x（x is within the domain of \psi) to \psi(x), within at most O(t(n)logt(n)), i.e., only logarithmic slow down over TM.

These results provide a foundation for characterizing the CoT complexity and precision complexity of the constructed Transformer. Specifically, prompting a single Transformer can compute any TIME2(t(n)) function within O(t(n)) CoT steps and any TIME(t(n)) function within O(t(n)logt(n)) CoT steps. Prompting a single Transformer can achieve the same precision complexity as that of the entire class of Transformers.

strengths:
The paper provides a theoretical foundation for prompt engineering. It is well-written, with a clear structure and logical flow, making it a challenging yet engaging read.

weaknesses:
There are a few minor typos to address. For instance, on line 158, the key map notation is mistakenly written as the query map notation, and on line 759, the first '1' should actually be '0'.

I have a question: does it make sense to use a one-hot representation as the embedding (lines 781–782)? Since the Transformer embedding layer doesn’t use one-hot encoding, this appears to leave a gap in the proof to me.

questions:
Does it make sense to use a one-hot representation as the embedding (lines 781–782)? Since the Transformer embedding layer doesn’t use one-hot encoding, this appears to leave a gap in the proof to me.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730704537411

thread_type:
official_review

<thread_object>
creator: reviewer_k74c

<content>
summary:
This paper demonstrates that a family of decoder-only transformers achieves Turing-completeness through appropriate prompting. The authors establish this by constructing transformers that can simulate a two-tape Post-Turing Machine (2-PTM), a model known to be Turing-complete. Their approach involves encoding 2-PTM programs and inputs into prompts, enabling the transformer to simulate the execution trace of the 2-PTM. A subsequent readout process extracts the final output of the 2-PTM from the transformer's output. The paper also provides complexity bounds for the chain-of-thought (CoT) steps required in the simulation, proving its efficiency.

strengths:
+ The paper presents a new reduction that proves Turing-completeness of transformers with hardmax attention.
+ The authors deliver a thorough construction and proof for their Turing-completeness result.

weaknesses:
- The paper lacks sufficient justification for the novelty of its results. The Turing-completeness of transformers with prompting appears to follow naturally from existing work. It’s well-known that a Universal Turing Machine (UTM) can simulate any Turing machine by encoding the machine as part of the input. Given prior work [1], which shows that transformers with hard attention are Turing-complete, it’s intuitive that a family of transformers can simulate a UTM. Consequently, encoding any Turing machine within a prompt for a transformer simulating a UTM to achieve Turing-completeness appears to be a straightforward implication.
- Regarding complexity, the simulation results presented do not appear groundbreaking. Previous work [2] establishes that there exists a UTM capable of simulating any Turing machine in $O(T(n)\log(T(n)))$ steps, given the machine halts within $T(n)$ steps. Since the simulation in [1] requires only a single transformer step per Turing machine step, it follows that [1]'s construction can also simulate within $O(T(n)\log(T(n)))$ steps. The authors should clarify why their new construction is necessary and how it extends or innovates beyond these established results.

[1] Pérez, J., Barceló, P., & Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research, 22(75), 1-35.

[2] Hennie, F. C., & Stearns, R. E. (1966). Two-tape simulation of multitape Turing machines. Journal of the ACM (JACM), 13(4), 533-546.

questions:
What is the advantage of using a 2-PTM instead of a standard Turing machine in [1]?

[1] Pérez, J., Barceló, P., & Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research, 22(75), 1-35.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714544453

thread_type:
official_review

<thread_object>
creator: reviewer_2gkz

<content>
summary:
This paper constructs a Transformer-like algorithm that, given an encoding of a particular two-tape Post-Turing machine, simulates the machine. The algorithm is "Transformer-like" in that it is a composition of a finite number of "layers," each of which has structure similar to that found in a Transformer (e.g., query, key, and value computations that feed into a (hard) attention mechanism). The authors conclude from this construction that "prompting is Turing-complete," i.e., that there exists a finite Transformer that can be prompted to efficiently simulate any program.

strengths:
This paper is clearly written, and the technical details appear to be sound. The construction of the particular Transformer for simulating 2-PTMs is clever.

weaknesses:
I am an outsider to this area, and am not confident in this evaluation. However, I found it difficult to understand the significance of this result. 

We, of course, already know that it is possible to unambiguously specify computations with strings in a finite alphabet. We also know that finite machines with infinite tapes can execute these computations. In some sense the "prompting paradigm" (use a string to tell a machine what we want it to do) is also just the "programming paradigm." So the real question is whether a Transformer can execute a program provided to it in its prompt, and it seems to me that the answer hinges on how you define "Transformer." As you vary the definition, you will be setting up different puzzles for yourself, regarding how to encode the various necessary operations (e.g., in this paper, Boolean logic, equality checks, farthest retrieval) within a "Transformer." Why is this particular model of Transformers interesting? 

It seems important for the model of the Transformer to reflect real-world Transformers in all essential respects; but in order to judge which respects are essential, more context is needed on what doubts or questions about (real-world) Transformers this research is meant to address. That is, a priori, why might someone *doubt* the existence of a Transformer that executes program instructions in its prompt? And does your theorem actually put those doubts to rest? For instance, if someone thinks Transformers are limited because they have finite context windows, this theorem will not dissuade them (it assumes infinite context windows). If someone thinks that somehow the "soft" nature of softmax attention limits Transformers' ability to correctly implement "hard" algorithms, this theorem will not persuade them otherwise (it assumes hard attention). And so on. What questions/doubts exactly is your theorem intending to settle? Is the model of Transformers that you propose sufficiently faithful to real Transformers to satisfyingly address those questions?

questions:
I would love to better understand what about this result you think might be surprising. Before you proved the result, did you have any doubt it would hold? What aspects of Transformers did you imagine might make them less than Turing-complete, when given infinite CoT steps and an infinite context window?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730789114763

thread_type:
official_review

<thread_object>
creator: reviewer_h1bs

<content>
summary:
This is a theoretical work whose main contribution is the proof that there exists a finite-sized transformer such that for any computable function $\varphi$ there is a corresponding prompt such that, when concatenated with an input $x$, the transformer generates an output which encodes the value $\varphi(x)$. To show this result, the authors use a new model of computations, called in the paper two-tape Post-Turing machines (2-PTMs), which extends Wang's basic machines and is inspired by the Hennie–Stearns theorem showing that any multi-type Turing machine (TM) can be simulated by a two-tape TM whose running time increases only by a logarithmic factor. The authors also provide bounds on the size of the output generated by the transformer, which depends on the size of the input and the time complexity of the multi-type TM computing the function.

strengths:
The computational power of Neural Networks, and especially of Transformers, studied in this work, is an important and interesting topic that has been studied for some time. The authors have shown new results in this field and improved previously known achievements, in particular those of Perez et al. (ICLR 2019 and JMLR 2021) and Merrill & Sabharwal (ICLR, 2024). While Perez et al. (2021) have shown that for any computable function $\varphi$ there exists a Transformer that computes the function, the submitted work proves that there exists a single finite sized (decoder-only) Transformer that, when fed with promptes corresponding to a function, is Turing complete. Moreover, the performance of prompting the single Transformer achieves the same precision complexity and almost the same chain-of-thought (CoT) complexity as the Transformers presented in previous works, which, however, were not universal.

weaknesses:
The topics discussed in the paper and the methods of proofs are not entirely new, and the main result, although it sheds new light on the issue of computability, is not groundbreaking in this field. Moreover, to claim that this work proves Turing completeness of prompting is in some sense an over interpretation of the achievements. First, although it is justified by the results of Hahn (2020) and others, a rather negative aspect of the results of this work is hidden in the fact that autoregressive generation has to process huge sequences of tokens (called in this and related works CoT). Second, to compute a function from the class TIME(t(n)), the constructed Transformer Γ needs $O(\log(n + t(n)))$ bits of precision. Thus, in this context, Γ is not universal in the sense that, for example, a Universal Turing machine is understood.

questions:
Please explain the aspect of universality of your construction mentioned above.

Could you please discuss in more detail what is the size of the constructed Transformer.

L.129: you write that you refer to the time complexity as the the time complexity on a random-access
machine (RAM). But this seems to be not true. Could you please explain this?

L.146: why is the embedding function, a function from $\Sigma$ and not from $\Sigma^+$ or $\Nat \times \Sigma$?

L. 158: You call: key map qry_{l,k}. It should be: key_{l,k}

L. 335: why do you define E(0) := ALALA1 and not as E(0) := ALA0ALA1 ?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731994394856

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
We sincerely thank all reviewers for their valuable time and thoughtful reviews. We appreciate reviewers' recognition that a theoretical foundation of prompting is intersting (h1Bs) and important (cbcS), that the proof has a thorough construction (2gkz, k74c), and that the paper is well written (2gkz, cbcS). We also thank reviewers for their constructive comments, which will further improve the quality of the paper and lead to interesting future directions. We provide our response below and have revised our paper accordingly. We warmly invite the reviewers for further discussion.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proves that LLM prompting is Turing complete, extending theoretical understanding to a common one-model-many-task setting of LLMs. I am not an expert in this area and lean on the reviewers for decision making. The reviewers appreciated the importance, novelty and technical correctness of the paper.