Constant Bit-size Transformers Are Turing Complete
Authors: Qian Li
Yuyi Wang
Venue: NeurIPS 2025 poster ()
Keywords: Transformer
Turing complete
Post machine
context window length
space complexity
Primary area: theory
TL;DR: Simulating Turing machines with transformers requires scaling only the context window length, proportional to space complexity.

Abstract: We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer, as long as the context window is sufficiently long. This improves previous works, which require scaling up either the model's precision or the number of parameters on longer inputs. Furthermore, we prove that the complexity class SPACE$[s(n)]$ exactly characterizes the expressive power of a constant bit-size transformer with a context window of length $s(n)$. Our approach relies on simulating Post machines, a Turing-complete computational model. Post machines can be modeled as automata equipped with a queue, exhibiting computational behaviors naturally aligned with those of transformers. The behavioral similarity between transformers and Post machines may offer new insights into the mechanisms underlying the reasoning abilities of transformers.

Constant Bit-size Transformers Are Turing Complete
Qian Li
Shenzhen International Center For Industrial And Applied Mathematics, Shenzhen Research Institute of Big Data Shenzhen, China
liqian. ictiggail.ccom
Yuyi Wang'
CRRC Zhuzhou Institute & Tengen Intelligence Institute
Zhuzhou, China
yuyivangg200gma1..cmm
Abstract
We prove that any Turing machine running on inputs arbitrary length can be simulated by constant bit-size transformer, as long as the context window is suffi- ciently long. This improves previous works, which require scaling up either the model's precision the number of parameters longer inputs. Furthermore, we prove that the complexity class SPACE[s(12) exactly characterizes the expressive power of constant bit-size transformer with context window of length s(n). Our approach relies on simulating Post machines, a Turing-complete computa- tional model. Post machines can be modeled automata equipped with queue, exhibiting computational behaviors naturally aligned with those of transformers. The behavioral similarity between transformers and Post machines may offer new insights into the mechanisms underlying the reasoning abilities of transformers.
Introduction
Transformer-basd -bsed large language models (LLMs) with chain tfahn-hf- (CoT) steps Achiam et al.
2023, Gemini et 2023 Anthropic 2024 Dubey al., 2024 Guo al. 2025 have demonstrated
exceptional capabilities across a wide range of complex reasoning tasks, such as mathematical
problem solving and code generation [Hendrycks et al., [022] Jimenez et al. 2023 Rein el. 2023) These remarkable empirical successes raise fundamental question: What enables transformers to support such general reasoning capabilities, and what are the limits this capability? Understanding this question is not only of theoretical interest but also of practical significance for further enhancing the reasoning abilitics of transformers.
Motivated by this fundamental question, line of theoretical works [Pérez et al. 202 Bhattamishra al. 2020 Merrill and Sabharwal 2023 2024 Li al., 2024 Qiu et al.) 2024 Zubié al.) |
Merrill and Sabharwal [0255] Yang et al. 2025 have studied the reasoning abilities of transformers through the lens of expressiveness. central result from these works is that transformers (using CoT steps) are Turing complete; that is, transformers have sufficient expressive power to simulate arbitrary Turing machines (TMs). However, in all these results, the bit-size of the transformers (i.e., the total number of bits representing the model) is not constant: either the precision bit [Pérez al. 2021 Bhattamishra et al. 2020 Merrill and Sabharwal 2024 Qiu et al. 2024) or the embedding dimension Li et al. 2024 must grow with the input length, meaning that larger models are required to handle longer inputs. This scaling requirement raises a fundamental barrier to approaching transformer baase
'The authors are listed alphabetical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparing the existing
proofs in terms of required precision, em- bedding dimension, effective window size, and CoT length. We focus on the nontrivial case where t(n), s(n) 2 n. We remark that these constructions typically do not employ the vanilla architecture but instead introduce specific modifications; see Appendix for a summary.
Source
Precision
Dimension
Window
CoT per TM-step
Pérez et al. 2021
(log t(a))
((1)
n + t(n)
Bhattamisha et a. 2020
unbounded
0(1)
+ t(n)
1
Memil and Sabharwal
2024
Ollg (()))
0(1)
+ t(n)
Lt 2024
((1)
Ollgg (())
(((()) log ((n))
Olog Un)) (amortized)
Quu el al. 2024
Ologg 0(1)
Q(1)
(((()) log (w))
Ollog (()) (amortized)
This work
O(1)
s(n)
s(n)
Any multi-tape TM running in time f(n) can be simulated by a Boolean circuit of size ((t(n) log t(m))
Arora and Barak 2009
Goldblum et al. 2024]. particularly for lifelong learning agents that interact with an open environment and accumulate an ever-growing history (e.g., the AIXI agent (Hutter 2005 ),
AGI [ecun 2024
where the input length grows unboundedly over time.
This motivates the following critical question:
Problem 1: Is necessary to continue scaling up the bit size of tranformers to handle longer inputs?
1.1 Our contribution
We answer Problem 1 in the negative. We prove that constant bit-size transformers are Turing complete. Specifically, given any TM, there exists a transformer with fixed numerical precision and a fixed number of parameters that can simulate the TM on inputs of arbitrary length, provided that the transformer's s context window is sufficiently long. In particular, by applying it to the universal Turing machine, which takes as input a description TM of a TM and an input string æ and outputs TM(x). we can conclude that single, constant bit-size transformer can compute any computable function, as long the description of relevant TM is loaded in the prompt.
Remark 1. In fact, it is not even necessary to load the task-specific TM description into the prompt or to pre-inject during pre-training. Instead, the transformer can be instantiated to simulate a TM that performs the meta-task of designing an algorithm for the given reasoning problem. For example. one can design the transformer to simulate Levin's 's universal search algorithm [Levin] 1973 1984 Schmidhuber 2004%, which solves arbitrary search problems, such as theorem proving and planning, as quickly as the fastest possible algorithu in an asymptotic sense. This suggests that, in principle, a single constant bit-size transformer has sufficient expressive power to achieve form of general reasoning ability.
We emphasize that the context window length is the minimal resource needed to scale up to handle longer inputs: The context window must be at least as long as the input length n, otherwise the transformer cannot even access the entire input. Moreover, we provide an exact characterization of the expressive power of constant bit-size transformers as a function of their context window length. Specifically, let WINDOW(s(n) denote the complexity class consisting of decision problems solvable by a constant bit-size transformer with a context window of length (s)))). SPACE (scCE(((() (n)) the class
of decision problems solvable by a TM using (s)))) space, and PSPACE == UKEN SPACE[n the class of decision problems solvable in polynomial space. We now state the main theorem of this paper:
Theorem 1. For any non-decreasingg function s(n) 2 n, we have [IND (PA)
In particular, WINDOW)poly(n)) = PSPACE.
Previous proofs establishing the Turing completeness of transformers suggested that the context window length must scale with the time complexity for solving the task. In contrast, Theorem [ implies that it sufficient for the context window length to scale only with the space complexity instead. This distinction is crucial, since many problems exhibit significant gap between space
Transformers allowed to generate arbitrarily long CoTs before producing the final output.

---

complexity and time complexity. For instance, solving Boolean satisfication problems, Sokoban puzzles (Hearn and Demaine 2005], model checking tasks [Sistla and Clarke 1985]. or other PSPACE-complete problems, require only polynomial space by tracking the current configuration, whereas the time complexity widely conjectured to be superpolynomial (Arora and Barak] 2009)
or even 2Poly(n) [mpagliazzo and Paturi 2.01]. Recently, Williams [2025) proved that every multi- tape Turing machine running in time t(n) can be simulated in space only O( ((v((m) log t(n)). As
consequence, there are problems solvable in (()(n)) space that require ()) time on multitape
Turing machines.
In addition, the simulation of TM by a transformer in Theorem I is uniform and easily generalizable with respect to the context window length. Specifically, to simulate given TM on increasingly long inputs, the transformer just needs to extend its context window by adjusting the relative positional encoding according to an explicit formula, without changing all other model parameters.
Aiming for stronger deductive reasoning ability, a line of engineering efforts tend to lengthen context window instead of growing parameter count. Our result formally justiftes this strategy: extending the window alone is sufficient. Moreover, a window that grows only polynomially with the input already suffices to solve every PSPACE problem, including game-tree search and mathematical proofs.
Remark 2.
Remark 3. There is ongoing debta on whether transformers can approach AGI. A common negative view (e.g. [Lecun 2024 Goldblum et al. (024]) argues that transformers, limited by finite size and window, cannot approximate unbounded computation. Our result shows that, at least for deductive reasoning tasks (whose solutions depend only on explicit information), scaling window length alone is theoretically sufficient, and continually scaling up size is not a principled requirement.
Our proof strategy is to simulate Post machines [Post 1936] with transformers. A Post machine can be modeled as an automaton equipped with a queue. By storing the TM's tape within the queue in a cyclic manner, Post machines can faithfully simulate Turing machines, and thus are Turing complete [Post 1936 Davis et al.] 1994]. By viewing the transformer's 's context window as queue-like structure, can observe that the behavior of Post machines naturally aligns with that of transformers. Leveraging this behavioral similarity. we can then design a transformer that faithfully simulates the step-by-step execution of Post machine. In general, this alignment offers a new interpretation of the attention mechanism: not only as a statistical aggregator, but also as a discrete computational operation over queue-like structures.
1.2 Other related work
Recent theoretical studies have examined the computational capabilities of transformers under various architectural constraints. [eng et al. [2023), Merrill and Sabharwal [2023 2024]. Li et al. [2024] proved that CoT steps can improve the reasoning capabilities of transformers: Transformert without CoT can only solve problems that can be solved by shallow circuits, whereas allowing polynomially long CoT steps enables the same model to solve any problem in P. In addition, Merrill and Sabharwal 2025 showed that transformer with depth growing only logarithmically in the input length can recognize regular languages and solve graph connectivity problems without CoT, whereas a constant- depth transformer requires CoT steps of length (2()). We remark that these papers assume either a Ollog --bbit precision or a Olog n) -mbeddiigg size, and require the context window to be long enough to cover the entire context. The survey by (Strobl et al. (2024) provides a comprehensive overview on formal-language expressivity of transformers, clarifying how design choices affect expressivity.
Aiming to reduce the required context window length and the memory, Yang ct al. (0055 proposed the PENCIL framework, which incorporates a reduction mechanism to recursively "crase" intermediate CoT steps. This allows the context window length to scale with the space complexity of the computation, rather than the time complexity. We remark that their results still require increasing the bit-size of the transformer as the input length grows.
Schuurmans et al. [2024] considered generalization of autoregressive decoding where, given a long input, emitted tokens are appended to the end of the sequence as the context window advances, and proved that the resulting system is Turing complete. This work also exploits the similarity between the behaviors of Post machines and Transformers. In fact, they analyze an even restrictive model, the so-called Lag system, where the next token depends solely on the leftmost two tokens in the queue
3

---

and not on the state of PM. The main technical challenge in their construction is thus to compensate for the absence of access to the state q. As a result, their simulation requires (s()))) CoT tokens per TM step, whereas ours are only ((s(n)).
2 Notations and preliminaries
Let IR be the set of real numbers and IN be the set of natural numbers. For n E N, let [n]] denote (1, .n.. We use bold lowercase letters to represent vectors or sequences (e.g., æ), and bold uppercase letters to represent matrices (e.g., A). Given a vector and indices S i, we use 2/ to denote the sub-vector (Irj 1f,1,..... xz). Let O,, denote the n-dimensional all-zeros vector. Given vocabulary V. let V denote the set of length-n strings over V, and let V := U of all finite strings over V.
+ y denote the set
2.1 Turing machines
(single-tape) Turing machine (TM) is defined as a tuple ()) where
E is the tape alphabet, including a designated "blank" symbol 1, designated "start" symbol D, and numbers and 1.
Q is a finite set consisting of possible states. We assume Q contains designated start state Istart and designated halting state qhait.
(Left, Right} is transition function describing the rules used in performing each step of the TM.
6 Q x + Q
The machine has a single tape that is infinite to the right and bounded on the left. The tape is equipped with tape head. Initially, the tape (from the leftmost cell rightward) contains the start symbol P, finite {0, 1]--tt x (the imput), and the blank symbols 1 on the rest of its cells. The head starts at the leftmost tape cell, and the machine starts in the state qstart. The computation then repeats the following step until the machine enters Qhalt: the machine is in some state g E Q and reading symbol from the tape, and if Ö(g, o) = (q', o', 2) for some E (Left, Right), then the machine replaces a with of in the current cell, changes state from g to q', and moves the tape head one cell in direction z.
Space complexity Let s - N be non-decreasing function. The complexity class SPACE[s(n)] consists of all decision problems (0, 1)* + {0. 13 that can be decided by single-tape Turing machine using at most (ss(n)) tape cells on inputs of length n 3 The class PSPACE == UKEN SPACE[n*) is defined as the class of decision problems that can be solved in polynomial space.
+
2.2 Post machines
A Post machine (PM)
Post 1936 is defined as a tuple (E, Q, where
Σ is the tape alphabet, including a designated "blank" symbol 1, designated "start" symbol
D, and numbers and 1.
Q is a finite set consisting of possible states. We assume Q contains designated start state Istart and designated halting state qhait.
5 Q x - Q I {Stay, Right} the transition function, specifying how the machine
updates the tape and state.
The machine has a single tape that is infinite to the right and bounded on the left. The tape is equipped with two tape heads: the front head and the rear head. Initially, the tape (from leftmost cell rightward) contains the start symbol P, finite {0, 1---ttinngg x (the input), and the blank symbols 1 on the rest of its cells. The front head starts the leftmost tape cell, the rear head starts at the right end of the input, and the machine starts in state Isart. The computation repeats the following step until the machine
We implicitly assume that (n) 2 n, since tape cells required load input of length

---

enters Qhatt: if the machine is in state E Q with the front head reading symbol from the tape, and ō(g, Ø) (q',o'22) for some 2 {Stay, Right). then the machine (i) changes the state from q to L' (ii) moves the front head either one cell to the right if z = Right, and (iii) moves the rear head one cell to the right, and then write o'.
One can see that PM can also be modeled as an automaton equipped with a queue of unbounded size: the queue is initialized as the input æ, the front head points the first element of the queue, and the rear head points to the last one. In each step, the PM reads and deletes the first element of the queue and may append string to the tail.
Turing completeness of PM The model of PM is Turing complete, i.e., equivalent in computational power to TMs. Specifically,
Theorem 2. Given any single-tape TM running t(m) time and s(n) space, there is an equivalent PM rumning in (tt(n) x s(n)) time and using a s(n)-size queue.
This theorem has been implicitly proved in several places, e.g., [mmans] 2025 and Section 9.1 of [Pettorossi] 2014). For completeness, we present a proof in Appendix B The intuition is as follows. The PM's queue stores the non-blank part of the TM's tape in cyclic manner: If the TM head changes a symbol a to a' and moves right, the queue shifts by deleting a from the front and appending o' to the end. If the TM head moves left, the queue cyclically rotates by moving the last symbol to the front, where the appended symbol may need to depend on the leftmost two queue symbols. To avoid explicitly pre-reading the next queue cell, pop the leftmost queue symbol and store it in the finite-state controller, without appending; thereafter, at each step, (i) pop the next leftmost symbol, and (ii) append symbol determined by the two most recently popped symbols.
apply a one-step delayed append trick: initially,
2.3 Transformers
For simplicity of notation, we present the definition of a single-head transformer, since only single- head attention used in our proof. The definition of general multi-head transformers deferred to Appendix(C
Let V be finite vocabulary. A decoder-only transformer is a parameterized neural network TFa mapping from V" to V. Specifically, a transformer is a composition TF == out dec o ... dec, pos emb of four kinds of layers. Given sequence (V1, ** U.) E V it computes the next token U++1 as follows:
1. Token embedding layer (emb): For j < i, map each fn E V to vector emb(u;) E Rdd Here, d called the embedding size.
2. Positional encoding layer (pos): For j S i, add a positional encoding pos(i j) E Rd to the token embedding emb(u,), resulting in the initial imput representation h2 == emb(r;) + pos(i j). Here, we assume relative positional encoding scheme, where the encoding depends only on the distance between U and U;.
3. Decoder Layer (dec, f= L 1): Each decoder layer dec, consists of two sublayers: an self-attention layer, followed by fully-connecte feed-forward network. Residual connections applied around each sub-layer]" Here, following common practice Pérez et al. 2021 Merrill and Sabharwal [2024] 2023 QQu et al. [2024). Yang et al. [2025]. we use hardmax as a realistic abstraction of softmax. In fact, hardmax the instance-wise limit of zero temperature limit of softmax (Yang et al. 2025]. Consider a vector E R.. If the maximum value in 8 appears at t
positions, then the hardmax function defined coordinate-wise as:
1 if s max; 8k: 0, otherwise.
hardmax(s),
3.1. Single-head self-attention layer: Compute the attention score
of = hardmax (hi Q² K ).... ... (h) Q' h (()kk)))))
*For simplicity, we ignore layer normalizations from the standard transformer architecture RRafford et al. 2019 in our analysis. With a little more technical treatment as in [Li et al. 2024]. our results can be extended to transformers with layer normalizations.
5

---

and then
a Σ % of (h,),, where (1)) h. V and sf. is the j-th entry of s! 1=1
Here, Q³ K Vc E Rdxd are parametrized matrices. Then, this sublayer returns h h.00.6 W af ++ b h where W E Rdxd and be E IRd are parametrized.
3.2. Feed-forward network: Apply multi-layer fully-connected ReLU neural network FF to h (+0.5 and returns
h ++ = FF(h
(
h C+0.5
Output layer (out): The final output representations h are projected onto the vocabulary space using a linear transformation followed by arg max function:
U/+1 1 == out( = arg max (Wout h + bout), where Wrut E R Mixd and b b R
We say that a transformer operates with a context window of length if the generation of U:+1 depends only on the last s tokens U1-s+1," ...,, U/. A transformer is said be of p-bit precision each parameter is represented using bits. We define the bit-size of transformer TFg as x | meaning that the entire model can represented by using p x (0) bits. In this paper, when we refer to transformers, we mean transformers that are allowed to generate arbitrarily long immediate CoT steps, unless stated otherwise.
Definition 1. We define (INDOW[s(ni] as complexity class consisting the problems {0, 1)" {0, 1} that can be solved by a constant bit-size transformer with context window of length (s(nn) on inputs of length
3 Proof of main results
In this section, we prove Theorem 1. which characterizes the expressive power of constant bit-size transformers with context window of length s(n) in terms of the complexity class SPACE[s(n)). In particular, it implies that constant bit-size transformers are Turing complete.
First, we prove that any constant bit-size transformer with context window of length sn)) can be simulated by Turing machine using ((s(n)) space.
Theorem 3. For any non-decreasing function s(n) Z n, WINDOW[((n)) C SPACE[s(m)).
Proof. Let L [0,1)* + {0,1} be decision problem that be solved by constant bit-size transformer using a context window of length s(z). We sketch a Turing machine using (s)(n) space that solves T. by simulating the transformer. The Turing machine maintains buffer of size s(n) storing the latest sn) tokens in the transformer's context. To compute the next token generated by the transformer, the Turing machine simulates the computation procedure described in Section 2.3 using an additional (ss)n) working space. After generating the next token, the Turing machine updates the buffer by appending the new token and deleting the oldest token that slides out of the window, and then cleans the working space. By iteratively repeating this procedure, one can see that the Turing machine faithfully simulate the transformer's behavior and solve the problem L. O
In the following, we prove the reverse direction, which is the main technical part.
Theorem 4. Let TM be a single-tape Turing machine that, on input x E 13", uses at most s(n) space and runs for most t(n) steps. There exists constant bit-size transformer with context window of length (s((n) that, on input x, takes (t(n)) s(ni) Col' steps and then outputs TM(x).
As a consequence, we have WINDOW((s(n)) 2 SPACE(S for s(n) 2
Proof. Let TM be a single-tape Turing machine that runs ((n) steps and uses at most s(m) tape cells. By Theorem 2 the TM can be simulated by Post machine that runs in ((t(n) s(n)) time and

---

uses queue of size s(n). We slightly adapt the Post machine to ensure that the queue size remains exactly s(n) throughout the computation, or equivalently, that the distance between the front and rear heads on the tape remains fixed at s(n). Specifically, we pad the input with snn)
copies of special symbol # the right initially, and in each computation step, both the front and rear heads always move one cell to the right. One can easily see that such an adapted PM = (,,Q, simulates the Turing machine as well. Furthermore, without loss of generality, we assume
{0, 1, #}. Q {0, 1 for some E N, and that qstart 8(0, q) for any (a, meaning that once the computation starts, the Post machine leaves Istart immediately and never comes back.
We now construct constant bit-size transformer TF with a context window of length s(n) to faithfully simulate PM. The intuition is follows:
The ssi)-size queue is simulated by the s(n)-long context window, where the first element in the queue (or the tape cell pointed by the front head) corresponds the oldest token in the window, and the last element in the queue (or the tape cell pointed by the rear head) corresponds the newest token. Besides, we will let the vocabulary of the transformer be V - x Q, so that a token also tracks the PM state information.
As mentioned above, in each computation step of PM, the first element in the queue is removed, and a new element is added, so that the queue size remains the same. Correspond- ingly, in each CoT step of the transformer, the oldest token in the window slides out, and new token is appended.
The transition function of PM takes the last element in the queue and the current state as input, and outputs the next state and the next element. Correspondingly, by carefully choosing the parameters, the self ooff-attention layer retrieves the last element from the oldest token the window, and the current state from the current token; subsequently, feed- forward network is used to implement the transition function 8.
formally define the transformer TF as follows: let Σ Q 1, #) x {0, 13..
1. Token embedding layer
Map each token (ar, q) to vector emb(a, E R as follows:
0,1,0,0.,,000000000 0), if
emb(a,g) =
(1,001,0.gg0,0000000, if = (1.0,0.1.g.0.0000.0), if = #
(I)
2. Positional encoding layer embedding emb(w;) where
Add a relative positional encoding pos(i j) RC+* to the token
Octos
if < i i-j s()) 1;
pos(i - j)
(0c47, 1), (0.47, 2),
if = ifi-j = s(n) 1,
Then return h. = emb(u;) + pos(i - j)-
Decoder layer The transformer has only one decoder layer, and the decoder layer has only one
attention head. In the self-attention layer, we set the matrix K, K,Q,V V, W E Rdxd and e TRd where d = as follows:
Matrix K: it has only one non-zero entry Kc48.1 = 1;
Matrix Q: it has only one non-zero entry Qcts,cts = 1;
Matrix V: has four non-zero entries: Vet5,2 Ve+6,3 Ve+7.4 Vet8,ct8
Besides, we set the matrix W E dddd to be the identity matrix, and b 0c+8-
7

---

The feed-forwart network FF is designed to simulate transition function 6. Specifically, we let
if h4 (g. 1, 0, 0,3); ((H-u))))))
if hc+s 2:
(8(0,9)
(F h
(5(1,))
if h4:0+8 (g. 0, 1, 0,3); h4:c+8 = (g. 0, 0, 1,3);
(5(#.0))
RDI is the unit vector where the entry indexed by (o', g') is and any other entry is Here, e(o(
4. Output layer We set W to be the identity matrix and bout the all-zeros vector. Then the output layer outputs 21+1 arg ).
In the following, we show that the transformer TF faithfully simulates the Post machine PM. Let (01, 11) (2): ... denote the execution log of PM running element added to the queue and qj is the state when adding d;- Note that (Ø), q:) = (Iz (start) for i n, (di, 96)
{0, 1)", where a; is the i-th
(#, (start) for for i 2 s(n). Let U1, .2,... denote the token sequence in the context of TF when it takes e1 (x1, Istart). Un = (Ins (start) as input. We show by induction that for each 2 1, we have 0 (o., %).
1 i s(n), and ((0i-s(m)+1:9) (:) = (a++1, (++1)
Base case: S n
This case trivial.
Inductive case: n S s(n) the self-attention layer, observing that K Kh = (0,47, 1) = and
S0ct8, ifijjii, Q h3 = pos(i -
(4)
(0 1), if = i,
we have
8; hardmax
((h) Q. h. K),
(h) Q K)) (0, ;0,1) R
and
Si.j" (V h2) =
Si,j (0c44, (0c4,,15.000 15,244 k)044) (0c+4, 12,24 1).
a:
1=1
j=l
Then
h W. a; + b h a, + h2 ( h2.2: 2).
In the feed-forward network layer, h. 0.5 is mapped to FF(h: 0.5) + h
0.5 which is ((#.qu)rr)) according
to Equation 3 Finally, the output layer outputs (#, Astars) as desired.
Inductive case: 2 s(n)
the self-attention layer, observing that K h = (0c+7, 1) = 1 and
0. if s(n) + < < i;
Q h = =pos(i- 5)
1, if = i,
(5)
2, if = i- ins +1,
we have
s; = hardmax (hhio0n)41 Qh K),
(h) Q, K) = (1, .1.00...00 E (m))))
and
si (0ct4, h0 2:: 19 A9.44) (0ct4, h(-(())+122)))))
a
j=i-s(n)+1
Then
h 0.5 a; + h (h 1:04 h s 1.22
In the ferward network layer, noting that by the induction hypothesis, we have
h 0.5
h1,50044 9t, and h 0.5
h,005:0477 h2-0(m)-1.24 0--s(m++1
1,5:44

---

The vector h 0.5 is mapped to FF(h; + h which is -(0))-))))1-)))) according to Equation (0441,441), then one can see that the output layer outputs
33. Recall that ((0)-s(n)+11
(1++1, 96-1) 1) as desired.
Now, we have shown that vi = (ax; (;) for any i 2 and thus finished the proof.
Remark 4. As we can see from the proof. to simulate the given TM on longer inputs. what we need to do is just change the relative positional encoding according to Equation 2 without changing all other model parameters.
Remark 5. We briefly compare our construction with existing Turing- curing-completeness: proofs and highlight why our construction achieves constant bit-size. In (Pérez el al.) 2027] and related follow- ups, the query may attend to many earlier tokens; when multplee positions tie for the maximum score, the hardmax outputs fractions such as 1/t, which requires the precision to grow with t. The proof of Li et al. [2024] encodes the simulated circuit directly into the absolute positional encoding, rather than into the parameters. Consequently, as the circuit expands, the positional encoding must also grow in dimension, so the embedding size is no longer constant.
In contrast, our construction leverages the automaton- -lik behavior of Post machines, which is simpler and more regular than the head movements of Turing machines the wiring patterns of circuits. As a result, at each Co'T' step the query attends to exactly one token, specisically the token located s(n) positions earlier. This fixed-offset attention can be implemented purely through relative positional encoding, without any additional arithmetic operations.
In particular, the input to hardmax is always one-hot, is the resulted attention distribution. As an alternative of hardmax, one could replace hardmax with the right-most hardmax function (Yang) et al. 2024y.
Combining Theorems 3 and 4 immediately conclude main theorem.
Theorem 1. For any non decreasing function s(n) 2 n, we have WINDOW[ (m)) SPACE(s(n)). In particular, HINDOW/poly(n) = PSPACE.
4 Conclusions and Discussions
In this work, we have shown that a constant bit-size transformer, with sufficiently long context window, can simulate any Turing machine on arbitrarily long inputs. We further proved that the complexity class SPACE(s(n)) precisely characterizes the expressive power of constant bit-size transformers with a context window of length snn), suggesting that the context window length needs to scale only with the space complexity rather than the time complexity as suggested by previous results. Our proof leverages the behavioral similarity between transformers and Post machine, which offers new insights into the mechanism underlying the reasoning abilities of transformers. We list some future directions:
Simulation efficiency: Our construction requires ((((n) - s(n)) CoT steps, which is potentially prohibitive for practical applications. It would be interesting and important to investigate whether this slowdown can be avoided without compromising optimality in other aspects.
Positional encodings: Our construction employs an nonstandard relative positional encoding. is open whether it can be replaced with fixed absolute positional encodings or other standard relative positional encodings. Moreover, our positional encoding explicitly depends on the assumed space upper bound, and it is unclear how this bound could be inferred automatically.
Learnability and empirical validation: Our contribution is purely about expressiveness. Whether standard training procedures can learn such behavior is an important open problem. How well our construction behaves in practice also remains to investigated.
5 Acknowledgments
The authors thank the anonymous NeurIPS reviewers for their valuable suggestions.
Qian Li's work was supported by Shenzhen-Hong Kong Science and Technology Innovation Coop- eration Zone Project N0.-77/WS-KCCCB--0000 Hunan Provincial Natural Science Foundation (Grant N0.2024115128).
Yuyi Wang's work was supported by the

---

References
Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt,
S. Altman, S. Anadkat, al. GPT-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
Anthropic. The claude model family: Opus, sonnet, haiku, 2024.
S. Arora and B. Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
S. Bhattamishra, A. Patel, and N. Goyal. On the computational power of transformers and its implications in sequence modeling. In Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455-475, 2020.
M. Davis, R. Sigal, and E. J. Weyuker. Computability, complexity, and languages: fundamentals of theoretical computer science. Elsevier, 1994.
A. Dubey, A. Jauhri, A. Pandey, Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Yang. A. Fan, et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21788, 2024.
G. Feng, B. Zhang, Y. Gu, H. Ye, D. He, and L. Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36: 70757-70798, 2023.
Gemini, R. Anil, S. Borgeaud, J.-B. Alayrac, J. Yu, R. Soricut, Schalkwyk, M. Dai, A. Hauth, K. Millican, al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805 2023.
M. Goldblum, M. A. Finzi, K. Rowan, and A. G. Wilson. Position: The no free lunch theorem, kolmogorov complexity, and the role of inductive biases in machine learning. 2024.
D. Guo, D. Yang. H. Zhang. Song, R. Zhang. R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. Deepseck-rl: Incentivizing reasoning capability in ilms via reinforcement learning. arXiv preprint arXiv:2501. 12948, 2025.
R. A. Hearn and E. D. Demaine. Pspace-conee ceppee-completensss of sliding- block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, 2005.
D. Hendtycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arX1v:2103.03874, 2021.
M. Hutter. Universal artificial intelligence: Sequential decisions based on algorithmic probability.. Springer Science & Business Media, 2005.
R. Impagliazzo and R. Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001.
C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan. Swe-bench: Can language models resolve weal-world github issues? arXiv preprint arXiv:2310.06770, 2023.
Y. Lecun. Meta ai, open source, limits of llms, agi & the future of ai, 2024. https::/www. com/vattchyv=5t111 $40
L. Levin. Universal sequential search problems. Problemy peredachi informatsii, 93):115--16, 1973.
I. A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, (11::11537, 1984.
Z. Li, H. Liu, D. Zhou, and T. Ma. Chain of thought empowers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, 2024.
10

---

W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of log- precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
W. Merrill and A. Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. 2024.
W. Merrill and A. Sabharwal. A little depth goes long way: The expressive power of log-depth transformers. CoRR, abs/2503.03961, 2025.
Pérez, P. Barceló, and J. Marinkovic. Attention is turing-complete. J. Mach. Learn. Res., 22: 75:1-75:35, 2021.
html
A. Pettorossi. Elements of computability, decidability, and complexity. Aracne editrice Srl, 2014.
E. L. Post. Finite combinatory 1936.
The journal of symbolic logic, 133):103-105,
R. Qiu, Z. Xu, W. Bao, and H. Tong. Ask, and it shall be given: Turing completeness of prompting. CoRR, abs/2411.01992, 2024.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
D. Rein, B. L. Hou, A. C. Stickland, J. Petty, R. Y. Pang. J. Dirani, J. Michael, and S. R. Bowman. Gpqa: graduate-level google-proof q&a benchmark. arXiv preprint arXiv:2311.12022, 2023.
J. Schmidhuber. Optimal ordered problem solver. Machine Learning, 54:211-254, 2004.
D. Schuurmans, H. Dai, and F. Zanini. Autoregressive large language models are computationally universal. arXiv preprint arXiv:2410.03170, 2024.
A. Sistla and E. M. Clarke. The complexity of propositional linear temporal logics. Journal of the ACM (JACM), 32(3):733-749 1985.
L. Strobl, W. Merrill, G. Weiss, D. Chiang, and D. Angluin. What formal languages can transformers express? survey, Transactions of the Association for Computational Linguistics, 12:543-561, 2024.
C. Umans. Decidability and tractability: Solution set 3, 2025. https://users.com cms caltech http//umann//221//snss..
R. R. Williams. Simulating time with square-root space. arXiv preprint arXi::250.11777, 2025.
A. Yang, D. Chiang, and D. Angluin. Masked hard-atte aatd-attttioon transformers recognize exactly the star- free languages. A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024.
C. Yang, N. Srebro, D. McAllester, and Z. Li. Pencil: Long thoughts with short memory. arXiv preprint 2rX3v:2503.14337 2025.
N. Zubié, F. Soldá, A. Sulser, and D. Scaramuzza. Limits of deep learning: Sequence modeling through the lens of complexity theory. arXiv preprint 40Xiv:2405. 16674, 2024.

---

A Modifications on Transformers in Turing Completeness Proofs
Existing proofs of buring-completencee for Transformers typically departure from the vanilla archi- tecture and make specific modifications, Pééezz et al. [2021] consider a Transformer with an absolute positional encoding given by the triplet (1, 1/2²) position i. In their construction, the attention score is defined as the negative absolute value of the dot product, and the attention mechanism uses average-hai harde attention. Moreover, the feed-forwart layers employ sigmoid activations in place of ReLUs. Merrill and Sabharwal (0224 dispense with positional encodings altogether and instead adopt Strict Causal Masking, where attention at position can access all tokens up to position but not the current token i. Their construction also uses average-hard attention and introduces Projected Pre-Norm: an arbitrary linear projection is allowed before layer normalization. In the proof Li et al. (002)) the simulated circuit is directly encoded into the absolute positional encoding, rather than into the parameters. Qiu et al. [2024) consider Transformers with nonstandard absolute positional encodings. In their construction, the query, key, and value maps in the attention sublayer are implemented as ReLU networks rather than linear transformations. This work employ nonstandard relative positional encodings.
B Proof of Theorem
Let TM = (I, 0) be a single-tape Turing machine that runs in time t(n) and space s(n). We construct an equivalent Post machine PM (E', Q', that simulates TM within O(t(n) s(n)) time and uses queue of size at most s(n).
Queue alphabet We define the queue alphabet >' ;= fo, E}. Here, i and R are temporary markers used for simulating a left move of TM's head. Specifically, temporarily marks the current head cell, while - temporarily marks its left neighbor.
Delayed append trick PM maintains a logical queue which represents the non-blank segment of TM's tape in cyclic manner. Formally, we realize L as L = R o Qphys where
is is register in the finite control storing the leftmost symbol of L, and
Ophys is the actual queue content. Thus 1pphys
[L| 1.
With this representation, the appended symbol is no longer restricted to depend only on the leftmost symbol of L; it can now be determined by the two leftmost symbols.
Initialization Initially, TM's tape contains the start symbol P. followed by the input ær and then blanks. Accordingly, the logical queue 7. is initialized to (D, ær): the first symbol > is placed in the register R, and the remaining symbols x are stored into Qphys- During the simulation, we will keep the following invariant:
Right before each simulated step, the leftmost cell of correponds to TM's head cell; its symbol is either unmarked or carries the mark, while all other cells of L are unmarked.
Simulation of one step Suppose TM in state q and its head reads a from cell i. Let 5(q. (g', a',,) with E {Left, Right). This means that TM overwrites cell i with o', change state from to q', and moves its head one cell in direction z.
Move Right. PM deletes the lefumost logical symbol and appends o' to L. thereby overwriting tape cell i. the resulting leftmost logical symbol D. indicating that TM has extended its non-blank segment by one blank cell to the right, then PM additionally appends blank symbol
Move Left. PM deletes the leftmost logical symbol and appends á' L, thereby overwriting tape cell i. It then cyclically rotates L, until the second leftmost logical symbol carries the mark. At this point, the first and second of I, correspond to tape cells 1 and i, respectively. PM then adds a mark to the first symbol and removes the mark from the second, after one additionally cyclic sweep of L; concretely,
1. delete the leftmost element and append the same symbol with the mark :; then
12

---

2. delete the leftmost element and append the same symbol with no mark; then
3. cyclically rotate L until the leftmost logical symbol carries the mark.
Analysis By induction on the number simulated steps, one can check that the invariant is maintained throughout the simulation, and hence PM faithfully simulate TM. For right move, PM performs O(1) queue operations. For a left move, it performs two full sweeps L, costing O(LL)) (s)) operations. Therefore, the overall running time is O(t(n) s(n)), completing the proof.
C Multi-head Transformers
multi-head Transformer employs the following multi-head self-attention layer in place of the single-head self-attention layer, while all other components remain the same as in the single-head transformer.
Multi-head self-attention layer: For each head = 1,2,,.. , H. compute the attention score
$ hardmax (hi Q h K&), mM ,h, Qh. h k¹)
and then
a Σ j=1
S 2 (h)), where (1) == h Ví
Here, o K Vi E Rddx//H are parametrized matrices. By concatenating the H heads, we obtain a: ((a))) T ... (a IT) E Rd. Then, this sublayer returns
h 2+05 W af + be + h
where V E Rdxd and be Rd are parametrized.
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: In Section 5 we prove the theoretical claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: Section discusses the limitations.
14

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification: We provide the setting and preliminaries in Section 2 and the complete proof in Section
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA].
Justification:
This paper does not include experiments requiring code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (tttps://nips.cc.
Bablic//uides/Cont http://oeeeumssssooooooo.oooe
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (ht
7 ctaipsscc/public/guiiee gwwp://ggeeeeeeeeeeeoeee www.eubmisssiiiicooooooo..oo...e Pollccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes].
Justification: The research conducted in this paper conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This paper is foundational research and not tied to particular applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: This paper poses such risks.
Guidelines:
18

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
This paper does not use existing assets
Guidelines:
The answer NA that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paper swi th code. com hinndataseess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA].
19

---

Justification:
This paper does not involve crowdsourcing experiments nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA].
Justification: This paper does involve crowdsoureing experiments nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Answer: [NA].
Justification: In this paper, the LLM is used only for writing and editing, and the core method development in this research does not involve L.MMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve L.MMs any important, original, non-standard components.
Please refer to LLM policy httppp///eaarrps.cc///oeeerrrrre for what should or should not be described.
20


Reviews:
[{"review_id": "61khjksQWb", "reviewer": "Reviewer_aGq8", "summary": "Transformers with Chain of Thoughts (CoTs) were initially proven by [Perez et al. 2021] to be Turing-complete. Essentially, this means that they are allowed to feed the output back into the input several times (that is, \"think out loud\") before outputting the final result of the computation. In subsequent years, researchers have revisited the result from [Perez et al. 2021] by simplifying the proof, or removing some unpractical assumptions in the model. For example, in the following paper Bhattamishra et al. simplified some of the assumptions in [Perez et al.] including replacing positional encodings with positional masking:\n\nSatwik Bhattamishra, Arkil Patel, Navin Goyal: On the Computational Power of Transformers and Its Implications in Sequence Modeling. CoNLL 2020: 455-475\n\nIn this paper and in [Perez et al. 2021], finite but unbounded precision is assumed. More precisely, this means that computation is done over rational numbers, which amounts to potentially infinitely many decimal places (it is possible to actually restrict finitely many decimal places, but the number of required decimal places will grow in the size of the input). This result has been further refined in [Merrill and Sabharwal 2023] with an even simpler usage of positional masking and additionally complexity analysis.\n\nA different set of assumptions for Turing-completeness was obtained by [Liu et al. 2024], where the authors use an unbounded \"embedding dimension\" but constant precision. Roughly speaking, this means that different parameter instantiations (possibly of different dimensions) exist for different input lengths. [Actually, the paper itself doesn't talk about another proof of Turing completeness of transformers, but as the current submission also acknowledges it follows from [Liu et al. 2024]]. \n\nThe current paper improves on and simplifies the result by [Liu et al. 2024] in that the dependence on the input length exists only in the relative positional encoding; the other parameters stay the same. More precisely, the bit size of a transformer is essentially the number of bits (with only floating points allowed, not rational numbers) required to represent the parameters of the transformer. Crucially, a relative positional encoding is allowed as a parameter. With this assumption, the authors establish a \"universal CoT transformer\" with a constant bitsize. Actually, this translates to non-fixed (absolute) positional encoding that depends on the input length. Additionally, the current paper also assumes a sliding window of a non-fixed size on the concatenation of the input and the intermediate CoT results, which is reasonable. \n\nAdditionally, the paper also proves a characterization of the complexity class SPACE[s(n)] of problems solvable in s(n) space, by allowing a sliding window of size s(n). The proof goes by encoding a universal Post Machine (a queue machine) by means of a CoT transformer. Note that the number of bits required to store values in the intermediate computation might also grow in the length of the input (for example, owing to the use of average hard attention mechanism, which divides by a non-fixed number).", "questions": "- Can you say what happens in the case of a fixed \"absolute\" positional encoding?\n- Is it possible to replace your use of positional encoding with a casual positional masking?\n- Can you explain key technical differences in the proofs in your paper compared to [Perez et al. 2021] and [Li et al. 2024]?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "To the best of my knowledge, this is the first Turing-completeness proof that assumes some sort of constant bit size in the entire parameter set. The only catch is that one has to use relative positional encoding, which translates to a parametric absolute positional encoding. That said, unlike [Li et al. 2024], this is the *only* parametric component; the others are fixed. To the best of my knowledge, this is the strongest Turing-completeness result under the \"constant precision\" regime.\n\nThe proof is also relatively simple and quite nicely presented. Essentially, the queue content in the post machine corresponds to the sliding window content in the CoT transformers. The explicit construction also makes it clear what varies in the size of the input. My only quibble here is that the authors have 1.5 extra pages, which can be used to provide more intuition of the proof (as well as some definitions). \n\nIn addition, I found that some definitions are excessively overcomplicated. For example, multi-head attention is defined in the paper, whereas only single-head attention is used in the proof. \n\nOverall, I think the strengths overweigh the weaknesses in the paper and I am leaning towards acceptance.\n\nMinor:\n- l. 145: \"in some state\"\n- l. 180: $s^l_{k,i,j}$ is not defined. Do you mean the jth entry of $s^l_{k,i}$?\n- l. 247: at first sight, it seems that you need to know i and j in pos(i-j), instead of just the difference i-j. Justify that this is not the case.", "was_revised": true, "final_justification": "The authors addressed my questions. I keep my accept score.", "rebuttal": "We greatly value the reviewer's suggestions and recommendations. We will revise the related parts accordingly.\n\n**Q1:** Note that the number of bits required to store values in the intermediate computation might also grow in the length of the input (for example, owing to the use of average hard attention mechanism, which divides by a non-fixed number).\n\n**A1:** In our construction, the attention weight is always one-hot: at each step, exactly one token in the window receives a non-zero score. So the hardmax output is $\\{0,1\\}$-valued, no division ever occurs, and the required precision stays constant.\n\nAs an alternative, one could replace hardmax with the right-most hardmax used in the paper “Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages” (We thank Reviewer Y1kW for this suggestion).\n\n\n**Q2:** Can you say what happens in the case of a fixed \"absolute\" positional encoding?\n\n**A2:** *With the constant bit-size constraint.* Whether a constant bit-size transformer with a fixed absolute positional encoding can still be Turing complete is an open problem. We currently have no proof either way.\n\n*Without the constant bit-size constraint.* Our second core result still holds: it remains sufficient for the context window length to scale with the space complexity of the simulated Turing machine.  A simple choice of the fixed absolute PE is \n\n$\\mathrm{poi}(i)= i \\mod p$ where $p>s(n)$.\n\nIn our proof, the Post machine's queue size keeps exactly $s(n)$ throughout the computation, or equivalently, that the distance between the front and rear heads is fixed at $s(n)$. So in each CoT step, the query attends to the only token exactly $s(n)$ positions earlier, which can retrieved with this absolute PE alone.\n\n\n\n**Q3:** Is it possible to replace your use of positional encoding with a casual positional masking?\n\n**A3:** Yes.  As noted in A2, in our construction, the query attends to the only token exactly $s(n)$ positions earlier. We can therefore switch to a causal positional masking scheme that allows token $i$ to attend only to token $i−s(n)$. All other parts of the proof remain unchanged.\n\n\n**Q4:** Can you explain key technical differences in the proofs in your paper compared to [Perez et al. 2021] and [Li et al. 2024]?\n\n**A4:**  \n- *[Perez et al. 2021] and related follow-ups.*  In these proof, the query may attend to many earlier tokens. When multiple positions tie for the maximal score, the hardmax outputs fractions such as $1/t$, which requires the precision to grow with $t$.\n\n- *[Li et al. 2024].* This proof encodes the simulated circuit directly into the absolute PE (rather than into the parameters). As the circuit (hence the input length) expands, the PE must grow in dimension, so the embedding size is no longer constant. \n\n- *This work.* The Post machine’s automaton-like behavior is much simpler and more regular than the head-moving  behavior of TMs and the wiring of a circuit. This let our construction satisfy a nice property: at every CoT step the query attends to exactly one token, always the token $s(n)$ positions earlier. This fixed-offset attention can be realized solely by a relative positional encoding without any additional arithmetic operations. \n\nIn addition, we will also revised the other part as suggested, including adding the missing references, simplifying excessively overcomplicated definitions, and fixing typos."}, {"review_id": "J1OvbzRJO6", "reviewer": "Reviewer_PMuH", "summary": "This paper presents a theoretical result on the computational power of Transformers. The authors prove that a Transformer with a constant bit-size (i.e., fixed number of parameters and fixed numerical precision) is Turing complete, capable of simulating any Turing machine on inputs of arbitrary length, provided its context window is sufficiently long. Theoretical statements and proofs are provided.", "questions": "See the Weaknesses part above.", "limitations": "The authors do not discuss limitations of this work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The paper is well-motivated and clearly written.\n- The paper provides more than a simple \"yes/no\" answer to Turing completeness. The equivalence creates a direct and formal link between architectural parameters (e.g., context length) and computational budgets (memory/space).\n\n## Weaknesses\n- **Expressivity vs. Learnability**: The proof is a constructive one, meaning it shows that a Transformer with specific, carefully engineered parameters exists. It does not address whether this complex, algorithmic behavior could be learned using standard gradient-based training methods. This is a significant gap between the theoretical capability and practical reality.\n\n- **Computational Cost of Simulation**: The simulation requires a number of chain-of-thought (CoT) steps that scales with O(t(n) * s(n)), where t(n) is the time complexity of the original Turing Machine. For many problems, this is prohibitively large and far exceeds the number of reasoning steps seen in practice, which may limit the direct applicability of the result.\n\n- **Idealized Model Assumptions**: The construction relies on an idealized Transformer model that uses hardmax attention and omits layer normalization. While the authors note these are common simplifications in theoretical work, it creates a disconnect from the standard architectures used in practice.\n\n- **Lack of Empirical Validation**: The work is purely theoretical. While the claims are powerful, the paper would be strengthened by even simple experiments that explore or demonstrate aspects of the proposed construction, which could provide insights into its feasibility or the challenges in realizing it.", "was_revised": true, "final_justification": "The rebuttal addressed my concerns, so I am raising my score to 4.", "rebuttal": "We appreciate the valuable comments and feedback. We provide a detailed clarification hoping to address the reviewer’s concerns.\n\n\n\n**Q1:** About Expressivity vs. Learnability.\n\n**A1:** Our contribution is purely about expressiveness. Whether standard training procedures can learn such behavior is outside our current scope and remains an important open problem. We will cite it as a future direction in the next version.\n\n\n\n**Q2:** About Computational Cost of Simulation.\n\n**A2:** We acknowledge this limitation, and have already cited it as an open problem in the Conclusion.\n\n\n\n**Q3:** About Idealized Model Assumptions.\n\n**A3:** Hardmax vs. softmax: Hardmax is a standard theoretical proxy, see e.g. [Perez et al. 2021], [Merrill and Sabharwal 2024], and [Li et al. 2024]. Importantly, our transformer construction is robust to switching to softmax: a softmax with any sufficiently small temperature will select the same unique-max token with probability $\\approx1$.\n\nLayer normalization: As noted in our footnote,  our results can be extended to transformers with layer normalizations, by adopting the trick from [Li et al. 2024]. Specifically, we can replace each constant-precision real number with a constant-dimensional $\\pm 1$-valued vector whose coordinates sum to zero, so that layer normalizations levels the computation unchanged.\n\nWe will make both points clearly in the next version.\n\n\n\n**Q4:** About Lack of Empirical Validation.\n\n**A4:** We agree that empirical experiments would be valuable for justifying the practical feasibility. We will cite it as a future direction in the next version.\n\n\n**Q5:** The authors do not discuss limitations of this work.\n\n**A5:** In the next version, we will add more discussions on limitations and future directions:\n\n- CoT length: Our current simulation needs $O(t(n) s(n))$ CoT steps; reducing this to $O ⁣(t(n))$ remains an open problem.\n- Learnability and empirical validation: Our contribution is purely about expressiveness. Whether standard training procedures can learn such behavior is an important open problem. How well implementations behave in practice also remains to be investigated.\n- Positional encodings: Our construction employs an nonstandard relative positional encoding; extending the result to fixed absolute positional encodings or other standard relative positional encodings is open."}, {"review_id": "wG6dVe3q6Y", "reviewer": "Reviewer_AC2j", "summary": "This paper is part of an active and growing line of theoretical research on the expressive power of transformer architectures. The central question is: how expressive are transformers as language deciders compared to traditional resource-bounded models like time- and space-bounded Turing machines (TMs)? This is a relatively new area with many open directions. A foundational result by Pérez et al. showed that certain transformer models are Turing complete when allowed to use Chain-of-Thought (CoT) reasoning, enabling them to simulate arbitrary computations. Since then, several works have explored what transformer parameter settings are necessary and sufficient to capture various classical models (e.g., space, time, Boolean circuit depth). A key parameter in this context is precision—the number of bits used to represent real numbers. Prior work established that logarithmic precision suffices for general computation.\n\nThis paper advances the field by showing that even constant-bit precision—a fixed number of bits—suffices to simulate Turing machines efficiently. Specifically, the authors define a transformer-based class ${\\rm WINDOW}(s(n))$, where the ith token depends only on the preceding $s(n)$ tokens, and prove that ${\\rm WINDOW}(s(n)) = {\\rm SPACE}(s(n))$ for all $s(n) ≥ n$. Thus, constant-precision transformers with an attention window of size $O(s(n))$ recognize exactly the languages in ${\\rm SPACE}(s(n))$.", "questions": "It would be interesting for the authors to explore and discuss the implications of their results when $s(n)$ is sublinear (e.g., $O(\\log n))$. Does ${\\rm WINDOW(O(log n))$ capture LOGSPACE? Are constant window transformers interesting?", "limitations": "There is no explicit Limitation section. But I am not concerned about that for this theoretical work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper makes a significant theoretical contribution by precisely characterizing the computational power of constant precision transformers in terms of classical complexity classes. It is indeed good to know that constant-bit precision suffices and this result is  relevant to both theory and practice.\n\nWeaknesses: The literature review could be more thorough. In particular, the authors should look at the recent survey “What Formal Languages Can Transformers Express? A Survey” by Strobl et al. (https://arxiv.org/abs/2311.00208), which provides a comprehensive overview of formal language expressivity results for transformers. Comparing and contrasting your result with  relevant results cited in this survey would help contextualize the current contribution within the broader research landscape. For example, in results such as those by Merrill and Subharwal involving ${\\rm CoT}(T(n))$, what is the implicit or explicit window size? Is it effectively $T(n)$? Clarifying how this relates to the ${\\rm WINDOW}(s(n))$ definition would strengthen the positioning of the result.", "was_revised": true, "final_justification": "The authors have promised to add more details and relation to prior work which was my earlier concern. I will update the score to 5.", "rebuttal": "We sincerely thank the reviewer for the valuable comments and feedback. We provide a detailed clarification to address the reviewer’s concerns.\n\n\n\n**Q1:**  The literature review could be more thorough. The recent survey “What Formal Languages Can Transformers Express?” by Strobl et al. offers a thorough overview of expressivity results.....For example, in results such as those by Merrill and Subharwal involving , what is the implicit or explicit window size? Is it effectively ? Clarifying how this relates to the definition would strengthen the positioning of the result.\n\n**A1:** We will broaden the related work section as suggested. In particular, also suggested by Reviewer Y1kW, we will add a table comparing the existing Turing-completeness proofs in terms of required precision, embedding size, positional encoding scheme, effective window size, and CoT length.\n\nAll existing Turing-completeness proofs, including that of Merrill and Subharwal (2023), require the context window to cover the entire context. So the implicit window length is $O(T(n)+n)$, where $T(n)$ is the number of CoT steps.\n\n\n\n**Q2:** It would be interesting for the authors to explore and discuss the implications of their results when is sublinear (e.g., . Does $\\mathrm{WINDOW}(O(\\log n))$ capture LOGSPACE? Are constant window transformers interesting?\n\n**A2:** Note that the entire input string is presented before the transformer starts generating CoT tokens, and at every step the transformer can look back only $s(n)$ positions.  If $s(n)<n$, the first $n−s(n)$ input symbols are permanently outside the transformer's attention and can never influence any CoT token.  Consequently, $\\mathrm{WINDOW}(O(\\log⁡n))$ does not capture LOGSPACE. In fact, it cannot recognize any language that depends on the whole input."}, {"review_id": "c3ZUUOb0xd", "reviewer": "Reviewer_Y1kW", "summary": "Allowing CoT steps enables transformers with the computational power to perform complex reasoning tasks. A body of theoretical work has shed light on this phenomenon through proof that transformers can simulate Turing machines, under various architectural assumptions. This work investigates the setting where the precision and context window of the transformer must be bounded, and provides a novel proof of Turing-completeness using Post machines. They show that transformers with constant bit-size and context window s(n) are equivalent to SPACE[s(n)]. The computational behavior of Post machines aligns very well with CoT.", "questions": "Questions\n- Is it possible to achieve the same effect of using the pos(i,j) positional encoding using some kind of an attention construction? While no longer constant bit-size, this would still be interesting in contrast with (https://arxiv.org/abs/2503.14337) by achieving space-efficiency without their reduction process. \n- Other proofs also use non-standard positional encodings (like pos(i)=i^2 or 1/i), but in this case the positional encoding depending on s(n) seems even more nonstandard. Could the authors make these and other assumptions more clear? \n- Is there more to say about the “natural alignment” between Post machines and transformers? Any future work or practical implications? There is a healthy amount of room left in the paper. \n\nSuggestions\n- It could be quite informative for the authors to create a table of various CoT Turing-completeness proofs to compare their result with others in the literature. For instance, the table could have columns for “precision” and “positional encoding” to clearly demonstrate the distinction with previous work. \n- Technically, the definition of hardmax computing 1/t means that O(log n) bit precision is possible in the transformers. Your construction gets around this by enforcing that only one item in the context window has non-zero score. A note could be made about this, or you could use some form of argmax (like right-most hardmax https://arxiv.org/abs/2310.13897) \n- It seems that [Liu et al. 2024] should be [Li et al. 2024]? \n- There seems to be a typo on line 263 with the angle brackets", "limitations": "I think the authors could be more upfront about the positional encodings used and other assumptions they make, but otherwise things are pretty clear.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- Very clearly written, constructions are shown in detail and I could follow them without much difficulty. \n- The identification of Post machines as a natural analogue of CoT computation is very nice and I agree sheds more light on the behavior of transformers with CoT than the proofs with Turing machines. \n- The work highlights the sometimes subtle differences between different algorithms that transformers may use in CoT\n\n\nWeaknesses\n- I’m not sure that the other proofs requiring an O(log n) precision is a very severe weakness that needs addressing – in practice the precision is often large compared to the sequence length (e.g. float16 can handle inputs on the order of 10^8 tokens without any problems (https://arxiv.org/pdf/2210.02671)). \n- If I understand correctly, the construction crucially upon the relative positional encoding pos(i,j) which sweeps some things under the rug. While other works use non-constant bit precision in order to compute the token to attend to, the pos(i,j) simply provides location of the Post machine’s head, thus streamlining the process. \n- For non-theory readers it would be informative to add a brief section on limitations or practical insights (given that you have 1.5 pages of space left over). For instance, what problems are solved in (say) an O(1) sized context window and how it compares to what problems transformers with CoT can solve in practice.", "was_revised": true, "final_justification": "The authors addressed my concerns and provided an interesting discussion. My concern about computing S(n) was not completely assuaged, so I maintain my score of accept (5).", "rebuttal": "We greatly appreciate the reviewer’s constructive comments and suggestions. We will polish the manuscript according to the review.\n\n\n\n**Q1:** I’m not sure that the other proofs requiring an O(log n) precision is a very severe weakness that needs addressing – in practice the precision is often large compared to the sequence length (e.g. float16 can handle inputs on the order of 10^8 tokens without any problems).\n\n**A1:** We agree that float16 or float32 is already sufficient for most current benchmarks. The issue could be relevant in lifelong continual learning setting: the agent may accumulate an ever-growing history, and the input length keeps increasing. \n\nIn addition, proving that fixed precision suffices also provides a justification for the use of fixed-precision formats (and even aggressive quantization) in hardwares.\n\n\n\n**Q2:** If I understand correctly, the construction crucially upon the relative positional encoding pos(i,j) which sweeps some things under the rug. While other works use non-constant bit precision in order to compute the token to attend to, the pos(i,j) simply provides location of the Post machine’s head, thus streamlining the process.\n\n**A2:** The key ingredient is not the particular nonstandard relative PE itself but the following property of our construction:\n\n- **Fixed-offset attention:** At each step, the query attends to the only token exactly $s(n)$ positions earlier, which can be retrieved solely by a relative positional encoding without any other arithmetic operations.\n\nIf we drop the constant bit-size requirement and switch to a fixed absolute PE, our second core result still holds: it remains sufficient for the context window length to scale with the space complexity. For example, one can use the absolute PE is $\\mathrm{poi}(i)= i \\mod p$ where $p>s(n)$. Because of the attention offset is always $s(n)$, the transformer can still retrieve the Post machine head using the absolute PE alone.\n\nIn addition, the reviewer may see our response A4 to Reviewer aGq8 for an explanation of the key technical differences from previous proofs.\n\n\n\n**Q3**: For non-theory readers it would be informative to add a brief section on limitations or practical insights (given that you have 1.5 pages of space left over). \n\nIs there more to say about the “natural alignment” between Post machines and transformers? Any future work or practical implications? There is a healthy amount of room left in the paper.\n\n**A3:** We will add the following discussions on limitations and future directions:\n\n- CoT length: Our current simulation needs $O(t(n) s(n))$ CoT steps; reducing this to $O ⁣(t(n))$ remains an open problem.\n- Learnability and empirical validation: Our contribution is purely about expressiveness. Whether standard training procedures can learn such behavior is an important open problem. How well implementations behave in practice also remains to be investigated.\n- Positional encodings: Our construction employs an nonstandard relative positional encoding; extending the result to fixed absolute positional encodings or other standard relative positional encodings is open.\n\nWe will add the following discussions on practical insights: Our theorem establishes that: a single, fixed bit-size transformer can execute any algorithm whose working memory fits in the context window. It has several practical insights. \n\n- **Understanding the general reasoning capability.** Although our theorem is stated per task and may look like in the \"one-model-one-task\" paradigm at the first glance, it in fact leads to a universal-model perspective: a constant bit-size transformer can simulate a universal TM, i.e., a general-purpose programmable computer. Hence, a *single* specific model, once trained, can execute any program that is provided in the prompt or embedded into its parameters. This offers an interpretation on how current general-purpose LLMs handle diverse tasks. \n\n  As noted in Remark 1, the program need not to be task-specific; it could implement some meta-tasks, such as designing new algorithm.\n\n- **Engineering guidance.** Aiming for stronger deductive reasoning ability, a line of engineering efforts tend to lengthen context window instead of growing parameter count. Our result formally justifies this strategy: extending the window alone is sufficient. Moreover, a window that grows only polynomially with the input already suffices to solve every PSPACE problem, including game-tree search and mathematical proofs.\n\n- **Implications for the AGI debta.** There is a ongoing debta on whether transformers can approach AGI. A common negative view (e.g. [1,2]) argues that transformers, limited by finite size and window, cannot approximate unbounded computation.  Our result shows that, at least for deductive reasoning tasks (whose solutions depend only on explicit information, such as Go or math), scaling window length alone is theoretically sufficient, and continually scaling up size is not a principled requirement.\n\n[1] Yann Lecun. Meta AI, open source, limits of LLMs, AGI & the future of AI. 2024\n\n[2] Goldblum et al. Position: The no free lunch theorem, Kolmogorov complexity, and the role of inductive biases in machine learning. 2024.\n\nRegarding the natural alignment between transformers and Post machines: the reviewer may see our response A4 to Reviewer aGq8 for an explanation on why simulating PMs leads to constant bit-size construction. An related open problem is whether the CoT length in our simulation be reduced from $O(t(n) s(n))$ to $O ⁣(t(n))$.\n\n\n\n**Q4:** For instance, what problems are solved in (say) an O(1) sized context window and how it compares to what problems transformers with CoT can solve in practice.\n\n**A4:** If the window length is $<n$, then the transformer cannot solve any problem that depends on the whole input, because the transformer cannot access the whole input. \n\nMore specifically, note that the entire input string is presented before the transformer starts generating CoT tokens, and at every step the transformer can look back only $s(n)$ positions.  If $s(n)<n$, the first $n−s(n)$ input symbols are permanently outside the transformer's attention and can never influence any CoT token.\n\n\n\n**Q5:** Is it possible to achieve the same effect of using the pos(i,j) positional encoding using some kind of an attention construction? While no longer constant bit-size, this would still be interesting in contrast with \"PENCIL: Long Thoughts with Short Memory\" by achieving space-efficiency without their reduction process.\n\n**A5:** Yes. Because of the fixed-offset attention property (if we drop the constant bit-size constraint), the relative PE can be replaced by a fixed absolute PE (as mentioned in response A2), or a causal positional masking, which directly restrict token $i$ to only attend to the only token $i−s(n)$.\n\n\n\nAdditionally, we will also revise other parts as suggested, including making the assumption of nonstandard relative PE more clear, fixing the typos, adding a note about hardmax, and adding a table comparing related results."}, {"review_id": "zhrPdM1Nug", "reviewer": "Reviewer_XoFA", "summary": "The paper is aimed at understanding the computational power of transformers with respect to the classical model of Turing Machines. Recent work has shown that transformers are Turing complete. This paper refines this body of work by showing that transformers of fixed size (in terms of size of embedding, number of layers, number of parameters) are sufficient. The equivalence proof does not require arbitrary precision arithmetic. It establishes precise relationship between the space bound of TM computation and the length of context window.", "questions": "The introduction highlights \"fixed numerical precision\" as a challenge w.r.t. earlier work. This is not discussed during the proof of the main result. It's likely obvious given the very discrete encoding, but could be explained (or more pertinently, why was this an issue in some of the earlier work, and what insight avoids it).", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe main result (Theorem 1) is precise and concise. The authors make a compelling case that this is a tight result, in particular, allowing the context window length to grow with the input size is unavoidable.\n\nThe proof structure is very clear and intuitive. It uses a classical result that shows that TMs can be simulated by queue machines. They explain how a transformer can then simulate a queue machine: the context window stores the queue, adding elements corresponds to emitting next token. The main technical challenge is using the attention mechanism to retrieve the current state at the oldest symbol and simulate a transition.\n\nWeakness:\nThe problem has been studied in a sequence of earlier papers. This is a nice and clean result, but doesn't seem surprising. Also not clear if this is relevant to practice. the claimed connection to understanding  \"reasoning ability\" of transformers is not justified.", "was_revised": true, "final_justification": "My original score was accept. The rebuttal and discussion was helpful to address any remaining questions. The final version is likely to be improved.", "rebuttal": "We sincerely thank the reviewer for the valuable feedback and questions. We will revised the related part according to the review.\n\n\n\n**Q1:** Also not clear if this is relevant to practice. The claimed connection to understanding \"reasoning ability\" of transformers is not justified.\n\n**A1:**  Our theorem establishes that: a single, fixed bit-size transformer can execute any algorithm whose working memory fits in the context window. It has several practical insights. \n\n- **Understanding the general reasoning capability.** Although our theorem is stated per task and may look like in the \"one-model-one-task\" paradigm at the first glance, it in fact leads to a universal-model perspective: a constant bit-size transformer can simulate a universal TM, i.e., a general-purpose programmable computer. Hence, a *single* specific model, once trained, can execute any program that is provided in the prompt or embedded into its parameters. This offers an interpretation on how current general-purpose LLMs handle diverse tasks. \n\n  As noted in Remark 1, the program need not to be task-specific; it could implement some meta-tasks, such as designing new algorithm.\n\n- **Engineering guidance.** Aiming for stronger deductive reasoning ability, a line of engineering efforts tend to lengthen context window instead of growing parameter count. Our result formally justifies this strategy: extending the window alone is sufficient. Moreover, a window that grows only polynomially with the input already suffices to solve every PSPACE problem, including game-tree search and mathematical proofs.\n\n- **Implications for the AGI debta.** There is a ongoing debta on whether transformers can approach AGI. A common negative view (e.g. [1,2]) argues that transformers, limited by finite size and window, cannot approximate unbounded computation.  Our result shows that, at least for deductive reasoning tasks (whose solutions depend only on explicit information), scaling window length alone is theoretically sufficient, and continually scaling up size is not a principled requirement.\n\n\n\n[1] Yann Lecun. Meta AI, open source, limits of LLMs, AGI & the future of AI. 2024\n\n[2] Goldblum et al. Position: The no free lunch theorem, Kolmogorov complexity, and the role of inductive biases in machine learning. 2024.\n\n\n\n**Q2:** The introduction highlights \"fixed numerical precision\" as a challenge w.r.t. earlier work. This is not discussed during the proof of the main result. It's likely obvious given the very discrete encoding, but could be explained (or more pertinently, why was this an issue in some of the earlier work, and what insight avoids it).\n\n**A2:** \n- **[Perez et al. 2021] and related follow-ups.**   The query may attend to many earlier tokens. When multiple positions tie for the maximal score, the hardmax outputs fractions such as $1/t$, which requires the precision to grow with $t$.\n\n- **[Li et al. 2024].** They encode the simulated circuit directly into the absolute PE (rather than into the parameters). As the circuit (hence the input length) expands, the PE must grow in dimension, so the embedding size is no longer constant. \n\n- **This work.** The Post machine’s automaton-like behavior is much simpler and more regular than the head-moving  behavior of TMs and the wiring of a circuit. This let our construction satisfy a nice property: at every CoT step the query attends to exactly one token, always the token $s(n)$ positions earlier. This fixed-offset attention can be realized solely by a relative positional encoding without any additional arithmetic operations. So the attention score is one-hot and entirely discrete; no averaging, division, or growing embedding is needed."}]

Author rebuttal:

Meta-review: **Summary of Claims and Findings**：
This paper presents a significant theoretical result on the computational power of Transformers. The authors prove that a Transformer with a constant bit-size—meaning a fixed number of parameters and fixed numerical precision—is Turing complete. The central finding establishes a precise equivalence: a constant bit-size Transformer with a context window of length $s(n)$ can recognize exactly the languages in the complexity class $SPACE[s(n)]$. The proof is achieved by simulating Post machines, a Turing-complete computational model whose queue-based operations align naturally with the autoregressive, windowed attention of Transformers.

**Strengths**:
* **Strong Theoretical Contribution:** This is the first work to establish Turing completeness for Transformers while maintaining a constant bit-size for all parameters and internal computation, improving upon prior results that required scaling precision or embedding dimensions with the input length. However, a similar idea is also explored in a preprint [Schuurmans et al.,24], though they do not focus on the constant precision. The authors should compare with [Schuurmans et al.,24] carefully in revision.
* **Precise Characterization:** The paper goes beyond a simple Turing-completeness claim by formally linking the Transformer's context window size ($s(n)$) to the space complexity ($SPACE[s(n)]$) of the problem, providing a tight characterization.
* **Clarity and Novel Proof Technique:** Reviewers consistently praised the paper for its clarity and the simple and clear proof structure. The use of Post machines provides a more intuitive and natural mapping to the Transformer architecture compared to direct Turing machine simulations.

**Weaknesses**:

The main issue of the paper, is that the cited theorem 2, which is the foundation of the entire paper, cannot be found in the provided reference. The closet result I am aware of in literature, are "Small Universal Circular Post Machines" by Manfred Kudlek and Yurii Rogozhin in 2001 and "Autoregressive Large Language Models are Computationally Universal" by Dale Schuurmans, Hanjun Dai, and Francesco Zanini in 2024. Still the results there are weaker than theorem 2 cited in this paper. For example, the Theorem 7 in Schuurmans et al. requires the transformer/post machine to read the leftmost **two** symbols and then decide what to write on the tape next. In contrast, Theorem 2 in this submission only requires reading the leftmost symbol only, which appears stronger to me. 

Below are some other weakness:
* **Idealized Model Assumptions:** The construction relies on a non-standard relative positional encoding and uses hardmax instead of softmax attention, creating a gap with architectures used in practice.
* **Hidden Requirement of High Precision**: The main reason that this construction of transformer with window attention does not need log precision is because the high-precision number S(n) is hard-coded into the inference system. As reviewer Y1kW pointed out, it is not clear how transformer can figure that our automatically using constant precision.
* **High Simulation Cost:** The number of chain-of-thought (CoT) steps required for the simulation of Turing machine running in $t(n)$ steps and $s(n)$ space, $O(t(n)s(n))$, is potentially prohibitive for practical applications. In contrast, previous work  [Yang et al., 25] provide same simulation using only $O(t(n))$ steps CoT with a different space-saving mechanism.

**Reason for Recommendation**:

The paper makes an interesting and well-presented contribution to the theoretical understanding of Transformers. The primary reason for acceptance is significance of proving Turing completeness under the realistic constraint of a constant bit-size and the novelty as well as simplicity of the proof. The precise equivalence established between window size and space complexity is a powerful result that advances the field, assuming the correctness of Theorem 2. While there are the weaknesses regarding idealized assumptions and the expressivity-learnability gap, they are common limitations for purely theoretical work in this domain and do not detract from the paper's core contribution.

After weighing the strengths and weaknesses, the final recommendation for this paper is Accept(poster), conditioned on that the authors will provide a proper reference for their Theorem 2, or alternatively, a rigorous proof for it. This is the conclusion that SAC and AC have reached after a long discussion. We do expect the authors to withdraw the paper if they cannot do so.

#References: 

- Kudlek, M. and Yu, R., 2001. Small universal circular Post machines. Comput. Sci. J. Mold, 9, p.25.

- Yang, C., Srebro, N., McAllester, D. and Li, Z., PENCIL: Long Thoughts with Short Memory. In Forty-second International Conference on Machine Learning.

- Schuurmans, D., Dai, H. and Zanini, F., 2024. Autoregressive large language models are computationally universal. arXiv preprint arXiv:2410.03170.
Decision: Accept (poster)