Ask, and it shall be given: On the Turing completeness of prompting
Authors: Ruizhong Qiu
Zhe Xu
Wenxuan Bao
Hanghang Tong
Venue: ICLR 2025 Poster (2025)
Keywords: Prompting
Large Language Model
Transformer
Expressive Power
Primary area: learning theory
TL;DR: We show that prompting is 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.

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.

Published as a conference paper at ICLR 2025
ASK, AND IT SHALL BE GIVEN: ON THE TURING COM- PLETENESS OF PROMPTING
Ruizhong Qiu, Zhe Xu, Wenxuan Bao, & Hanghang Tong University of Illinois Urbana- Chammaaan (rq5, zhexu3, wbao4, htong) é wlinoiii edu
ABSTRACT
Since the success of GPT, large language models (LLMs) have been revolutioniz- ing machine learning and have initiated the so-called LLM prompting paradigm. In the era of LLMs, people train a single general-purposs 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 theoret- ical study on the LLM prompting paradigm the best of our knowledge. In this work, we show that prompting is in fact furing-complett there exists 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, 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 single finite-size Transformer to be efficiently universal. which establishes theoretical underpinning for prompt engineering in practice.
INTRODUCTION
The mainstream architecture of large language models (LLMs; e.g.. OpenAl 2024
Anthropic [224]]
Metal 2024) Google 2024) is Transformers (Vaswani et al.] (017). There has been a series of
theoretical studies on Transformers under realistic abstractions (Pérez et al.
2019 Bhattamishra
cct al. 2020 Hahn 2020 Pérez et al. 2022 1| Hao et al. 2022 Liu et al. 2023a Chiang et al. [023]
Merril & Sabharwal [2033] Roberts 2023 Merrill & Sabharwal 2024a bj Hou al.) 2024| Li
ct al. 2024). For example, Pérez et al. (2021) have shown that the class of all Transformers with
hardmax attention is Turing-complete: for any computable function to E (lM)) there exists a Transformer that computes yo using ((t(n)) thain-of-thoughhe (CoT: Wei et al. 2022b) steps and
(log(n + t(n))) precision on length-n inputs; Merrill & Sabharwal (202a)) have later improved the CoT complexity to ((t(z)) for (IME(t(n)) functions. These works have finely characterized the capacities and limits of Transformers under the classic one-model-one-task paradigm.
Nevertheless, existing theoretical studies fail to align with the LLM prompting practice (i.e., one- model-mann-tasks)) In the era of LLMs, people train single general purposse LLM and provide the LLM with different prompts to perform different tasks. Since the success of GPT (Brown et al., 2020 the LLM prompting paradigm has revolutionized machine learning (L.iu al. 2023b). For example, a bonus capability arising from prompting is zero-shot learning [Wei et al. 2022a): when provided with suitable prompts, LLMs can even perform novel tasks not present in their training cor- pora. Such empirical success calls for theoretical understanding of the LLM prompting paradigm:
Fundamentally, how powerful is the LLM prompting paradigm?
We answer this call and present the first theory the LLM prompting paradigm the best of our knowledge. In this work, we show that prompting is in fact Tluring-compll there exists a finite-size Transformer such that for any computable function, there exists corresponding prompt following which the Transformer computes the function. Furthermore, we show that prompting is not only universal but also efficiently universal: even though we use one finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers.
Main contributions. Our main contributions are informally stated follows:

---

Published as a conference paper at ICLR 2025
Expressive power. We show that prompting is T'uring-complae there exists a finite-size Transformer I such that for any computable function ip, there exists a finite prompt a such that for any imput æ. the Transformer I" computes p(x)) following the prompt क.. Importantly, our constructed Transformer I' is independent of the function yo, the prompt T is independent of the input æ; and the input can be arbitrarily long.
Simple construction. In fact, it is not hard to deduce the existence of such Transformer by combining Theorem of Hennie & Stearns (1966) and Theorem 3.4 Pérez et al. (2019), but explicitly constructing the Transformer via that approach is cumbersome. In- stead, we provide a simple constructive proof, which makes it easy to further study the properties of the construction such as CoT complexity and precision complexity.
CoT complexity. We show that our I' can compute any (IME)(t(n)) function within ((t(n)) CoT steps and can compute any TIME(!(n) function within O(t(z) log t(n)) CoT steps for any length-n input. Notably, our result shows that even single Transformer can still achieve nearly the same CoT complexity as the class of all Transformers does.
Precision complexity. We show that our I" can compute any TIME(((n)) function within (log(n + {(n)) bits of precision for any length-n input. Notably, our result shows that even single Transformer still achieve the same precision complexity as the class of all Transformers does. In particular, can decide any language within log preppiiiiiion.
1.1 RELATED WORK
In modern machine learning (Wei al., 2024
Chen al.) 2024 Liu al.,
2024a b 2023c
Quu 2024
iet al. 2024b a 2023; 2022 Xu et al. [024 Qiu & Tong 2024; Zeng et al. 2024 Lin et al.
Yoo et al. 2025| 2024] Chan et al. 2024 Wu al., [024] He et al. [024]] Wang al.) 2023),
Transformers have nowadays become a mainstream architecture. Existing theoretical studies on Transformers fall under the classic mne-model-one-tast paradigm: they need construct different
Transformers for different tasks. There are two lines of related work: (i) when at most O(1) CoT
steps are allowed, it has been shown that Transformers are capable but far from Turing-complett
(Hahn 2020 Hao et al.] 2022 Liu et al.) 2023a| Chiang et al., 2023; Merrill & Saabharwa] [023]
2024b; (ii) when more CoT steps are allowed, it has been shown that the expressive power of
Transformers increases with the number of CoT steps (Pérez et al. 2019; Bhattamishra al. 2020
Pérez et al., 2021 Roberts 2023 Merrill & Sabharwal [224a]] Hou et al.) 2024 Li et al.) 2024)
Besides that, there have recently been studies on the learnability (Malach) [003]] Grau-Moya al.,
2024) and the in-context learning capability (Akyürek et al. 2022) von Oswald et al.) 2023 Zhang
al. 2024 Ahn et al. 2024 Vladymyrov al. 2024). Nevertheless, existing work studies the
LLM prompting paradigm (i.c., the one-model- mooodel-many-tskee paradigm), Our work is the first to bridge
this gap the best of our knowledge.
1.2 TECHNICAL OVERVIEW
A core step of our constructive proof is to construct a new model of computation (called 2-PTMs) that can be easily encoded into a prompt using a finite alphabet. Furthermore, we show that 2-PTMs are not only Turing-complete but also nearly as efficient as Turing machines.
Theorem (informal version of Theorem 4.1 Any TIME(t(n)) function can be computed by a 2-
PTM within ((((n) log t(n)) steps.
Given any computable function y, we encode its 2-PTM into a prompt π T. Then, it remains to construct a Transformer I' that can execute 2-PTMs. Since it is known that Transformers without CoTss are not universal (Hahn) 2020), the Transformer I' needs to use CoT steps to execute 2-PTMs. Specifically. we use CoT steps to record the execution steps of the 2-PTM so that the Transformer can restore the state of the 2-PTM at any step. This establishes the CoT complexity of I'
Corollary (informal version of Corollary 4.5). Our constructed T compute any TIME(((M)
function within (t()n) log (m)) CoT steps.
To incorporate input æ into computation, we use O((z)) CoT steps to emulate an imaginary process of writing the input onto tape of the 2-PTM. This implies the precision complexity of T.
Corollary (informal version of Corollary 4.7). Our constructed I' can compute any TIME(t(n))
function within Ollogin + ((n))) bits of precision.
2

---

Published as a conference paper at ICLR 2025
Finally, we construct decoder-only Transformer that achieves the desiderata above by leveraging ReLU activation, layer normalization, and causal attention.
2 PRELIMINARIES
Let e denote the empty string. Given an alphabet Σ, let 5d (n 2 0) denote the set of length-n strings over Σ, let E = Un.0 Σ" denote the set of all finite strings over E, let E == Un>1 Σ" denote the set of all non-empty finite strings over Σ, and let I denote the set of all countably infinite strings over Σ. Each symbol in called a token. For string a E Σ", let |a:| denote the length of the string, and let x denote repeating the string times. For two strings æ, y E Σ let a y denote their concatenation. Given string v = T 31 1.....40 ".---//-11 E Σ", for an index i E 2, let Jy denote the (i mod lar))-h token of æ;; for indices i, j E Z with i mod |ae| S j mod |ar] let Zyy denote the substring Ty mod [a]] Tit mod [m])+1 Li mod lx))--1-
2.1 THFORY OF COMPUTATION
Turing machines. Turing machines (TMs; Turing 1937a) are an abstract model of computation that defines the notion of computability (Church 1936 Kleene 1936: Turing 1937b). An m-tape TM is defined by septuple (Q, Istart, Phalt: 2, m, o) where Q is the finite set of states, qannt E Q is the initial state, Phah is the halting state, Σ is the finite alphabet of the tapes, - E Σ is the blank symbol,
m E N is the number of tapes, and ō (Q) \ {ghate }) x 2 Q x (Σ x {,, S, R is the transition function (L: left: S: stay; R: right). See, e.g.. |rora & Barak (2009) for details. By the Church-
Turing thesis (Church 1936 Kleene 1936 Turing 1937b). function o dom o > {o, 1}" is said to be computable there exists a TM that computes ((x) ) for all inputs x E dom (p.
Shannon (1956) has shown that any TM M over any alphabet can be simulated by a TM M' over the binary alphahet (o, 1 with .. = 0 (although M' uses more states). Hence, we will assume that TMs have binary alphabet for simplicity throughout this paper.
Time complexity. Let n denote the length of the input. A function t(n) : NN -> R4 is said to be a complexity function iff t(n) is non-decreasing and either t(n) is constant > 1 or t(n) + oo as n + 0o. In this work, we refer to the time complexity as the the time complexity on a random-access machine (RAM) unless otherwise stated (e.g., when working with TMs). If ((((n) is complexity function, let TIME.. (t(n2) denote the class of functions that can be computed by an m-tape TM within (((nn) steps; let TIME(t(n)) == U TIME (t(n)) denote the class of functions that can be computed by TM within (t(nn)) steps; and let P C TIME(poly(n)) denote the class of (indicator functions of) languages that can be decided in polynomial time.
2.2 NEURAL NETWORKS
ReLU neural networks. A ReLU neural network + : :. + RR is composition vi := d Rd-11
2/ of basic operations 1) : 1R
O...................... 1) where each basic operation (z)
(z E IR*)) is either an affine map (2) = Wiz b, (W. E R xer, b, E IR++)), an entry-wise
ReLU activation (z) = max 2z 0} (Fukushima 1969) with et+1 = et, or a layer normalization
(Ba et al. 2016) with e141
Decoder-only Transformers. Mainstream LLMs are based on decoder-only Transformers (Radford et al. 2018). Given a finite token alphabet Σ, a decoder-only Transformer r Σ+ -> Σ (with greedy decoding) is composition I == arg max of out Ti.- ..... To I emb consists of an embedding layer I'emh D + (Rd)), causal-atlention Transformer layer ri (R2))+ + (Rd)+
(1=00 O,..., L 1), and an output layer Tous : Rd I token embedding is a map emb Σ Rdd and positional encoding is map pos: N + Rdd Following the common practice (Vaswani al. 2017), given the input token sequence e uy -.. U/ul-1 E+, the embedding layer Tomb adds a positional encoding pos(i) to each token embedding emb(u:):
Zo.i == cmb(u:) + pos( i i= 0...... | 1,
where pos is computable function. Following existing theoretical works Pérez et al., 2019 Hao et al.] [022] Merrill & Sabharwal] (2024a), we use hardmax attention as a realistic abstraction of softmax. Given an R sequence 8, if the maximum value of appears & times, then one has
3

---

8ik,iij simr, Published as a conference paper at ICLR 2025
hardmax,(s) if 8; equals the maximum value and hardmax,(s) 0 otherwise. Each Transformer layer i has Hj attention heads followed by ReLU neural network Φi IRd Rdd Each attention head k has a query map Q I + Rd a key map key k R² + Rd a value map val,, R Rd, and similarity map simi, RR R (k O,... ReLU neural networks. The similarity scores between two tokens ey and Uj are
..... HH. 1), all of which are
key (
decoder-only Transformer layer Ii is computed via causal attention and residual connection:
M1 Σ
11+ = 21,1 + tb
hardmax, ($L,,, ,L.,,,,,,... vall, xall
(3)
==
The output token is greedily selected according to the final outputs of the last token U/ul-1i
[(v)
arg max ouu (=
(4)
cE
where the output layer Tou is ReLU neural network.
Given Transformer 7, let generater Σ - Σ+ denote autoregressive generation using F. Specifically, let E E+ denote the input sequence and E Σ" the (current) output sequence. Ini- tially, y is an empty string. each generation step, we append I' [(w--y) y) to to The generation process ends once the last token of is a so-called stop token E Σ, and we define generate ( at last. It possible that generation never ends, in which case we have y E Σ", The autore- gressive generation procedure is formally presented in Algorithm [I] A Transformer is said to use log-precision for a computable function yp if the intermediate computation of all generation steps uses Ollog n) bits of precision for every length-n input of function yo (Merrill & Sabharwal 2023).
TURING COMPLETENESS OF PROMPTING
Theorem 3.1 (Turing completeness of prompting). There exist finite alphabet Σ, a finitesiize
decoder-only Transformer I' x Σ. and coding schemes tokenize {0.1]* + 2n and readout: 2 + {0, 1} with which prompting is Turing-complete: for every computable function p : dom & > {0, 1}" with dom vp C f0, 1)", there exists a prompt n E Ex+ such that for every input x E dom yp, generate,(T. tokenize (x)) computes a finite CoT, and readout(generaate
ttoenize(x))) <(x).
Here, E, I, tokenize, readout are independent of ip; To is independent of æ; for any input x E (o, 1),, tokenize and readout run O((z)) and O(1g(=))) time on RAM, respectively.
Our Theorem 3.1 shows that prompting can enable a single Transformer to be universal and estab- lishes theoretical underpinning for prompt engineering in practice. Note that CoT is necessary for Turing completeness because it is known that Transformers without CoT's cannot even compute the parity function (Hahn 2020). As CoT typically contains more information than the answer ((x) alone, we need map readout n + {0, 1 here to extract the answer, resembling the fact that humans need read out the answer from the generated COT.
Furthermore, to elucidate the technical non- con-iriviality of our Theorem 3.1 we remark that our Theo- rem 3.1 has ruled out trivial possibilities:
Memorization? It is impossible that the Transformer F simply memorizes all computable functions, because there are infinitely many computable functions while I' has only finite size (i.e., has a finite number finite-bit parameters).
Self-answerigg? It is impossible that the prompt n. simply reveals the answers for all possible inputs, because there can be infinitely many inputs while the prompt is finite.
Tautology? It is impossible that I simply restates π. tokenize(z)) and lets tokenize or readout compute (xxx) instead, because the time hierarchy theorem (Hartmanis & Stearns 1965) implies that a computable function &p in general can require more than [0 [ ( (x)]]] time while tokenize and readout run in only O([z]) time and O(1((z))) time, respectively.
Following prior work (e.g., Pérez et al. 2019) we assume that every arithmetic computation in I'is exact.
4

---

Published as a conference paper at ICLR 2025
constructive. In the rest of this section, will present the core structions in our proof, including the prompt, the CoT steps. the input tokenizer, and the Transformer. Due to space limit, the complete proof is deferred to Appendix B
Our proof of Theorem 3.1
3.1 CONSTRUCTION OF PROMPTS
In this subsection, we show how to construct prompt n for any given computable function s-- The basic idea here is that we let the prompt encode a formal description of the function and later construct a Transformer that can exccute the description. The construction of the Transformer is deferred to Section 3.4
As computabilityy means that there exists TM that computes s, one might seek encode the TM into the prompt. Unfortunately, a TM can have an unbounded number of states and an unbounded number of tapes, but we are only allowed construct all prompts using a single finite alphabet Σ and to execute all prompts using a single finite-size Transformer. Even though one can use sophisticated schemes encode TMs (Turing 1937a). it remains highly non-trivial to construct Transformer to efficiently execute such encoded TMs.
Hence, instead of working with TMs directly, here we want model of computation that (i) can be easily encoded by single finite alphabet, that (ii) is still Turing-complets and that (iii) is nearly as efficient as TMs. Although a possible approach
to use an imperative model of computation such as Wang machines (Wang. 1957) and Davis Sevvi--Sgal--aee Oigal-Weyuker 's Post-Turing machines (DSW- PTMs: Davis et al. 1994), it is still unknown how to efficiently simulate arbitrary TMs using Wang machines or Davis- Sigal-
Post-Turing machines. This suggests that these models of computation might not be the best candidate for constructing the prompt.
To fulfill our desiderata, we propose new imperative model of computation that extends Wang ma- chines and DSW-PTMs. Inspired by the Hennie-Stearm theorem (Hennie & Stearns 1966), we let model of computation use two bi-infinite tapes A and B. Each tape has infinitely many cells over the binary alphabet {o, 1} and a head pointing to a cell. We call this model two-tape Post-Turing machines (2-PTMs). A 2-PTM is defined by finite instruction sequence & (to, 441-1)
where each instruction 1y (0 S |c|) is one of the following:
#: halt;
rL (T E B)): move the head for tape one cell left, and go 1j+1
7B (T E {A, B)): move the head for tape one cell right, and go to 1j+1;
70 (T e (A, BA)) write 0 to the pointed cell of tape т, and go to lj+1i
r1 (T E B):: write 1 to the pointed cell of tape т, and go to 1j+13
T! (A. B]; k + j): if the pointed cell of tape 7 is 0, go to 4x else, go to lj+13
. T?x E [A, k # j): if the pointed cell of tape 7 is 1, go to 4x else, go to lj+1-
Let I denote the set of all possible instructions. Before execution, the input is written to tape A, and the head for tape is pointing to the leftmost cell the input (called cell 0). All blank tape cells are filled with 0. Then, execution starts from instruction tu and halts upon instruction 4, and the output the content left on tape starting from cell O. We will show in Section 4.1 that 2-PTMs are not only Juring-comple
but also nearly efficient as TMs.
Next, we describe how to construct a prompt for a given computable function. Recall that 2-PTMs the binary alphabet {o, with blank symbol being o. To distinguish the input symbol 0 and the blank symbol 0, we employ Shannon's 's encoding $ {o, + [0, (Shannon, 1956) to translate inputs and outputs of computable functions:
S(E) = E, S(0) 10, S(x) == ((x)) ... ... S(z)))))) x E 10,1}*
S(1 11;
(6)
(7)
Thus, we identify 00 as the blank symbol. Note that Shannon's 's encoding S injective, and that both S and its corresponding decoding 5-1 are computable in linear time. Since the class of 2-PTMs is Turing-complete then given any computable function ip, there exists a 2-PTM & E I that computes S(((())) from S(x) for all E dom s.. It remains encode into prompt TT.-
We will define map P N x I + E" to encode each instruction and let the prompt be the concatenation of P(j, 15), where the alphabet E will be specified later. For instructions rL, TR,
5

---

Published as a conference paper at ICLR 2025
TO, r1, can simply create corresponding token in E for each of them:
p(j,)) = if iy is one of 7L, TR, rO, r1.
(8)
For instructions r and T2k, since k can be any natural number, we can no longer create token for each & because otherwise the alphabet I would be infinite. Instead, to help the Transformer to exccute the prompt, we use a unary encoding w.r.t - j:
p(.))= = 0 -ok @ if 1 on and ls j, (G. @
o (T1,
(9)
14 = ox and > j.
where we create seven auxiliary tokens A!, B,, A?, B?, -,,, ,, @ E 2 to be used by the Transformer. Finally, we construct the prompt as
T ==
P(O, (0) ... -([e - 1, 1,4411)
(10)
where we create two auxiliary tokens S Σ to be used by the Transformer.
Example. 2-PTM for deciding the DYCK language (Schützzenherger 1963
A? AOAAAAAAA ARARA1ARBLB 13 A1 ARA? ? 19BBBB 21 BLB! 20ARBB gALARARA AOALAOALA 2 ARARA1 #,
and its corresponding prompt is
0A0ALOOALL ---- BAA.:AAAAAAAL0------AAAABBB--111 (ARARKLABBLL7
MOOLLOOAAA 01RIBALSS.
3.2 RECORDING EXECUTION IN COT STEPS
is known that finite-size Transformers without CoT steps are not universal HHahn achieve Turing completeness, here we leverage CoT steps to record execution steps of the 2-PTM & so that the Transformer can restore the state of e at any execution step. In this subsection, we focus on the case where the input is empty; we will describe how to incorporate the input in Section 3.3
2020). To
Let denote the current instruction, and let Ca2 Og denote the pointed cell of tapes and B, respec- tively. Note that each execution step can be summarized as a quadruple (j, L Ca, GB), where ij is the current instruction, and e and Oş are the currently pointed cell of tapes A and B, respectively. We will define a map C N x I x {o, 1]2 + E" that maps each execution step to one or more CoT steps. If ly is one of 4, rL, TR, r0, r1, we simply use a single CoT step to record ey:
C(j. Sy, Ca. 02) := ij If iy is ! a or ?kk, we record whether the go-to condition is satisfied or not:
if Ej is one of H, TL, TR, TO, T1.
(11)
if ; = T k and c, + 0;
if f T ks C. 0, and k: j;
if = T !, G, = 0, and > j;
(12)
if = T? and C, # 1;
if t T T?K, C, = 1, and k: j;
if ij T2,, C. = 1, and k: j;
where we create two auxiliary tokens / E E to indicate whether the go-to condition is unsatisfied or satisfied, respectively. The execution step stops once reaches the halting instruction #.
Finally, we append the output plx) after the execution steps in the COT. We create a new auxiliary token Σ to mark the beginning of the output and reuse the token output, and we put the output p(x) E {o, 1} C E between and $. Hence, we define readout as extracting the part of the CoT between : and (see Algorithm 2 By construction, the number of CoT steps is proportional to the number of execution steps plus the length of the output.
Σ to mark the end of the
Example (cont'd), d). An empty input e is in the DYCK language. Its corresponding CoT steps are:
/AOALAOAL/ AALLAAAAAAARAAAAARBB//L A1 11.
To recap, we have created a finite alphabet of 23 tokens all together:
: == (t, AL, BL, AR, BR, AO, BO, A1, B1, A!, B!, 1, A?, B?, ,, +, ,,,,,,,,//,,,,,,0,
(13)
From now on, will omit delimiters for conciseness when there is ambiguity.

---

Published as a conference paper at ICLR 2025
3.3 CONSTRUCTION OF INPUT TOKENIZER
In this subsection, we describe our input tokenizer tokenize: {0, + Σ", which is independent of the function yp and can encode any input æ E [0, 1]" without changing the prompt T.. Although it is possible to introduce additional auxiliary tokens to represent inputs, here we provide a simpler construction that makes use of only the existing tokens in 2.
The key idea here is to use CoT steps to emulate an imaginary process of writing the input to tape We will define a map : {0, 13* 2 that encodes an input into CoT steps. Since 2-PTMs assume that the head for tape A is initially pointing to the leftmost cell of the input, we write the input from right to left onto tape A. Hence, for each bit 2; of the input æ, we write its Shannon encoding S(x;)) from right to left onto tape A:
OO) = ALALA1,
E(1) = ALA1ALA1.
(14)
For the entire input, we concatenate the CoT steps of each bit from right to left:
((x) := E(x a -|-1) E(xo),
{0, 1)
(15)
Intuitively, E(x) represents execution steps of an imaginary program that writes S(x) onto tape A.
To ensure that the tape-A head is at cell O after writing the input, we first move the tape-A head [S()) = || steps right. Hence, we define the CoT steps for writing ((x) as Z (0, + E-
((x) == AR E(x),
x E {],
(16)
Nevertheless, there is a caveat: 2-PTM should start from 40. but these extra CoT steps Z(x)
will confuse the Transformer into starting from 4[Z(=]]- To address this caveat, our input tokenizer tokenize additionally employs an imaginary go-to step to let the Transformer go back to 4. Follow-
ing Equation 12), re-use =; -, to construct the imaginary go-to step:
lokenize(x)) == fc ((x)) .= - B
if x C,
(17)
if x 7
Example. Since input 01 has Shannon encoding S(01) = 1011, it is tokenized as
tokenizo(O1) = ARARARARALAIALLAAAI
e
3.4 CONSTRUCTION OF TRANSFORMER
In this subsection, we sketch how to construct a decoder-only Transformer that executes prompts through CoT steps as described in Section 3.2 Due to the space limit, we only present three core operations to used by / here and defer the detailed construction to Appendix
Boolean algebra via ReLU activation. Let ReLU(z) == max(2, 0} denote the ReLU function. Boolean algebra is a basic building block our Transformer for, e.g., checking the go-to condition. A core operation in Boolean algebra is the A operation. Here, we implement A via ReLU activation:
u A U = ReLU(u++ uu 1),
u, 13.
(18)
Together with negation ~V = 1 - v. they can implement all other Boolean operations such as V -((-u) (-e)) and u + (u (-w)) + ((-u) A v).
* Equality check via layer normalization. Let LN(z) := || - denote layer normalization
(LN). When checking whether a tape cell has been written or not, we will need an equality check between two real numbers: NotEqual RR2 > {0. 1} where NotEqual v) | (u, E R). Since NotEqual is not a continuous map, it cannot be implemented using only affine maps or ReLU activation. Instead, we implement NotEqual via layer normalization as follows:
NotEqqullu, (u, v) ReLU(LN(( u)) ReLU(LN((: - u)). U. E R.
(19)
Farthest retrieval via causal attention. A core operation to be used by the Transformer I' can be abstracted as follows: Given number sequence e (vo,..., "//ojj,,,)///)) with v; E (-1,0,+1) for all i, find the smallest i such that Ej=o fy - Uj. However, since causal attention is average

---

Published as a conference paper at ICLR 2025
rather than sum, it cannot even compute == U for arbitrary i. It can compute the average Ej= V/ for every i, but Σj= 1/ ー== 1 by does not mean Ee= E ey-
To bypass the mismatched coefficients 74T and |o) we use LN to remove the averaging coefficient
I+ First, we let every token attend to the initial token at i = 0 to compute *II and compute
Ei=o 1 T
o uy) V Vo 1,) )
Σnz V3
1 i+1 11+1 u, = LN
(20)
If Σ 2j= = دبر 1/. we have u. 1|0|-1 = 1; if مز= 1jj # L==0 U/j we have u.! u/o
1. Thus, we can add 1/ 1 to the query map qry and add u, to the key map key in attention to retrieve an with Σj 1/ -
2 1
remains to retrieve the smallest such i via causal attention. Since is E {-1, 0, +1}, then note that if u wp|-1 < we in fact have
1
|0| +
1
u 1
(21)
| +1
v 10 2
V(Di
+ +)2 +1 V(la + +1)
1 ( + 1) +1
= 1 Ω
(22)
Vlul2 + 1 (lo) + 1) +1
This motivates us to use the following quantity, which can be computed in positional encoding pos:
(i + 1) + 2) +1
P := 1i++))+IV( 2)
2
(i 1)4
(23)
Note that if u!! u o| = and u. 11|1-1 < 1, we also have
u 1p| j ++
P|ll-
I 2 11 + P|o| - < 1 = un 1 < un 24 11 +
Plo
(24)
i
Therefore, we can retrieve the smallest i with u 1/1| = 1 by using query vector 1//p/-1,P/p) -1) and key vector (u:; ) in causal attention.
4 COMPLEXITY BOUNDS
We (i) show in Section 4. that 2-PTMs are Turing-compler and nearly as efficient as TMs and (ii) use this result to characterize the complexities of our constructed in Sections 4.2 & 4.3 Through- out this section, let I(n) denote complexity function. Following the convention in complexity theory, we allow different computable functions to have different constant factors in big O.
4.1 EFFICIENT SIMULATION OF TMs BY 2-PTMS
Since 2-PTMs are essential component of construction, we need the complexity bounds of 2-PTMs to analyze the complexities of r. While Wang machines and DSW-PTMs suffer from a polynomial slowdown over TMs (Neary al. (014), we show that our 2-PTMs in fact has only at most a logarithmic slowdown over TMs. Let T(ME2PTM(((T)) denote the class of functions that can be computed by 2-PTM within (t)(n)) steps.
Theorem 4.1 (efficient multi-tape simulation). TIME(t(n)) C FTME2 log (())-
Theorem 4.1 shows that 2-PTMs are Turing-complete and nearly as efficient TMs. To prove it, we need the following Lemma 4.2 to establish a relation between two-tape TMs and 2-PTMs.
Lemma 4.2 (two-tape simulation). TIME, (+(n)) S (1M)))PM(t(n)).
Proof of Lemma 4.2 For any computable function o E TIME)(t(n)), there is a two-tape TM M =
(Q. Qstartt Chalt. 0 1 - m 2, that maps S(x) (((((x)) within time O(t(n),, according
to Shannon (1956). Suppose w.l.o.g. that Q = {0, 1......... K} (K E N,) and that Quart 0, 9ualt =
K. We will construct 2-PTM of length |r| 27K 1 that simulates M within time O((nn).
8

---

Published as a conference paper at ICLR 2025
Recall that 8 (Q) (9han))
Q (f0, 1} x {L, (L) We use exactly six instructions
(ig (3)))))dd)) to simulate each transition (q', c2 da. d2 dz), where q' E Q. ca. cá E {0, 1), da. da E
{L, R). If da, da + S, we let
la' Mla..d ( (Ac4, Ada, Brg, Bdg, A 270', A3270')
(25)
If d2 = S or de S, we can replace the corresponding Ad, or Bdl with Arg or B respectively, so that (gy d4, d. de,)) still has exactly six instructions.
Then for each q E Q {gaat), we use 27 instructions to simulate its transition rules:
277 = (A327 B8274+8 (86 (g.00,1) 27 (.0. (6(..1.))
(26)
For the halting state ghalt = K, we use one instruction 127K == # to simulate it. Since simulates each transition of M by ((1) steps, then also has time complexity O(t(n)).
Due to space limit, the proof correctness of & deferred to Appendix
We now ready to prove Theorem 4.1
Proof sketch of Theorem 4.1 Let E TIME(t(n)). Then, there exists a TM M that computes within T(n) O(t(n)) steps for every length-n input.
Case 1: There exists E N such that (mo) < no. Thus, the behavior of the TM M depends only on the first T(no) no bits of the input. Hence, further increasing the length of the input does not change the behavior M. Therefore, a tighter time complexity (n) of M is
f(m) & ((m)) = O(1), Vn E N.
(27)
This implies that & E TIME>(1) S. 2 PTM(1) TIME log (n)).
Case 2: T(n) n for all E N. Then by the Hennie-Stearns Stearns theorem (Hennie & Stearns 1966).
(TME,(((m) log (n)).. Therefore, by Lemma 4.2
o E (tM))(t(n)) log ((n)) S TIME2PMM(((() log
(28)
follows from the above two cases that TIME(((n)) S TIME log t(n)).
Theorem 4. shows that 2-PTMs have only at most logarithmic slowdown over TMs. In subsequent Sections & 4.3 we will use Theorem to characterize the CoT complexity and the precision complexity of our constructed l'.
4.2 COT COMPLEXITY
In this subsection, we analyze the CoT complexity of our construction. We will show that our con- structed / can compute any TIME)(t(n)) function within ((t(n)) CoT steps and any TIME(t(n)) function within O(t(n) log t(n)) CoT steps for any length-n input.
Definition 4.3 (CoT complexity elass). Let CoT (t())) be the class of functions that our con- structed Transformer I can compute within O(t(n)) CoT steps.
Lemma 4.4 (CoT complexity for 2-PTMs). (t( S CoTr(t(n)).
Proof sketch. For any &p TIME (t(n)). since prompt π.. has length | O(1), then by Section 3.2 each #, T<, T>, r0, 71 takes = O(1) CoT step, and each T T2k takes at most O( 0(1) CoT steps. This implies that (IME) C CoTr(
O
Corollary 4.5 (CoT complexity for TMs). For two-tape TMs, TIME:(!(m) C CoT ((())) For general TMMs, TIME( S (t(n) log t(n)).
Proof. For two-tape TMs, by Lemmas 4.2 & 4.4
TIME2(+tm)) C (MM)) S (tT)).
For general TMs, by Theorem & Lemma
TIME(((m)) TIME PTM (()) log ((n)) CoT ((()) log log((n)).

---

Published as a conference paper at ICLR 2025
Corollary 4.5
shows prompting a single Transformer can compute any (t(E)(t(n)) function within ((t(n)) COT steps and any TiME(t(n)) function within ((t(n) t(n) CoT steps. Notably, this is nearly the same as the CoT complexity of the class of all Transformers, which can compute any (I))(((n)) function within ((((n) CoT steps. The logarithmic slowdown here is because the class of all Transformers
simulate unbounded numher of tapes while our single Transformer simulates only a finite number of tapes. Assuming (t(n)) * TIME(t(n)). ) it is unlikely that the CoT complexity (t((n) log (n)) of I' for TIME(t(n)) could be further improved to O(t(n)).
4.3 PRECISION COMPLEXITY
In this subsection, analyze the precision complexity of our construction. We will show that our constructed I" can compute any TIME(t(n)) function within O + t(n))) bits of precision for any length-n input; in particular, it can decide any P language within log nog-precision. Following the common practice in numerical analysis, we assume that each floating point number has significant bits and guard bits (Goodman & Feldstein 1977). where both significant bits and guard bits are used in arithmetic operations while guard bits are rounded off in number comparisons.
Definition 4.6 (Precision complexity class). For a complexity function p(n), ler PRECr (p(n)) be the class of functions that constructed I' compute using O(p(n) significant and guard bits. Corollary 4.7 (Precision complexity). TIME(((n)) C PRECr (IEEC((oo((+((())))))) P PRECr(log n.)
Proof sketch. For any function & E CoT (tt(n) log t(n)). since the prompt T has length O(1), then by Section 3.3 the total length I of the prompt, the tokenized input, and the CoT steps is
I= 0(1) On)) + ((t(n) log t(n)) O(n t(n) log t(n)).
(29)
Thus, according to Section 3.4 all the intermediate results during computation are S O(1), and attention similarities have mutual differences 2 2 ( 22 log Koj))aaa)) ). This implies
CoT (I(n) log (n)) PRECr(log((n> ((n) log ((n)) ((1))) PRECr(log(n) + ((n))). (30)
It follows from Corollary
4.5 and Equation 30 that
TIME(t(n)) S
S ( + t(n))).
(31)
In particular, we have
P TIME(poly(n)) S (Ro(r + (nly(n))) (REgr()
Notably, Corollary 4.7 shows that prompting a single Transformer can achieve the same precision complexity as that of the class of all Transformers: it is known that the class of all Transformers can compute any TIM)(t(n)) function within O(lognn + {(n))) precision (Pérez et al. (201)) while we further show a single Transformer with prompting can well. This suggests our precision complex- ity is presumably tight unless there are further advances in the complexity theory of Transformers.
CONCLUSION
In this work, we have shown that prompting 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 have shown that even though we 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 single finite-size Transformer be efficiently universal, which establishes theoretical underpinning for prompt engineering in practice.
ACKNOWLEDGMENTS
This work is supported by NSF (2416070). The content of the information in this document does not necessarily reflect the position the policy of the Government, and official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Kwangjun Ahn. Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to imple- ment preconditioned gradient descent for in-context learning. Advances Neural Information Processing Systems, 36, 2024.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? Investigations with linear models. In The Eleventh International Conference on Learning Representations, 2022.
Anthropic. The Claude 3 model family: Opus. Sonnet, Haiku, 2024. URL httpt:ttpp:/wwttt odn. anthropic cttp:ii.ccomma/ooo com http:////...aaa.........aaaaaaa.
Card_Claude__1 pdf
Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. University Press, 2009.
Cambridge
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E, Hinton. Layer normalization. arXiv, 1607.06450, 2016.
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of Transformers and its implications in sequence modeling. In Proceedings of the 24th Conference on Computa- tional Natural Language Learning, pp. 455-475, 2020.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. arXiv, 1416,14165, 2020.
Eunice Chan, Zhining Liu, Ruizhong Qiu, Yuheng Zhang, Ross Maciejewski, and Hanghang Tong- Group fairness via group consensus. In The 2024 ACM Conference on Fairness, Accountability, and Transparency, pp. 1788-1808, 2024.
Lingjie Chen, Ruizhong Qiu, Siyu Yuan, Zhining Liu, Tianxin Wei, Hyunsik Yoo, Zhichen Zeng, Deqing Yang, and Hanghang Tong. WAPITI: A watermark for finetuned open-source LLMs. arXiv, 2410.06467, 2024.
David Chiang. Peter Cholak, and Anand Pillay. Tighter bounds the expressivity of Transformer encoders. In Proceedings of the 40th International Conference on Machine Learning, pp. 5544- 5562, 2023.
Alonzo Church. An unsolvable problem of elementary number theory. American Journal of Math- ematics, 58(2):345-363, 1936.
Martin Davis, Ron Sigal, and Elaine J Weyuker. Computabilityy complexity, and languages: funda- mentals of theoretical computer science. Elsevier, 1994.
Kunihiko Fukushima. Visual feature extraction by multilayered network of analog threshold ele- ments. IEEE Transactions on Systems Science and Cybernetics, 5(4):322-333, 1969.
R. Goodman and Alan Feldstein. Effect of guard digits and normalization options on floating point multiplication. Computing, 18:93-106, 1977.
Google. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv, 2403.05530, 2024.
Jordi Grau-Moya, Tim Genewein, Marcus Hutter, Laurent Orseau, Gregoire Deletang, Elliot Catt, Anian Ruoss, Li Kevin Wenliang, Christopher Mattern, Matthew Aitchison, and Joel Veness. Learning universal predictors. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 16178-16209 2024.

---

Published as a conference paper at ICLR 2025
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 171, 2020.
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention Trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-810, 2022.
Juris Hartmanis and Richard E. Stearns. On the computational complexity of algorithms. Transac- tions of the American Mathematical Society, 117:285-306, 1965.
Xinyu He, Jian Kang, Ruizhong Qiu, Fei Wang, Jose Sepulveda, and Hanghang Tong. On the
sensitivity of individual faimess: Measures and robust algorithms. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 829-838, 2024.
Fred C. Hennie and Richard Edwin Stearns. Two-tape simulation of multitape Turing machines.
Journal of the ACM, 13(4):533-546, 1966.
Kaiying Hou, David Brandfonbrener, Sham Kakade, Samy Jelassi, and Eran Malach. Universal length generalization with Turing programs. arXiv, 2407.03310, 2024.
Stephen Cole Kleene. X-definability and recursiveness. Duke Mathematical Journal, 2(2):340-333, 1936.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers Transformers to solve inherently serial problems. In The Tweifth International Conference on Learning Represen- tations, 2024.
Xiao Lin, Zhining Liu, Dongqi Fu, Ruizhong Qiu, and Hanghang Tong. BackTime: Backdoor attacks on multivariate time series forecasting. In Advances in Neural Information Processing Systems, volume 37, 2024.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representa- tions, 2023a.
Lihui Liu, Zihao Wang, Ruizhong Qiu, Yikun Ban, Eunice Chan, Yangqiu Song, Jingrui Hc, and Hanghang Tong. Logic query of thoughts: Guiding large language models to answer complex logic queries with knowledge graphs. arXiv, 2404.04264, 2024a.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre- train, prompt, and predict: A systematic survey of prompting methods in natural language pro- cessing. ACM Computing Surveys, 55(9):1-35, 2023b.
Zhining Liu, Zhichen Zeng, Ruizhong Qiu, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Topological augmentation for class-imbalanced node classification. arXiv, 2308.14 14181, 2023c.
Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Class-imbalanced graph learning without class rebalancing. In Proceedings of the 41st International Conference on Machine Learning. 2024b.
Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Yada Zhu, Hendrik Hamann, and Hanghang Tong. AIM: Attributing, interpreting, mitigating data unfairness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2014-2025, 2024c.
Eran Malach. Auto-regressive next-token predictors are universal learners. arXiv, 2309.06979, 2023.
William Merrill and Ashish Subharwal. The parallelism tradcoff: Limitations of log- precision Trans- formers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
William Merrill and Ashish Sabharwal. The expressive power of Transformers with chain of thought. In The Twelfth International Conference on Learning Representations, 2024a.
12

---

Published as a conference paper at ICLR 2025
William Merrill and Ashish Sabharwal. A logic for expressing log-precision Transformers. In Advances in Neural Information Processing Systems, volume 36, 2024b.
Meta. Introducing Llama 3.1: Our most capable models to date, 2024, URL wtt.tttss//a..eeeeeee
com/ com/blog/meta Lama- ama-3-1/
Turlough Neary, Damien Woods, Niall Murphy, and Rainer Glaschick. Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy. Journal of Com- plexity, 3065):634-666, 2014.
OpenAl. Hello gpt-4o, 2024. URL wtt.hpppps//gpppee..cccc///////e
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the Turing completeness of modern neural network architectures. In International Conference on Learning Representations, 2019.
Jorge Pérez, Pablo Barceló, and Javier Marinkovie. Attention is Turing-complete. Journal of Ma- chine Learning Reseurch, 22(75):1-35, 2021.
Ruizhong Qiu and Hanghang Tong. Gradient compressed sensing: query-efficient gradient esti-
mator for aig-dimenssooal zeroth-order optimization. Proceedings of the 41st International Conference on Machine Learning, 2024.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: differentiable meta solver for combina- torial optimization problems. In Advances in Neural Information P Processing Systems, volume 35, pp. 25531-25546 2022.
Ruizhong Qiu, Dingsu Wang. Lei Ying, Vincent Poor, Yifang Zhang, and Hanghang Tong. Re- constructing graph diffusion history from single snapshot. In Proceedings the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1988.,988, 2023.
Ruizhong Qiu, Jun-Gi Jang, Xiao Lin, Lihui Liu, and Hanghang Tong. TUCKET: A tensor time series data structure for efficient and accurate factor analysis over time ranges. Proceedings of the VLDB Endowment, 17(13), 2024a.
Ruizhong Qiu, Weiliang Will Zeng, Hanghang Tong. James Ezick, and Christopher Lott. How efficient is LLM-generated code? A rigorous & high-standard benchmark. arXiv, 2406.06647,
2024b.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language
understanding by generative pre-training, 2018. URL /tttps://ddn... openai..pppp.....ommmmomo....... com/
saraarcch-oovrr/laaaaa hrg.ap/c........aoooo.eeeeeeaaer wawggaaggeuunddsstaddi.... paper. .dff
Jesse Roberts. How powerful are decoder-only Transformer neural models? arXiv, 2305, 2023.
Marcel Paul Schüitzebergeer. On context-free languages and push-down automata. Information and Control, 6(3):246-264, 1963.
Claude E. Shannon. universal Turing machine with two internal states. Automata Studies, 34: 157-165, 1956.
Alan Mathison Turing. On computable numbers, with application to the Entscheidunggspoolee.. Proceedings of the London Mathematical Society, 42(2):230- 2253,,066,,11 1937a.
Alan Mathison Turing. Computability and X-definability. Journal of Symbolic Logic, 2(4))153-163, 1937b.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, volume 30, pp. 5998-6008, 2017.
Max Vladymyrov, Johannes von Oswald, Mark Sandler. and Rong Ge. Linear Transformers are versatile in-context learners. arXiv, 2402. 2024.
13

---

Published as a conference paper at ICLR 2025
Johannes Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordy- intsev, Andrey Zhmoginov. and Max Vladymyrov. Transformers lear in-context by gradient descent. In Proceedings of the 40th International Conference on Machine Learning, pp. 35151- 35174. PMLR, 2023.
Dingsu Wang, Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenot, and Hang- hang Tong. Networked time series imputation via position-awes awwre graph enhanced variational autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2256-2268, 2023.
Hao Wang. variant to Turing's 's theory of computing machines. Journal of the Association for Computing Machinery, 4(1):63-92 1957.
Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, An- drew M Dai, and Quoc V. Le. Finetuned language models are zero-shot learners. In International Conference on Learning Representations, 2022a.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Ohain-of-thouglee prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pp. 24824-24837, 2022b.
Tianxin Wei, Ruizhong Qiu, Yifan Chen, Yunzhe Qi, Jiacheng Lin, Wenju Xu, Sreyashi Nag, Ruirui Li, Hanqing Lu, Zhengyang Wang, Chen Luo, Hui Liu, Suhang Wang, Jingrui He, Qi He, and Xianfeng Tang. Robust watermarking for diffusion models: A unified multi-dimensional recipe, 2024. URL
net wttp//pffddd0111111...
Ziwei Wu, Lecheng Zheng, Yuancheng Yu, Ruizhong Qiu, John Birge, and Jingrui He. Fair anomaly detection for imbalanced groups. arXiv, 2409.10951 2024.
The Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discrete-state continuous-time diffusion for graph gener- ation. In Advances in Neural Information Processing Systems, volume 37, 2024.
Hyunsik Yoo, Zhichen Zeng, Jian Kang, Ruizhong Qiu, David Zhou, Zhining Liu, Fei Wang, Charlie Xu, Funice Chan, and Hanghang Tong. Ensuring user-side faimess in dynamic recommender systems. In Proceedings of the ACM on Web Conference 2024, pp. 3667-3678, 2024.
Hyunsik Yoo, Ruizhong Qiu, Charlie Xu, Fei Wang. and Hanghang Tong. Generalizable recom- mender system during temporal popularity distribution shifts. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
Zhichen Zeng, Ruizhong Qiu. Zhe Xu, Zhining Liu, Yuchen Yan, Tianxin Wei, Lei Ying, Jingrui
He, and Hanghang Tong. Graph mixup approximate Gromov-Wass Wasserstein geodesics. In Proceedings of the 4/ International Conference on Machine Learning, 2024.
Ruiqi Zhang, Spencer Frei, and Peter L. Bartlett Trained Transformers learn linear models in- context. Journal of Machine Learning Research, 25(49):1-55, 2024.
14

---

Published as a conference paper at ICLR 2025
Algorithm
Autoregressive generation: generate,(2))
Input: decoder-only Transformer I Σ* + E; nonempty input e E+; stop token $ Σ
Output: generated output Σ+ U E
1: repeat
2: generate next token +- [()
3: append next token æ +-
4: until e c= $
5: return generated output
Algorithm Extracting output from CoT (readout)
Input: generated CoT E
Output: extracted output y E 10,
I: initialize the left index i -2
2: while U; + : do
decrement the left index 4: end while
3:
5: return extracted output 0;-1:-1
CONTENTS
Two-tape Mss v.s. 2-PTMS
2-PTMs simulating two-tape TMs
1
A.2
Bi-infinite two-tape TMs simulating 2- 2-M
66
Proof Theorem/3.1
B.
Embedding layer
B.2
Other positional identifiers
B. 3
Parsing CoT steps
4
Retrieving pointed tape cells.
B.5
Parsing instructions in prompi
B.6 6
Locating current CoT step
B.7
Executing next CoT step
20
B.8
Extracting final output
B.9
Generating next token
22
1.10
Composing the Transformer
22
B.
Size of the constructed Transtormer
Experiments......
Concluding remarks
A TWO-TAPE TMS V.s. 2-PTMS
In this section, we characterize the relation between two-tape TMs and 2-PTMs.
A.1 2-PTMS SIMULATING TWO-TAPE TMS
In this subsection, show the correctness of the construction presented in Section 4.1
For each non-halting state g E Q (ghatt) since we use + 1+1+6+6++ 1+66 = 27 instructions to simulate its transition rules, put these instructions at 4277:279+227 Thus, the instructions for state q starts at (27g- Besides that, for the halting state Qbalt = K, we put the halting instruction after the last non-halting state K 1. Thus, the halting instruction is - recapitulate, the instructions for every state E Q start at 127g-
127K
127 To
Hence, make state transition to g' Q, should go to instruction 127g'. Since we do not know pointed cell values after we move tape heads, We use two go-to instructions (A 27 A? with op- posite conditions ensure state transition g'. This establishes the correctness of Nig db))))
15

---

Published as a conference paper at ICLR 2025
To simulate transition rules ó(g, O, 0), 8(g, O, 1), 8(g, 1, 0), ,0, 1, 1) for each non-halting state q Q \ (qaat), we first use A 227 to check the pointed cell value of tape A and then use B 8 and +2 to check the pointed cell value of tape B, where it is easy 27q + 8, and 27q + 21 are correct.
that the indices 27q + 14,
Finally, note that the simulation is always valid because 2-PTMSs have bi-directional tapes while TMs have uni-directional tapes. This concludes the correctness of the constructed 2-PTM t.
It follows that (IME)(t(n)) S PlM))))
A.2 BI-INFINITE TWO-TAPE TMS SIMULATING 2-PTMS
In this subsection, we show that any 2-PTM can be simulated by a TM over two bi-infinite tapes.
For any E TIME2-rrM((((i))
there exists 2-PTM & that computes (()()) from S(x) within
time (tt(n).. Let K := [4]. We will construct a two-tape TM M = (Q == {0. 1..... K), quar == 0, Phalt := K, f0, 1}. simulates the 2-PTM & within time O(t(n)), where we simulate each instruction (j = O..... /
...,,,),,
: -=
m 2, (Q {9hatt }) {0, Q x (f0, 1] {L, R) )²) that
1) using state j. Let Ca, < (0,1) denote the pointed cell value tapes A and respectively.
If = #, then we only make a transition to the halting state Ghait
5(j. Cx, cp) == (ghalt Ca. S, Ca, S).
(32)
If 1j = Ada (d4 E {L, then move the head for tape and keep the head for tape B:
ö(j. ca. 0B) := (j 1, ca. da. C3 S).
(33)
If = Bdg (dg E { R)), then we move the head for tape and keep the head for tape A:
ò(j, Ca, ca) == (j + 1, Ca. S, <B, dg).
(34)
If = Ac4 (c E (0, 1),, then we write e, to tape A and keep tape heads:
8(j, cg) (j + 1, c S).
(35)
If BCg (6 E {0,1)), 1}), then we write o to tape B and keep tape heads:
8(j, ca. cb) == (i + 1, Cr. S. S).
(36)
= = (T E B)), we go to if the pointed cell on tape r is 0 and to j + otherwise:
ö(j, Ca. ca) = 1 S, Cz. 8) if c, # 0. (ki, S,
if c, =0, 0,
(37)
if = T? (T (A, we go to if the pointed cell on tape r and jo + otherwise:
8(j, Ca c2) = { (k. S.
c if #1.
(38)
S,, S)
The correctness of the construction above is clear. Since M simulates each iy through 1 0(1) transition, then M also has time complexity ((t(n)).
B PROOF OF THEOREM 3.1
In this section, we present our detail construction the Transformer I' the proof of Theorem 3.1 We will show that we can execute the constructed prompts using affine maps, ReLU activation, layer normalization, and causal attention. Some key ideas are presented in Section 3.4 in the main paper. Unless otherwise specified, the similarity map use in causal attention is the identity function.
B.1 EMBEDDING LAYER
Here, we present our construction of the token embedding and the positional encoding in the embed- ding layer I' emm Let v = Up Up E It denote the input token sequence of the Transformer.
For each token U; (i = 0, .., 2|ol 11, we use the one-hot representation as its embedding:
z = [[,,=));
Σ.
(39)
As described in Section 3.4 we use the following positional encoding for each position
(i + (i + 2) +1
(40)
Vi+ 1) +
16

---

Published as a conference paper at ICLR 2025
B.2 OTHER POSITIONAL IDENTIFIERS
In addition to the positional encoding, we compute three other positional identifiers to be used later. First, we causal attention with query 1, key 1, and value =/ compute
pos.
(41)
i+1
==
Next, we use layer normalization (LN) to compute two other positional identifiers:
(2 2 pos, LN(1, (1, = (
i+1
1
(42)
1)²+
B.3 PARSING COT STEPS
Since the prompt and the CoT share some tokens, need distinguish CoT steps from the prompt according to the position of the delimiter token $. Specifically, we need an indicator of whether each token v; located after the delimiter token not. Thus, we use causal attention with query 1, key 1, and value = to compute the discounted indicator:
after delim, disc
(43)
2+1
==
Then, we use layer normalization to convert it to Boolean value:
after delim
LN(2 after delim, disc)
[Bjseny=s]
(44)
Next, we check if token is a CoT step of writing a cell using RcLU LeLU-immleeented Boolean algebra:
r write == ReLUU== + is + after delim
1), T TE
{(AAB)) (A,B];
(45)
can compute the value that being written using ReLU:
(2 + x; after delim
1),
TE (A,B];
(46)
can also compute the direction of head move in CoT step using ReLU;
mave ReLU(=) is TR
after delim
1) (eI.U(=) is + zfherr delim
1), E (A,
(47)
B.4 RETRIEVING POINTED TAPE CELLSS
Before retrieving the pointed tape cells, we need to compute the current positions of tape heads. Since attention cannot compute sums directly, we use the idea presented in Section 3.4 to compute a normalized representation of the position. Specifically, we first use causal attention with query 1, key 1, and value 25 move to compute discounted head positions:
cur disc
move
T E (A,
(48)
Then,
and LN compute normalized representation of head positions:
cur norm
one nuem)
LN(2) cur disc 16
pos. 1
(49)
move
j=
T (A,
(50)
2/=00 2j move
E2 2j muve)2
Next, can retrieve the pointed tape cells by finding the last write step the same position. We use causal attention with query (1, 27 our norm 22 one norn pp) key
(g/57 7 2 norm = cur norm 1
-2 pos. 1TT and value (2] write 2 cur is writesT compute
17

---

Published as a conference paper at ICLR 2025
the retrieved tape cells (2] 2
norm, 27 retr w (T {A.B)). Note that also com-
pute 2| ret eur norm and 2; retr write here because there is a caveat: the pointed tape cells might not have been written yet. We use LN and ReLU to compute an indicator of whether the pointed tape
cells have not been written:
not lound = (LLU T CuT Borm
retr our norm) )) + ReLLU(L(
reir OUT nOrm
cur norm
[=7 ou MaE
of?? tet out 2000)
TE (A. (51)
If retreived tape cell has not been written yet, it must have blank value 0:
Zi
val : ReLU(x 2/ + z
not found
write
1), TE (A,
(52)
B.5 PARSING INSTRUCTIONS PROMPT
Recall that each instruction is encoded into one more tokens. Thus, we first compute whether each token is the start a instruction in the prompt:
is inst = R2LU(2
+
AL
+
is BL
+ 21
AR AR
+ Bs
(53)
+ is
AD
24
is
80
+ 24
is
+ is8B1
(54)
isB
is
A7
is mg
2;
after delim).
(55)
We compute a program index / for the start token of each instruction. We use causal attention with query 1, key and value z/ inst to compute the program index of each token in the prompt:
prog idx disc,
is inst
(56)
j=0
We further subtract 1 from Σj=o is inst to handle the lag between the prompt and the CoT: 2f
prog
prog disc, raw
20ss, 1
is inst
(57)
i+1
3=0
Then, we use LN to compute normalized representation of Σÿ=
is inst
1:
"j
(2) prog idx norm
prog idk norm
:= LN(2 prgg pos,
(58)
i=0 inst
(59)
inst
1)2
(Ej= inst 1)2 +1
== 2j
Besides that, since go-to's 's special instructions that need multiple tokens to encode, also check whether a token is the start of a go-to instruction:
gote cond
is A! 2/
16 B1
A2 B2
(60)
We also need a go-to index for tokens -, + in the prompt to mark the order of tokens within each go-to instruction. To compute it, first compute the reciprocal number of tokens between is and the start token uor of the current go-to instruction, using causal attention with query 1, key prng idx and value 2,
poto cond
Ejse Zj gotd
1
goto disc
(61)
Ej
+' +1
Then, LN to compute normalized representation of the go-to index:
(a
goto idx norm, goto norm, raw = LN(1
disc
(62)
1'
(63)
&' +12+1 Vii 16-+++1++1
18

---

Published as a conference paper at ICLR 2025
To match the go-to index of non- con-go-to tokens, we finally adjust them if is the start token t/ of the current go-to instruction:
golo idx norm idx norm, raw
+ 2,
cond
(64)
20tO one norm poto one norm, row
2
goto cond
(65)
That is, when 2s is the start token of of go-to instruction, we instead have
golo idx norm
golo one norm
(1, (1,
(66)
B.6 LOCATING CURRENT COT STEP
Here, we describe how locate the current instruction to execute. We can imagine program pointer t that indicates the instruction we are currently executing. A caveat here is that each go-to instruction needs multiple CoT steps. Thus, it is important to check whether during a go-to instruction or not.
First, we compute how each go-to step contributes the program pointer via ReLU:
prog move := [=]
is
+ =i
after delim 1) ReI.U + z
after delim
1).
(67)
Then, we use causal attention with query 1, key 1, and value x. goog move to compute the discounted total contribution:
prog move disc
pong move,
(68)
==0
and use LN to compute a normalized representation
Σ 3
prog move.
prog move norm
prog move one norm
LN(2 prog move disc pos,
(69)
prog
(70)
2=== prog move +1
===== 2i
.rog move )2
+
Next, we check whether the token vs is the start token oy of the current execution step record in the CoT:
24
is rec start
+ ReLUU
is AL
+
2;
is BL
26
is
AR is ER
(71)
+
40
zi
80
21
31
+ 2
Bs
(72)
+ + 2/t + 23
after delim
1),
(73)
where also add 2/- here for convenience later. Similarly. check whether the token v; is the ending token of of the current execution step record in the CoT:
ReT.U is
+2, + 2, .s
+ 2/ 2/5AR
BR
(74)
+ A0
+ 2, B0
+ 2, is
is
(75)
+2 + after dolim
1).
(76)
Then, imagine that each token has record index to mark which each execution step it belongs to. To compute it, we first compute the reciprocal number of execution steps so far, using causal attention with query 1, key 2/. and value 2//
2 is ree start is Ej-o Σj=
prog rec one disc
2
1
(77)
2
is start
+1
We then compute a normalized representation of + using LN:
(z) prog norn
prog norm = LN(1, 2.
prog disc
(78)
t' +1
1
(79)
+12
V(e 112
19

---

Published as a conference paper at ICLR 2025
Next, since each go-to execution step needs multiple CoT steps, we need to handle go-to execution step records specially when the go-to condition is satisfied. We can image that each CoT step has temporary program index that marks the order of each token in go-to exccution step record. To compute it, we first compute the reciprocal number of tokens between vy and the start token Up of the current go-to execution step record, using causal attention with query 1, key - 2 value 2)
prog ree one disc and
2/
prog kmp one diss
Ej=r
1
(80)
1' +1 Ej=e
With this, we can compute normalized representation of + using LN:
(egiogg tmp norm, nw prog tmp one norm, m == LN(1, z.ping ump one disc)
(81)
1 -( Vi V(i +1)
i-1'+1
(82)
To match the temporary program index of non-go-to execution steps, we further adjust them if U; is the ending token of the current go-to instruction:
prog tmp
:= (e, Drogg
prog tmp norm, raw
2
rec end
+ end
(83)
prog tmp one norm := (eLU prog tmp one norm, raw
is rec end
(84)
That is, when ey is the ending token of the current go-to instruction, we instead have
(2,
prog tmp norm
:
prog tmp one norm) (1,0).
(85)
We will use the quantities above to identify the instruction execute.
B.7 EXECUTING NEXT CoT STEP
To generate the next token, we need to execute the current instruction and record it via a CoT step. Before that, we check whether 2 belongs to a satisfied go-to execution step record:
ise goto = ReLU(=) + 2 + + + after delim - 1).
(86)
2
Another quantity we will need is how each CoT step contributes to the current program pointer:
prog move
ReLU AL
is BL 2,
+ 2;
+ zz
(87)
+ is + 2,
+ z B
(88)
+ + lb after delim
///
1) - ReLU + 2
after delim
(89)
We also compute an auxiliary bound 2 prog ree diff on the differences between some attention scores
using causal attention with query (s.mg ree norm prgg rec one norm
T, key (=)mme 2o0o BTT, and value pj-
We further compute an auxiliary quantity:
2
prog rec bias
3 ReLUU prog rec diff'
1
+ +22 is rec gotn
2).
(90)
2
Using this quantity, we will be able to avoid attending to tokens outside the current execution step record. Next, we use it to identify the next instruction to execute. We first compute the discounted program in- dex of the instruction that we need to execute, which is proportional to the sum of 2
is easy to see that 2
prog diff
< 3 if and only if 2;
is goto
cur move until the beginning token Uy of the current exccution step record, using causal attention with -nrrog prog rec morm -2- prog rec one nonnyT key (1, 2 rec norm prog rec one norm value
query (zr rec biss
:2)
(2) pang cur move
2/ "T, and similarity function (z) == 2 - ReLU(2 - x) min 2}:
ΣØ=
prog move
Σj 3j
prog cur move
prog cur disc 2
(91)
Σド=ul 1
1
E/=
prog our one disc
(92)
Σ
7 +
20

---

Published as a conference paper at ICLR 2025
Then, we use LN to compute normalized representation of Σ ==0 2)
prog cur move;
(2) Doog cur norm
one morm
= LN (2/
poog cur disc
prog cur one disc
(93)
j=== prog move
(94)
(=j= poog cur moNe
V VEj= prog cur move)2
Next, we find the instruction 4 whose program index matches the current program
pointer and whose go-to index matches the current temporary program index, using
causal attention with query (2g cur norn prig cur one norm prog tmp norm progg imp one norm Pis -1) key (a) prog ids norm prog idx one norm
idx :
14
1)T and value 2)s0:
24
loken is
ii 21
OF (L, BR, AO, BO, A1, A B!, B!, A?, -,
(95)
Joken
(96)
Note that exactly one of them is 1. remains to execute the instruction and record its outcome. If loken a for some A?, B?}, then we need check whether the go-to condition is satisfied or not:
sar 8! ReLU(2 (2 token A!
A val
(97)
sat B = ReLU(2 (2
token is
2. val
(98)
&? ReLU(
of
token A7
24 val
1), 1).
(99)
2
ReLU(2
24
Joken BY
24 val
(100)
They enable us to choose (satisfied) or (unsatisfied):
token is
24
sat A!
+ 2,
sat &?
+
2:
(101)
token is 24
token A!
2,
token B1
2/
tooken A?
2
token 87
token
(102)
B.8 EXTRACTING FINAL OUTPUT
After execution, the content left on the tape A is the Shannon-encoded output 5(pp(z)). We need to extract the decoded output (xx) from the previous CoT steps.
First, we need to check whether we have arrived at the final output stage:
is read key 2/
2::
2/ 2/
(103)
Suppose that we are now trying to find the k-th token of the output ((x). Recall that the k-th token (k 0) of the output sp(x) corresponds to the (2k)-th and (2k + 1)-th tokens of S(p(w)). To help compute the indices 2k and 2k + 1, we compute the following shifts:
read curO shift = 2( + 2/11),
(104)
2;
read curl shift ks 2(2
is
(105)
Suppose that token : is the t-th token in the generated COT. We use causal attention with query 1, key 2/ for = +
is key and value (2jead curD shift 2 curl shift
2/ :)T to compute the discounted 2k and 2k +
2k
24
read curt disc
is read key
read curo shift zj
i- 1-1+1
(106)
===0 2
1
2k +
read curl disc
read curl shift
(107)
Σ = 0== 2j
read key
t
==0
1
read
(108)
read
2j
i
t
1=0
21

---

Published as a conference paper at ICLR 2025
We use layer normalization to compute representations of 2 and 2k 1: read norm
read
one norm
= (24 read curn read disc)
24
2k
(109)
(2k)²
(2k)²
(2fead
curl curl norm
21
gead one norm
LN (2fend disc read disc)
23
2 +
(110)
(2k + +)= V2K + 1)3
Next, similarly with Appendix B.4, we retrieve the (2k)-th and (2k + 1)-th tokens of ((((()) as follows. We use causal attention with query (1, 2, curD morm read curD one norm p,) key
write T compute the 2,
(2Jo A write -, norm = one morm
= = IT_ and value (z/ write 2A cur morm
retrieved tape cell status (=fead retrt) 27 retrO cur norm rread reirO is write)T, yT. We use causal attention with
query (1, 2, curl norm 22/and curl one norm P.) key (2) A write .23 norm .2 cur one norm -2) -2p00.11 1)T
compute the retrieved tape cell status We use LN and ReLU to compute an indicator of whether the retrieved tape cells have not been written:
and value (z/ write .2Acur norn A wrile)
(=tcad retrl ==tead retrl cur norm =z retrl is write
rrea retrO not found
= ReLU(LN read turt) norm
read retrll cur Borm)) )) + ReLU(IN( (4 read retrO cur norm
read curô morm
Len cart com nom #ot euaa
(111)
read retel not found
(LL read curl norm
read retrl cur norm)) + RcLU(LN read retrl cur norm
read curl norm)
2,
Iggaddaart nom a rumm
(112)
Finally, we can obtain the values of cells 2k and 2k 1:
read = (eLU(2) read retrO
found
2/
retri)
1),
(113)
read retrl val = ReL.U(2 read retri
read retrl not found
read retri write 1).
(114)
Using the quantities above, we can decide the next token to generate:
Joken = 2 RcLU(2 key + 2 retrO val
read retel val - 1),
(115)
Joken
2 ReLU( is read key + gead retrt val + 2;
read retrl val 2),
(116)
= 2 2 key 2,
read retrO val
(117)
Here, we use coefficient 2 to distinguish the output extraction stage from the execution stage.
B.9 GENERATING NEXT TOKEN
The next token be generated by the Transformer I' is
arg max
token is 21
(118)
o BL, AL, AD, A0, B0, /1
The generation procedure stops upon the generation of the ending token $
1.10 COMPOSING THE TRANSFORMER
In this subsection, we describe how to compose the aforementioned operations into a Transformer.
Embedding layer. Recall that the construction uses 4 positional encodings Ps. 1o.. ; 2000 pos, Thus, our token embedding and positional encoding use the first |-] 1 dimensions. For the token embedding emb, the first | dimensions are the ont-hot representation of the token, and the next dimension is zero. For example, if v; is the first token 57, then
emb(w:) = 1,0,....0 O.
0.0, 0. )
(119)
first [X]] dims:
dim:
slots for intermediate results
Nevertheless, the token in the prompt does not stop the generation procedure.
22

---

Published as a conference paper at ICLR 2025
For the positional encoding pos,
pis( 0, 0.......0
Pi-
0, 0.0.....0
)
(120)
lirst |لك]] dims: zeros
next dim: pos enc slots for injermediate results
Therefore, the embedding layer for the example above is
emb(v;) + pos(() = 1, 1.0......
P
0.0.... 0
)
(121)
first [ dims: one-hot
DEXT dime
slots for intermediate results
Here, emb((:) + (1) is indeed the standard embedding layer in LLMs.
Intermediate results. Recall that each Transformer layer has a residual connection after its output. Thus, can compute each intermediate result via Transformer layer and add it to the hidden embedding via the residual connection. For the example above, we can construct a Transformer layer that computes z/pm and then the hidden embedding after the residual connection of this Transformer layer
1.0....,0. O, Ps. pos,
0, O....,0 0
T.
(122)
first dims: one-hot
slots for other intermediate resulis
B.11 SIZE OF THE CONSTRUCTED TRANSFORMER
In this subsection, we show that the constructed Transformer I' has a constant size terms of the number of its operations and the number of bits to represent its parameters.
Number of operations. From the construction above, we can see that the constructed Transformer I' does not depend on or æ. (To compute different functions y,, we change only the prompt but do not need change the Transformer.) It is clear to see that our constructed Transformer has constant number of operations.
Number of parameter bits. From the construction above, we can see that the constructed Trans- former uses only 0, + 1,2, as its parameters. These numbers can be exactly expressed with constant number of bits.
C EXPERIMENTS
We demonstrate our construction through Python implementation. Our code and demo results are publicly available at
D CONCLUDING REMARKS
Connection with universal TMs. Hennie & Stearns 1966) have shown that there exists uni- versal TM (UTM) that can simulate any Turing machine M in O(t(n) log t(z)) steps if M halts in t(n) 2 n steps. Then by Pérez et al. (201)), there exists a Transformer that simulates this UTM. However, due to the complication of the UTM, it would be quite involved to explicitly construct this Transformer. Nevertheless, this UTM has inspired us to propose 2-PTMs, which enables to explicitly construct a simpler Transformer. Furthermore, our 2-PTMs establish the first theoretical framework to formalize prompting. Using our 2-PTM-based framework, we believe that people will be able to generalize more results from the classic one-model-one-tate paradigm the L.M prompting paradigm.
Discussion on CoT complexity. A limitation this work is that our construction uses long CoTs for hard problems with high time complexity. However, while it might be possible to slightly improve the CoT complexity, recent theoretical evidence has suggested that long CoTs are very likely to be necessary for these hard problems. For example, Merrill & Sabharwal (024a) have shown that any Transformer with O(log n) CoT steps can solve only problems. Assuming L * NL, it implies that any Transformer with Oloogn) CoT steps cannot solve any NL-complete problems such
23

---

Published as a conference paper at ICLR 2025
directed graph connectivity. An interesting future work is to show tight lower bound of the CoT complexity.
Discussion hardmax. Following prior works (c.g., Pérez al. 2019; Hahn 2020), this work uses hardmax in attention to simplify construction. However, real-world Transformers use softmax in attention. Using hardmax instead of softmax is limitation of this area. We hope to address this limitation in future work.
Discussion context windows. The Transformer constructed in this work uses unbounded context window. However, practical implementations of Transformers typically use a bounded con- text window due memory considerations. This is indeed limitation of current studies the Turing completeness of Transformers. To address this limitation, we hope to study bounded context windows in future work.
Discussion on learnability. Our current work focuses on expressive power rather than learnability. While we have shown the existence of Transformer on which prompting is suring-complets does not necessarily imply that Transformer effectively learns to simulate any 2-PTMs through CoT steps. Investigating the learnability of such Transformer is an intriguing direction for future research.
24


Reviews:
[{"review_id": "qNOG5UxZRC", "reviewer": "Reviewer_h1Bs", "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.", "questions": "Please explain the aspect of universality of your construction mentioned above.\n\nCould you please discuss in more detail what is the size of the constructed Transformer.\n\nL.129: you write that you refer to the time complexity as the the time complexity on a random-access\nmachine (RAM). But this seems to be not true. Could you please explain this?\n\nL.146: why is the embedding function, a function from $\\Sigma$ and not from $\\Sigma^+$ or $\\Nat \\times \\Sigma$?\n\nL. 158: You call: key map qry_{l,k}. It should be: key_{l,k}\n\nL. 335: why do you define E(0) := ALALA1 and not as E(0) := ALA0ALA1 ?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xf2gyVCeQ4", "reviewer": "Reviewer_2gkz", "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.", "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?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "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. \n\nWe, 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? \n\nIt 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JIufymH0YV", "reviewer": "Reviewer_k74c", "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.", "questions": "What is the advantage of using a 2-PTM instead of a standard Turing machine in [1]?\n\n[1] Pérez, J., Barceló, P., & Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research, 22(75), 1-35.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "+ The paper presents a new reduction that proves Turing-completeness of transformers with hardmax attention.\n+ 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.\n- 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.\n\n[1] Pérez, J., Barceló, P., & Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research, 22(75), 1-35.\n\n[2] Hennie, F. C., & Stearns, R. E. (1966). Two-tape simulation of multitape Turing machines. Journal of the ACM (JACM), 13(4), 533-546.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V30oWveNVC", "reviewer": "Reviewer_cbcS", "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.\nAdditionally, 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.\n\nTo 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.\n\nThese 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.", "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.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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'.\n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)