Softmax Transformers are Turing-Complete
Authors: Hongjian Jiang
Michael Hahn
Georg Zetzsche
Anthony Widjaja Lin
Venue: ICLR 2026 Oral (2026)
Keywords: soft attention
FLaNN
recursively enumerable
Turing-complete
formal languages
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are Turing-complete. In this paper, we prove a stronger result that length-generalizable softmax CoT transformers are Turing-complete. 

More precisely, our Turing-completeness proof goes via the CoT extension of the Counting RASP (C-RASP), which correspond to softmax CoT transformers that admit length generalization. We prove Turing-completeness for CoT C-RASP with causal masking over a unary alphabet (more generally, for the letter-bounded languages). While we show that this is actually not Turing-complete for arbitrary languages, we prove that its extension with relative positional encoding is Turing-complete for arbitrary languages. We empirically validate our theoretical results by training transformers for various languages that require complex (non-linear) arithmetic reasoning.

Published as a conference paper at ICLR 2026
SOFTMAX TRANSFORMERS ARE BURING-COMPLEE
Hongjian Jiang
Michael Hahn
RPTU Kaiserslautem-LLnddat
Saarland University
hongjian. jiang@ eanggrpptu... de
mhahn& Ssst. moni-saarland.do
Georg Zetzsche
Anthony W. Lin
MPI-SWS Kaiserslautern, Germany georgêmpi-swss
RPTU Kaiserslautem-Lanm Landau and MPI-SWS Kaiserslautern, Germany
awl @nmmpi sws. .org
ABSTRACT
Hard attention Chain-of-Thouur (CoT) transformers are known to be Turing- complete. However, it is an open problem whether softmax attention Chain- of-Thought (CoT) transformers are Turing-complete. In this paper, we prove a stronger result that length-generalizzbbe softmax CoT transformers are Turing- complete. More precisely, our serringccomleteneess proof goes via the CoT exten- sion of the Counting RASP (C-RASP), which correspond to softmax CoT trans- formers that admit length generalization. We prove turing-completenes for CoT C-RASP with causal masking over unary alphabet (more generally, for letter- bounded languages). While we show this is not Turing-complete for arbitrary languages, prove that its extension with relative positional encoding is Turing- complete for arbitrary languages. We empirically validate our theory by training transformers for languages requiring complex (non-linear) arithmetic reasoning.
INTRODUCTION
Transformers Vaswani et al. 2017) have enabled powerful Large Language Models (LLMs) with Shain-of-Thougee (CoT) steps, which are capable complex reasoning (cf. (Wei et al. 2022 Ope- nAI et al.) 2024)). But what task can (and cannot) be done by CoT transformers? This fundamental question lie at the heart of the recent effort in understanding the ability of transformers through the lens of formal language theory (see the survey (Strobl et al. (2024)). In particular, the question whether CoT transformers is Vtrring-complete - that is, capable of solving any problems solvable by Turing machines is especially pertinent; see the work (cf. (Pérez et al. 2021: Bhhttamishra
et al. 2020 Merrill& & Sabharwal 2024 Qiu et al. 2025 Li Wang]
Are CoT transformers Turing-complete? All existing proofs of Turinggcompleteness of CoT transformers (cf. (Pérez et al., 2021 Bhattamishra et al., [020 Merrill & Sabharwal, 2024 Quu al., 2025 Li & (225][0255 employ hardmax attention, which a rather unrealistic assumption. In particular, its use comes at the cost of a lack of a trainability guarantee. It is still an open question to date whether CoT transformers that use softmax attention are curiing-complete, and whether one can guarantee some sort of trainability. A closer look at these proofs reveals direct simulation of Turing machines using CoT transformers, where the position of the head of the Turing machine should be "deduced" by means of attention from the CoT tokens. This was so far achieved using averaging hard attention, which uses (xx n> attention score (as in Pérez et al. (202T)) or layer norm (as in Merril & Sabharwal (2024)). It is unclear how to achieve this using softmax; more generally, it is still an open question if softmax transformers can capture languages of averaging hard-attention transformers (see Yang & Chiang (2024): Yang et al. (2024)).
Contributions.
The main contributions of this paper are (i) to prove for the first time that softmax CoT transformers are furing-complete, and (ii) to provide guarantee of length generalizability.
More precisely, we use the framework from Huang et al. (2025) of sangth--eneralizable softmax transformers. Roughly speaking, language 7. length generalizable if idealized learning pro-

---

Published as a conference paper at ICLR 2026
converges to L, if provided with all inputs of length < for some i. In particular, the authors showed that a simple declarative language called C-RASP (with causal masking) Yang & Chiang (024) can be converted into their framework, thereby also admitting length generalization. To date, this is still one of the most predictive notions of trainability for transformers that have solid theoretical foundations, as well extensive empirical evidence. Our results use the extensions of these models with CoT steps.
cedure (in the sense of Huang al. (2025)
As we noted, direct simulation of Turing machines using softmax transformers rather tricky, would be challenging to extract the position of the head of the Turing machine by means of softmax attention. The main innovation in our proof technique is to exploit the counting power of softmax transformers (through C-RASP) to simulate Minsky's 's counter machines, instead of Turing machines. This would entail Turing-com coonngteemleteesss of softmax transformers. The details of our results are below.
We first show that CoT C-RASPs with causal masking are Turing-comples over unary alphabet holds for letter-bounded languages,
E {a}. More generally, we show that Turing-completened i.e. L of... a, where di,...., ún are distinct letters in the alphabet. Such languages are espe- cially interesting because of their ability to model complex number-theoretic concepts (e.g.. prime numbers, exponentiation, multiplication, etc.).
Interestingly, we show that CoT C-RASPs with causal masking are not Turing-complete over arbi- trary languages. In fact, simple languages (e.g. palindromes) cannot be solved by CoT C-RASPs. To address this limitation, the next novelty in our proof is to extend CoT C-RASPs with Relative Po- sitional Encodings (RPEs) (cf. Shaw al. (2018): [ Liutkus al. (221) Dufter al. (2022)) which assigns a positional information to any token relative to another token. We extend the framework Huang al. (2025) by adding RPEs, and show that length- generalizability still holds. Next, we show that RPES are sufficient for CoT C-RASP to work with arbitrary input words: they allow us to compute an unambiguous encoding of the input word into a number that can be accessed by the simulated counter machine. This results in full corine-co in the presence of RPEs.
We provide an experimental validation of our results for CoT C-RASP and CoT C-RASPIRPES] by showing length generalization of transformers for complex number-theod theoretic concepts with wnary representation (to be captured by CoT C-RASP) and with binary representation (to be captured by CoT C-RASPIRPES)). For example, the concept of prime numbers will be represented as the language L = {aP: p is prime} with unary representation, and as (bin(p) p is prime} with binary representation (where bin(p) denotes the binary representation of p. e.g., 5 is written as 101).
Organization. We start with the CoT models in Section 2 We then prove furing-completenees aaiing-oopleeteess for the general case We report our experiments in Section Finally, we conclude in Section 6
results for the unary and detter-bounded cases in Section 3 is proven in Section
MODELS FOR TRAINABLE COT TRANSFORMERS
2.1 TRANSFORMERS AND C-RASP
Softmax Transformers. We assume transformer decoders with softmax attention and causal masking (Softmax Attention Transformers. SMAT). Our formal definition of softmax transformers follows that of Huang al. (2025). Attention weights are defined as
softmax(log n (V. KT Qv:1)-1)
where V; denotes activations at position and K. Q transform these to keys and queries, respec- tively. Here, scaling with log n is included, as it is needed to theoretically represent sparse functions across unboundedly input strings and circumvent theoretical limitations of soft attention (Chiang & Cholak 2022, Edelman et al. 2022). For the feedforward networks, we assume one-layer networks, where each hidden unit has either ReLU or Heaviside activation. Here, as in Huang et al. (2025). Heaviside is needed to theoretically represent functions with sharp thresholds; at any finite input length, it can be arbitrarily closely approximated using ReLU MLPs. As is standard, we encode an input E* by applying token embedding function em Σ R for some dimension k.
To define the computation CoT via SMAT, we need the transformer to be able to output a token. We further define output function o R Σ, parameterized by applying linear function
2

---

Published as a conference paper at ICLR 2026
R - R followed by argmax selecting the symbol receiving the highest score. Overall, view an SMAT as a length-preserse preserving map Σ* - Σx, where T(æ); indicates the symbol predicted after reading the prefix 2 .......
We refer to Appendix A for formal definition and further discussion of design choices. We further refer Appendix A.4 for brief primer the framework and results of Huang et al. 2025)
C-RASPs. C-RASP is equivalent the fragment K, # Yang & Chiang (2024) Yang et 2024)
of LTL[[Cunt] Barceló et al. 2024) with only past operator:
Φ Q. (a Σ) E + pellllllllltteeeee
c(cE N) # t+t
Let us define the semantics of C-RASP by structural induction on the C-RASP expressions. Suppose side remark, it possible also allow the empty string input, and for this we can use the "start-of-string" symbol +. We do not do this to avoid clutter. For syntactic category y,, we will define |[ as bitstring h ... hn (0, 1 On the other hand, for syntactic category i, we will define [[ as sequence my ... my E 2" of integers. For each sequence o, we will write o())
Wh W/ Σ+ [As
to denote the vth element in the sequence. We start with the base cases:
P Qa- In this case, h4 E {0, 1} is iff wA = a. In this case, m, = e for each
We now proceed to the inductive cases:
p 1/1 A 2/2. Then, h4 min 1 (22 (1))
yp vi w2. Then, h; max [1 (i), ( (.)
p . Then, h4
(t).
y 1 ~ 1. Then, h; = iff (1) ~ (i)
#l6]. Let my = 0. Then, for each i > 0, m, = m;-1 + 1 [Tl = 1; else
m, m--1-
Relative Positional Encodings. We also define an extension C-RASPIRPEs] (resp. SMAT[RPEs]) of C-RASP (resp. SMAT) with Relative Positional Encodings (RPEs), which are simply subsets 9i = N x N. We start with C-RASPIRPES). In the sequel, the notation [ refers to the function mapping each (i,j) E N x N 10 such that [[)]((.,)) = iff (i,j) E R.
For the syntactic category t, allow counting terms # [xpl which is to be interpreted at position as the cardinality of {i E [1.ji] : (i,j) E R, .p) Thus, we include depending on the positional encoding of each i relative to j. [Alternatively, Ri can be construed allowing positions certain distances from each j.] This generalizes the class C-RASP(periodic, local] defined by Huang et al. (2025), where is either periodic local.
As for SMAT[RPEs], the definition is simple modification of SMAT: the formula in becomes
softmax(log n {v"' "V''' + X[ (1))))))
Here, we interpret À bias term and [[]] as 1 if (i, [[] otherwise, is O.
Discussion of Relative Positional Encodings Relative positional encodings, which modify atten- tion scores with positional information, are popular approach for providing positional information to transformers. Our formalization of RPEs simple formal abstraction of additive relative po- sitional encodings, which add a position-dependdnt term to the attention logits (Shaw et al.) 2018 Dai et al., 2019; Xue et al., 2021 Press et al. 2022 He et al. 2021). Schemes in the literature differ in whether they are parameter-fie free (e.g., Press al. (2022) or involve learnable parameters. We consider the especially simple case where R is determined a-priori, parameter- free, and independent of the task at hand. We provide more discussion in Appendix A.3
3

---

Published as a conference paper at ICLR 2026
2.2 EXTENSIONS WITH CHAIN-OF-THOUGHT
Suppose I is the (finite) set of possible CoT tokens. CoT tokens in some F'F S I are reserved to indicate that the computation to terminate and that the input string is to be "accepted". Let T.F,. We define CoT to be map F Σ I I where I' is a finite set of CoT tokens, where all non-final symbols are in I' I- C r. Here, note that we include both finite (terminating) CoTs in I* and infinite (non-terminating) CoTs in Iw. Consideration of non-termen non-terminating CoTs is needed for Turing completeness. The language [(F) recognized by F is the set of all w E E* where F(w) is finite and ends in an element of Fr S r.
CoT C-RASPs. We extend C-RASP (resp. C-RASP/RPES)) with CoT' as follows. A CoT C- RASP expression (over I') is a non-empty sequence S = di....,d di of definitions d: of the form:
On, -Pa,
where 0; E .r and Pa, a normal C-RASP (resp. C-RASPIRPESS) expression. The intuition of S is switch condition, which will tell the program which token to output. S outputs a token string w E (EuS)= if [[ Th (Iwl) = 1 for some i. The output of S on a string w E (EuT-p)+ is the smallest index such that [lwwo))))))) = 1 and that IIyp, (Iwl)
input
defined to be 0g, where for each j < i. In this case, we write S(w) = a, Note that a CoT transformer might terminate without outputting a token if II ([wll immediately rejected. Here, we write S(w) 1 (i.e. undefined).
for each j; in this case, the input string w will be
A CoT C-RASP S generates the string U Um...Um E I* on the input w E Σ if S(wU, ... Uk-1) = UR for each & 1 I,..., m. Intuitively, this means that S autoregressively outputs the symbols in U. The language L(T) accepted by CoT C-RASP is defined be the set of all Σ* such that there exists finite string U E I ending in an element of I'r such that T generates on w, and nostlast symbols in are in T-F.
We remark that, in many cases, the order of the sequence S is not so important, especially if we can ensure that at most Oa, is going to be satisfied. We will use this in the sequel.
CoT SMATs. Recall that we view an SMAT T as a length-preserving map T Σ* - Σ*, where T(x); indicates the symbol predicted after reading the prefix I1 24. An SMAT T (E I))*
(T)* generates the string U = U1- ..- U,, E I* on the input w if autoregressively predicts the string U - that is, if T(WU1 ... U--1)
Us for each k: 1,..., m. The language L(T) accepted by a CoT SMAT T is defined to be the set of all w e Σ* such that there exists finite string U e r*
ending in F such that T generates U on w, and non-last symbols U are in I'-F
Proposition 2.1. If a language is accepted by a CoT C-RASP (resp. C-RASP(RPES]), then it is also accepted by CoT SMAT (resp. SMAT(RPEs]).
Proof Sketch for Proposition 2.1 see Section A.2 for full details. The starting point is Theorem 9 in Huang et al. (2025), which shows that C-RASP be simulated by limit transformers, which in turn are closely related to SMAT[RPES]. This earlier result concerned language acceptance by a single binary label computed at the final token; we extend it CoT generation, obtaining a SMAT that at each position outputs a one-hot vector indicating which COT token to output.
2.3 LEARNABILITY WITH COT
We now show that CoT C-RASP is learnable in the framework of Huang al. (2025). Intuitively, this framework considers transformers being trained on data from some bounded length and then deployed on data of larger lengths. We now make this formal. As before, we view SMATs as defining
maps T Σ" - Σ*. The hypothesis class θ is the set of SMATS where each parameter vector and matrix of T represented at p bits of precision, for some depending on T.
Definition 2.2. A language L is length- generalizably learnable with CoT if there is a CoT F with L(F) = L such that the following holds: For each i 1, 1,2, 3...., use the idealized learning procedure from Definition 6 in Huang al. (2025) to choose a sequence of SMAT's T, + (i
4

---

Published as a conference paper at ICLR 2026
1,2,3.... such that each T, generates F(w) i.. on all imputs |oa| & a Then, there is some No depending on L such that for all >> No. T, will exactly recognize the language L with CoT.
For the purpose of understanding the rest of the paper, the details of the idealized learning algo- rithm from Definition 6 of Huang et al. (2025) is not of utmost importance, though suffice it to say that it attempts to minimize a regularizer that results in favoring simpler and smaller transformers. Interested readers can find more detaits in Appendix AA.4
Next, we analogously define the same notions in the presence of RPEs. Given set Ri S N x N. define the hypothesis class @[ as the set of SMAT[RPES] T with the RPE R, where each parameter vector and matrix of T is represented at p bits of precision, for some p depending on T, and where each À in (2) is fixed to 1. We then define Angtth-generalizably learnable with CoT with RPE R by replacing O with Ogx in Definition 2.2
Here, the intuition is that we can learn single SMAT that works for all input lengths, even when training only on data from some bounded length, as long as the training length is sufficiently large. We note that the definition of the learning setup is substantially simpler than in Huang et al. (2025) since our transformers use no absolute positional encodings. Whereas Huang et al. (2025) used separate hypothesis classes O, at each context window size our learning setup requires a single hypothesis class that works for all input lengths. We then obtain the following guarantee:
Proposition 2.3. Consider language expressible in C-RASP[RPES] CoT, using RPE R. Then it is length--eneraliinn generalizably learnable with RPE R.
Proof Sketch for Proposition| 2.3 see Section A.2 for full proof. The proof is straightforward adaptation of results of Huang et al. (2025). Theorems 7 and 9 in that paper show length- generalizable learnability for languages expressible in C-RASP without CoT. Building on Propo-
sition 2. we extend this to CoT C-RASP.
3 UNARY CASE
In this section, we prove Turinn-completeness of of CoT SMAT for unary alphabet, i.e., Σ = {a}. More precisely, CoT SMAT recognizes all recursively enumerable languages over unary alphabet. In fact, we prove stronger turing-completene invariant languages. In turn, these results will be proven by establishing CoT C-RASPs for such languages and invoking Proposition 2.1 To help with readability, the reader may see Example where we construct a CoT C-RASP for the PARITY language, which incidentally known (cf. Huang et al. )2025)) not to be expressible by C-RASP without Co'T.
results for ceter-bbunned languages and permutation-
Theorem 3.1. Each recursively enumerable language over a unary alphabet Σ = {a} can be rec- ognized by SMAT in the CoT setting.
The theorem follows from the following proposition and Proposition 2.1 Proposition 3.2. Each recursively enumerable language over unary alphabet Σ {a} can be recognized by C-RASP in the CoT setting.
In turn, this follows directly from the following theorem; recall that a language L Σ is letter- bounded if it is subset of a"aş a..a,, for some distinct letters d1...., On E Σ.
Proposition 3.3. Each recursively enumerable letter-boundee language over any alphabet can be recognized by C-RASP in the CoT setting.
We will deduce Theorem 3.3 from the following theorem, which will be most convenient for our construction. Given an alphabet Σ with Σ {ai...... ".)) the corresponding Parikh map is the map V: E - Nº, where w E Σ* is mapped to (IW)a,
[w)a.). where |w la, is the number of occurrences of a, in w. In other words, (ww) is the vector that contains all letter counts in w. Notice that for u, v E Σ*, we have (u)
(u)) if and only e can be obtained from u by re-arranging if for any
the letters, by permuting u. We say that language L S Σ* is cermutaationinvariicnn u, E n with (2) = (v), we have u L if and only if E L. In other words, membership in L does not depend on the order in which letters appear in word.
Such a sequence always exists, there is just finite number of inputs at each length
5

---

Published as a conference paper at ICLR 2026
Proposition 3.4. Each recursively enumerable cotmanttationinnaariin language over any alphabet Σ can be recognized by C-RASP in the CoT setting.
We prove Theorem 3.4 by simulating counter machines. To define these, we define 4% to the set of expressions oo of the following form: conjunction of counter tests of the form Ij indicates the ith counter and ~ E {>, =.. A k-counter machine (k-CM) is a tuple (P, A, 90, F), where P is set of states, A E P x 22 x P Z is finite set of transitions, qo E P the initial state, and F' E P is the set of final states. We also assume that the machine is deterministic, i.e., for any transitions (p, y: 9, u) and (p.'', 2t') starting in the same state p. but with (g. u) * (g', u'), the expressions ip and şp cannot hold at the same time (i.e. vp A o' is unsatisfiable). For a transition (p, G, 9, u), will use the notation Src(T) = p. (gl(T)
0, where
q. ifr == yp and u, u.
A configuration of such a k-CM is tuple (g, a)) E P x Zt, where E P and x E Zt. For configurations (p.z) x)) (g. 3) E P Zt, we write (p. x) (q. y) if there is transition src(T) = p. tgt(T) = 4. (p)(()) is true, and y = x + u, By S, we denote the reflexive transitive closure of the relation
A with
the configurations. A configuration (q, is initial if q 40- We say that an initial configuration (qu. x) is accepted if (go. x) =, (p. y) for some y E Z and p E F. In other words, if there exists run of the k-CM that eventually arrives in final state.
We will employ the following variant of the fact that counter machines are Turing-complete. Note that if one uses CM language acceptors, with input-reading transitions, then just counters In our construction, it will be most convenient to provide the
sufficient for Vuring-completenen input of the CM at its counters. In this setting, it is known that three additional counters (aside from the input counters) are sufficient for
Lemma 3.5. For every recursively enumerable set S = N", there is a (n + 3)-CM so that for every E No, the configuration (go, x, 0, 0, 0) is accepted if and only if x: S.
This is a direct consequence of CM, lan- guage acceptors are able to recognize all re- cursively enumerable languages (this is implicit in (Minsky] [961] Theorem la), and explicit in (Fischer et al. 1968, Theorem 3.1)) and that k-CM accept the same languages as 3- CM (Greibach/ 1976, Theorem 2.4). Moreover, if S E Nº is recursively enumerable, then the (I)) S} is recursively enumerable language, and so there exists a three-counter machine M that recognizes L. This three-counter machine can easily be turned into (n + 3M-CM as we need it: whenever M reads letter d;, our CM will decrement the i-th counter; and when M uses counter (1,2,3), then our CM will use counter n + j.
To : > 0/ (-2,0)
TI 1 00((0)
start
90
Figure 1: 2-CM with transition labels
language
{af {aft...a0"
Corollary 3.6. For every recursively enumerable permutaation-ins invariant language (n + 3)M so that for every Σt, we have I. if and only if (4o, V(w),, O, O, 0) is accepted.
Σ*, there is
Proof. Follows from Theorem 3.5 For a recursively enumerable L S Σ+, the Parikh image (LL recursively enumerable; since
-iniataiiionnnnaaanntnn we have L iff v (ww) E (L).
Proof of Theorem 3.4
Let Σ {aI...... .n and take permutation invariant recursively enumer-
From Theorem 3.6 we get a (n + 3)-CM such that from the configuration Co = (4o, 31, F 0, O, 0). the CM will reach
able language L
and only if a ... a E T.
We define the set r of CoT tokens to be Σ unioned with the transition relation A. Note that the C-RASP going to be evaluated at the last position on input we where E T The construction of the C-RASP CoT transformer considers the following cases.
Initial step. At the beginning, the last symbol in the input to the C-RASP is in E. This indicates that the CM is in the initial state go- We add the following rules to our CoT C-RASP expression
O, - xp (Q..l...... # [QQa.. Qa:
for each a E Σ and each transition 7 = (go, 9, p, u) E A. The order in which the rules are added is not important since the counter machine is deterministic.

---

Published as a conference paper at ICLR 2026
Non-initial step. After initial step, the last symbol in the input is always transition of the CM. which indicates which state the CM is in. We add the following rules to our CoT C-RASP expression S (in no particular order):
Op (, 6443) Qr:
for any T, 7' A with tgt(T) src(7'). Here, ti........................ 4n are the count-valued C-RASP terms
= #1Q,11
Σ up(i)
[Qp]
for i 1....,7
(3)
PEA
4=
Σ AEA
up)()
# 1ppl
for i = n 1, 22 3.
(4)
Intuitively, each [[t will tell us the value of the ith counter. For i 1,...,n, we have the additional summand # [Qa.] because this is the initial value of the ith counter, according Theo- rem
Output symbols.
The desired output symbols for acceptance are any e A for which lg((T) E F.
Correctness.
The C-RASP directly simulates the CM, so correctness is immediate.
Finally, Theorem 3.3 follows easily from Theorem 3.4 We can modify our C-RASP to check (e.g. in each step) that the (initial) input word belongs to aj a.a See Section for the proof.
Example 1. In this example, (a+ [wla =2 OY,, which is a permutation invariant language. Note that this was proven not to be expressible in C-RASP without CoT Huang et al. (2025). We start with the the two 2-counter machine as depicted in Figure 7 To make the illustration simpler, we have opted to use only counters (which are sufficient for this language), instead of counters. The counter machine starts at (go, x, y), where x records the number of a's and y the number of b's. It reduces æ by 2 until becomes zero, which point accepts by moving to qı-
illustrate the construction of CoT C-RASP for parity (i.e. (w
We now specify the C-RASP rules for the counter machine. We use as an arbitrary letter in {a, b}. We start with initial step, corresponding to the first transition taken by the counter machine:
On # [Qal > 0 Qc
O, - - +1Q = A Q.
(5)
Note that, for our language, acceptance is only possible when the imput is nonempty, i.e. the last symbol at the initial step is some e {a,b) The C-RASP for the non-initial steps are as follows:
O 1 - #10,11 0 A
O #1aa1 - #10 QTo
(6)
GENERAL CASE
Given that Theorems 3.3 and 3.4 show that for letter-bounded or permutation-invarian languages,
COT C-RASP are Turing-complete, this raises the question of whether they even Turing-complete for general language L S * The following shows that they are not:
Proposition 4.1. C-RASP in the CoT setting is not Turing-complest complete over = {a, b).
This follows from the following lemma (e.g. take PALINDROME).
Lemma 4.2. If a language L is recognized by CoT C-RASP, then for each n the restriction L,, S all inputs of length & n. is recognized by an automaton size polynomial in n.
This is an immediate corollary of the logarithmic communication complexity of Limit Transformers and hence C-RASP (Theorem 12 in Huang et al. (2025)). which also holds even equipped with learned Absolute Positional Encodings (APEs). See Appendix for details. However, will show that with relative positional encodings, CoT C-RASP are in fact fully Turing-complete:
Theorem 4.3, Every recursively enumerable language over an arbitrary alphabet Σ can be recog- nized by C-RASP|RPEs| in the CoT setting and, thus, be recognized by Col SMAT[RPES].
7

---

Published as a conference paper at ICLR 2026
Membership in CoT SMAT[RPES] follows from Proposition 2.1
The CoT C-RASPIRPES] constructed in Theorem 4.3 is based on the following idea. Given an input E Σ* with say [ا] = n, our CoT C-RASPIRPEs first computes encoding of e I vector in N After this, it uses a construction similar to above to simulate a CM on this encoding.
To avoid confusion between multiplication of 0 and 1 on the one hand and concatenation of words, we will use different symbols for the numbers 0, 1 E N and the letters 0 and 1. Then for a = O, b 1, c O, and d 1, we can distinguish between ab 0 and ed 01. To convert between these objects, we use the notation 0 =- O, 0 0, T = 1, and 1 = 1.
Encoding words over two letters We first describe how to encode two-letter words. Formally, we have partial function 3: N - {0, 1) where + means that 3 is partial, i.e. not every number represents a word. However, if a number represents word, then it is unique. A number x E N will represent a word if and only if x # O. Hence, suppose # Then we can write z _i 6,2', where .m...... by {0, J. and bm 1. Let j = max(i b, 0} be the left-most position of zero when writing the most significant bit first. Then we set
3(x) == b b
by-
In other words, ((x) is the word consisting of all digits of x's binary representation, when reading from most significant bit first, and starting after the left-most zero. For example, we have
B(29 23 2 1010,
3(2%) 00000,
3(2 + 23 + 2n) 10.
Encoding words over arbitrary alphabets Now suppose E is an arbitrary alphabet with E {ai...., ). Then we encode words in E by vectors in N Similar to above, we define a partial function σ: N - Σ. Let us first describe the domain of a. We say that an n-tuple (wi..... W,) of words Wi,..., wn E {0, 13" is consistent if (i) the words Wi..... Wp have the same length, say m E N and (ii) for every position E [1, m). there is exactly one [1, n1] such that wy has the letter 1 at position i. Intuitively, the consistent n-tuples correspond exactly to the words in Σ*; A word Σ. of length m corresponds the n-tuple (Wi..... ,,,) where each wy has length n, and the 1's in are exactly at those positions that carry a, in w. This leads to an intermediate partial function μc: (fo, 13$)*
D where p(W1.... wn.) defined if and only if (wi...., wn) is consistent, and in that case, μu( u(W....., w,) E 2* is the word corresponding to Wi,..., Wn.
With this, we are ready to define a. The domain of a consists of those x (#1....,, ......,,22.. .n) e N where (i) all entries are non-zero and (ii) the tuple (3(21)...., ((x,)) is consistent. Moreover, for (Z....., x,)) E dom a. we set
<<>) == ((8()))..... B(x,))
For example, for n 2, we have
022 + 2", 2 2 2t) = (((2 + 2", 2, + +2 + +22)) = p(001, 110) = d2a2411
An important property of a is that if we change x = (x1, ,.)) by introducing further I's on the left of some binary representation of z;, then a (xx) remains the same. For example, we also have
(2 + 2 + 20: 2 22
24) ((3(2 2 20, 24 + 22 + 2*)) ((001, 110) a2a2011
although we modified the left-most entry by introducing the term 25. Thus, for every E > and every it E N, there is an x E N such that (i) all entries in x are 3 k and (ii) (xx) w.
key ingredient in our proof is the relative positional encoding (recall that we have shown that without RPF, Theorem does not hold). Perhaps surprisingly, the RPE we use in the proof does not depend on the language we are accepting: It is the same relation for every Turing machine we want to simulate. Its definition is based on the partial function (: N - {0, 1)* above. We define the relation N S N x as
The relative positional encoding
(i, E R
i j& i E [1, (8(()) and the word ((j) E 1)* has 1 at position
for every (1, E N. X N. For example, j = 26 + 25 + 23 + 2 + 20, then we have B(j) = 1011 and hence (1,5), (3. 5), (4, E Ri but (2.j) R..
8

---

Published as a conference paper at ICLR 2026
Overview Our C-RASP with CoT will work in two phases. During the first phase, it prolongs the input so that subsequently, a o-encoding of the original input word can be computed using Count- Valued Operations. For this, it relies the RPE R. In the second phase, our C-RASP simulates counter machine, similar to the permutation-invariant case.
Phase I: Constructing encoding of the input word In order to compute the a-encoding æ N" of the input word w Σ*, our CoT C-RASP proceeds as follows. It compute the entries =<1), ((n) of x in this order. Suppose (WI..... Why,)) is the consistent tuple representing w, i.e. u u(wi..... ,,,)
w. To compute (=1), our CoT C-RASP appends a dummy letter Di until the current word length satisfies 3(E) = w1. Note that this is possible since there are infinitely many l with ((E) w1- Once this holds, place special letter E1. Then, the CoT C-RASP appends
dummy letter Ce until the current word length satisfies (t) = W2, and then places E2, etc.
Initially, the last letter will be some a, E Σ. Then, our CoT C-RASP simply outputs D: We have
O Qa,
for each a, E Σ. When we have letter D at the end, our CoT C-RASP checks whether the current length E already satisfies B(() wy:
Oth - Qu k # = # [Qa1
# DE [T| = #1,,
(8)
O_,- On A (# [ #[Q..] v [T + #lQn.))
for each i = 1...., If we evaluate rule 8 on word of length É, we check that (i) the last letter is Di (ii) the number of positions j with (j. f) A that carry 0g equals the total number of positions that carry ag and (iii) the number of positions j with (j, R equals the number of positions that carry ag. Thus, conditions (ii) and (iii) say that the positions j with (j, E) Ri are precisely those that carry an ag In other words, (()) w. If these conditions are met, then the output letter is EB
Moreover, if we evaluate rule 9 we check that 3(E) does not equal we yet. In this case, the output letter is again D. and the whole check will be repeated with the next word length.
If the last letter is EL with i & n - 1, then we start computing x + 1): We output D++1 in 10
O - -Qn.
for each = 1..... n - 1
(10)
for each transition r with src(T) = 40 If the last letter is En, we initiate the CM run by outputting some initial transition T. This is rule 11
O - QI.
(11)
After the above process, we have placed II...., Thus, the current input word is then of the form
w'= w B / E .. EE where for the tuple x (......, .n,) with x; |W| [w|+/A +++f++ +i
we have (xx) = W. A count-valued operation can then access the encoding of w using the terms
X,
0]
for I,....
(12)
Thus, X; is the number of positions that have no occurrence of E.; to their left (and do not carry E themselves). Since there is exactly one occurrence of Ek this means X, is exactly the position of EE, minus one. Therefore, the term X, evaluates to ari), meaning we have a (X1,..., X,) w.
Phase H: Simulating the counter machine During the first phase, our CoT C-RASP appended letters to make an encoding x E N of the input word available through C-RASP terms Eq. (12). We now use a CM that starts with this encoding in its counters and then decides whether w E L. Such a counter machine exists because of Theorem 3.5 and the fact that S = {ær E No o(xx) L} is recursively enumerable (since a is computable). The simulation of the CM on œ works exactly like in Section 3 except that in the terms defined in equation 3 instead of using # [Q..] for = 1....,n,
we use the C-RASP term X; defined in equation 12] See Section forr details.
Example 2. Let us illustrate the case of the language L = {a. b) of words that end in b. We will need a CM that recognizes the set S {ar E N² a(x)) E L.} of encodings of words L. Observe that x N² satisfies oxx) E L if and only if xx)) is even: This is because for x E N where 3(x)) is non-empty, the string ((x) E {0, 1)* ends in 0 if and only if x is even. Therefore, our CM in Fig. I recognizes exactly S. Thus, our CoT C-RASP will have the following rules. For Phase I, it has the rules 7 to 12 where d1 = a and a2 = b. For Phase II, we want to simulate the CM from Example 7 and
introduce the same rules (5) and (6), except that in (6). Qu is replaced with X, everywhere. This way, we simulate the CM in Fig. 7 on some encoding x E N2 of the input w (i.e. (x)) w) and then check whether ax(1) 1) is even.
9

---

Published as a conference paper at ICLR 2026
5 EMPIRICAL EXPERIMENTS
We empirically validate our Turing-completeness results on several complex arithmetic concepts. See Table2in in Appendix for details. Our theory predicts that CoT C-RASP with NoPE suffices for unary representation (of numbers), while RPEs are needed for binary representation. Accordingly, we conduct three experiments: 1) Unary without positional encodings, 2) Binary with RPEs, and 3) Binary without RPEs. For each task, we construct two counter machines (CMs), one for the Unary representation and one for the Binary representation.
We employ a decoder-only LLaMA architecture Touvron et al. 2023 and train all weights from scratch without any pre-trained initialization. The model is trained on inputs of length [1-100] and evaluated three test sets: an in-distribution split with lengths [1-100] (testo), and two out-of- distribution splits with lengths [101-200] (testi) and [201-300] (test2). The SMATs are trained using AdamW (weight decay 0.01) with batch size of 64 and maximum 30k steps. To prevent overfitting, we use an EarlyStopping callback that monitors validation loss and stops training if the model's s accuracy reaches 100% on the in-distribution test set (lestn) for three consecutive epochs.
As shown in Table T SMAT achieves strong in-distribution performance on Unary representations, with accuracy exceeding 99.90%. It also generalizes well to longer sequences, maintaining high ac- curacy. In contrast, the Binary representation with RPEs exhibits hear-perfect generalization across all three test splits, consistently achieving 100% accuracy. However, removing RPES causes gener- alization to break down: only Prime reaches around 95% on testo. and all tasks exhibit almost no generalization. Together, these results show a clear contrast: Unary inputs generalize naturally with NoPE, whereas Binary inputs require RPEs to achieve any meaningful length generalization.
Unary
Binary (w/ RPE)
Binary (w/o RPE)
Language
testp
test
test2
testa
test;
test2
tests
test
tests
Prime
100
100
100
100
100
100
95.00
0.40
0.00
Exponential
99.95
99.96
99.96
100
100
100
82.80
0.06
0.00
Division
99.90
100
99.99
100
100
100
76.40
0.02
0.00
Greatest Common Divisor
99.99
100
99.70
100
100
100
70.20
0.03
0.00
Multiplication
99.99
100
99.98
100
1000
100
64.40
0.02
0.00
Table 1: Generalization accuracy on three test sets (testo, tests, test2) in unary/binary.
6 CONCLUDING REMARKS
Related work. Our work builds on Huang et al. (2025): They defined a learnable framework of softmax attention transformers (called Limit Transtormers), and a declarative framework (C-RASP) for them. In this paper, we further show that these classes of transformers are Turing-complete. Most of our main results use new techniques that have not been used in relation to transformers, e.g., simulation of counter machines. In relation to the learnability framework itself, Huang et al. (2025) dealt with transformers without CoT or Relative Positional Encodings, not sulficient for "uuiingcoomlltteess. We extended the proof techniques in [Huang et al. (2025) to these extensions. Recently, Yang et al.) (2026) showed that the learnability framework from Huang et al. (2025) is learnalle in the limit, but not in the non-asymptotic sense of et al. (2025).
Similar to our work, Hou et al. (2025) aims to provide length-generalizing constructions for Turing completeness. However, there are two key differences. First, we demonstrate the existence of soft- max transformer constructions, whereas et al. (2025) only demonstrated constructions in RASP (Weiss et al. 2021). Second, the approach of Hou et al. (2025) ensures length generalization only no n-grams are repeated, for some fixed n, which is likely to be unrealistic in the limit of long inputs. In contrast, approach theoretically ensures full length generalizability.
Future work. Recent results have refined Buring-completnnes for transformers (albeit with hard attention) by relating the number of CoT steps and complexity classes, e.g., see (Merrill & Sabhar- wal 2024) and (Li & Wang 2025). Refining our result with complexity is left for future work.
https://huggingfe wwt.a/c......aaaaaaaaee/mae 11ama 11ama
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank Pablo Barcelo, Michael Benedikt, David Chiang, Andy Yang, Will Merrill, and Jon Rawski for helpful discussions. This material is based in part upon work supported by the Eu- ropean Union (ERC. LASD, 101089343, and and ERC, FINABIS, 101077902, https: /tt.:///ooooog///////////// 3030000077700000000000
REFERENCES
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir V. Podolskii. Logical languages accepted by transforeer encoders with hard attention. In The Twelfth International Conference Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. URL htttps::/ppeneeeieeeeee htt.://aww..aaa...e.oooooooooana 7ma
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications sequence modeling. In CoNLL, pp. 455-475, Association for Computa- tional Linguistics, 2020.
Thomas Chen, Tengyu Ma, and Zhiyuan Li. Non-asympiotic length generalization. In Forty-second International Conference on Machine Learning, 2025.
David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), ACI. 2022, Dublin, Ireland, May 22-27, 2022, pp. 1654-7664. Association for Computational Linguistics, 2022. doi: 10. 10.18655/1/00222ACCC A2L. URL 2022 -occc-looon-o 527.
Zihang Dai. Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2978-2988, 2019.
Philipp Dufter, Martin Schmitt, and Hinrich Schütze. Position information in transformers: An
overview. Computational Linguistics, 48(3):333 09 2022. ISSN 0891-2017. doi: 10.1162/ coli a00045..
00445
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, pp. 5793-5831. PMLR, 2022.
Patrick C Fischer, Albert R Meyer, and Amold I. Rosenberg. Counter machines and counter lan- guages. Mathematical systems theory, 263):265-283, 1968. doi: 10.1007/BF01
Sheila A. Greibach. Remarks on the complexity of nondeterministic counter languages. Theor:
Comput, Sci., 1(4):269-288) 1976. doi: 141116//0004-377577799100007
Michael Hahn. Theoretical limitations of self-attention neural sequence models. Transactions of the Association for Computational Linguistics, 8:116-171, 2020.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert
with disentangled attention. In International Conference on Learning Representationss 2021.
Kaiying Hou, Eran Malach, Samy Jelassi, David Brandfonbrener,, and Sham M. Kakade. Universal length generalization with turing programs. In Forty- Internattioaal Conference on Machine Learning. 2025. URL https: httt::/:///petteeeeeeeeeeeea//am
VViews and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the Furopean Research Council Executive Agency, Neither the European Union nor the granting authority he held responsible for them.

---

Published as a conference paper at ICLR 2026
Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Raj Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. A formal framework for understanding length gen- eralization in transformers. In The Thirteenth International Conference Learning Repre- sentations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL https: //openreviess form/ d==44 9N5V51
Zachary Izzo, Eshaan Nichani, and Jason D Lee. Quantitative bounds for length generalization in transformers. arXiv preprint arXiv:2510.2700: 2025.
Qian Li and Yuyi Wang. Constant bit-size transformers are turing complete. CoRR, abs/2206,1122777 2025. doi: (0.48550/ARXIV2550..18 12027. URL https:///ci. 0ttp::////ol.or/1004888850 48550///44555//// 2506 12027
Antoine Liutkus, Ondrej Cifka, Shih-Lun Wu, Umut Simsekli, Yi-Hsuan Yang, and Gaël Richard. Relative positional encoding for transformers with linear complexity. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Re- search, pp. 7067-7079. PMLR, 2021. htw.:htppp/ee http::://pccceedinga. mlr press/v139/ liut kussla....... html
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Aus- tria, May 7-11, 2024. OpenReview.net, 2024. URL pestps::/oppenreev// weetiiewwweeeeeeeeeeeee net/ forum?
id-N JNG1Ph8hh
Marvin L Minsky, Recursive unsolvability of post's problem of" tag" and other topics in theory of turing machines. Annals of Mathematics, 74(3):437-455 1961. doi: 10.2307/1970290.
OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Moham- mad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Seemaddtt-Shapiro. Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brock- man, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Alty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gib- son, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hal- lacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billic Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Ka- mali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, tukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger. Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning. Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Rejichrr Nakano, Ra- jeev Nayak, Arvind Neelakantan, Richard Ngo. Hyeonwoo Noh, Long Ouyang, Cullen O' Keeff, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl,
12

---

Published as a conference paper at ICLR 2026
Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross. Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Sel- sam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Pre- ston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vi- jayvergiya, Chelsea Voss. Carroll Wainwright, Justin Jay Wang, Alvin Wang. Ben Wang. Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng. Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Work- man, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojeiech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2024. URL https: //tp:://axiv.../ http://.wwrg//////33....00
Jorge Pérez, Pablo Barceló, and Javier Marinkovic, Attention is turing-complete. J. Mach. Learn. jttp://r..rr/gpppp////////// 3000/2200000...00 302.htmll
Res., 22:75:1-75:35, 2021.
Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022.
Ruizhong Qiu, Zhe Xu, Wenxuan Bao, and Hanghang Tong. Ask, and it shall be given: On the turing completeness of prompting. In The Thirteenth International Conference on Learning Rep- net. waat:/foumm?1 httt///orrmmmtaaaaasspsssp/
resentations, 2025. URL URLhttpss: wwwprrevvvvee
Peter Shaw. Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position represen- tations. Marilyn Walker, Heng Ji, and Amanda Stent (eds.). Proceedings of the 2018 Con- ference of the North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies, Volume (Short Papers), pp. 464-468, New Orleans, Louisiana, URL
June 2018. Association for Computational Linguistics. doi: 10.18653/11/N18-205 https:/
wwggy.org/me. /org/N1 20747
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? A survey. Trans. Assoc. Comput. Linguistics, 12:543-566 2024. doi: a _006633
10.1162/TACL) A), 00663. URL (otthtts::// //ooi.
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: En- hanced transformer with rotary position embedding. Neurocomputing, 568: 127063, 2024.
Hugo Touvron, Thibaut Lavril Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Ar- mand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023. URL http:: http:::://axxx..rrege.oe www. 22t.//2022.0 13971
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998 6008, 2017. URL http:::/pppoccc..ggggggooo/ neur ips. Cc/ httpppppr21111 2017/hash/ html
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '2, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN
1088.
Gail Weiss, Yoay Goldberg, and Eran Yahav. Thinking like transformers. In International Confer- ence on Machine Learning, pp. 11080-1 1090. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2026
Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. mt5: A massively multilingual pre-trained text-to-text transformer. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 483-498, 2021.
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. CoRR, abs/2404.043333, 2024. doi: 10.4850ARXIV22444.0455 URL
https://doi. http:///oooorg///../// (18550/axXiv.. 04333
Andy Yang. Lena Strobl, David Chiang, and Dana Angluin. Simulating hard attention using soft
attention. CoRR, abs/2412.09925,, 2024. doi: 10.4850/ARXIV.241..009 URL https:
//doi.org/10. 48554855500 000o:/10..8555/aaxi111 2492.09925
Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, and Anthony Lin. Length general- ization bounds for transformers, 2026. Under submission (preprint: httpp:: /enodo .oo.//ooooroooooooooooooooo org/
recoorss/18800000
A ADDITIONAL MATERIAL ON SECTION
A.1 FORMAL DEFINITION OF SOFTMAX TRANSFORMERS.
Our definition of softmax transformers follows that of Huang et al. (2025 though we use highly simplified notation here for exposition. In SoftMax Averaging Transformers (SMAT), given sequence
VI.... Vn
a single layer outputs
WI, Wn.
where
v. O(v))
where C(-) is feedforward network, V Σ w(j),, and
softmax(logn n (v. K Qv:))
(13)
where V; denotes activations at position and K. Q transform these to keys and queries, respec- tively. Here. scaling with log n is included, as it is needed to theoretically represent sparse functions across unboundedly input strings and circumvent theoretical limitations of soft attention (Chiang & Cholak 2022, Edelman et al. 2022). Here, we show the case of a single head, extension to multiple heads straightforward
We assume C' is one-layer feedforward layer, where each hidden unit has either ReLU or Heaviside activation. Here, as Huang al. (2025), Heaviside needed to theoretically represent functions with sharp thresholds; at any finite input length, it can be arbitrarily closely approximated using ReLU MLPs.
Huang al. (2025) also assume that attention logits rounded fixed precision; do not require this for our results here. Also, whereas Huang et al. (2025) consider Absolute Positional Encodings (APE), which necessitated introducing fixed context windows and positional offsets, do not consider APE here, and so do not need to introduce offsets. Thus, SMATs considered in the present paper uniformly applicable arbitrarily long inputs.
To interface SMAT with an input string w E Σ+, we apply token embedding function em Σ. R& for some dimension k; these are followed by some number of SMAT layers. To define CoT SMAT, we need the transformer to be able to output a token. To this end, we define an output function o : Rd - Σ, parameterized by applying a linear function d E followed by an argmax selecting the symbol receiving the highest score.
Overall, we view an SMAT as length-preet preserving map T Σ* Σa, where T(x); indicates the symbol predicted after reading the prefix .1 ...
14

---

Published as a conference paper at ICLR 2026
Discussion Our formalization of SMAT follows the setting of Huang et al. (2025), which was designed to study the learnability of transformers. We note two aspects, which are needed to enable softmax transformers to represent functions across arbitrarily long inputs, and overcome well-known theoretical limitations of softmax attention (Hahn 2020 Chiang & Cholak 2022). First, scaling attention logits with log n is necessary represent sparse attention to specific positions, which otherwise would be impossible to achieve using softmax attention (Habm) 2020 Chiang & Cholak) 2022 Edelman al. (022). Importantly, this scaling does not involve any new learnable parameters. Second, using Heaviside activations is necessary to represent functions with sharp thresholds, as is needed to perform exact comparison of counts across unboundedly long lengths. At any finite input length, Heaviside can be arbitrarily closely approximated using ReLU MLPs. We view Heaviside (which is not differentiable) as a theoretical proxy for steep ReI.U network as standardly trainable.
A.2 PROOFS FOR CoT EXPRESSIVENESS AND LEARNABILITY
Proof of Proposition 2.7
This is a simple extension of Theorem 9 in Huang et al. (0025) as we now
explain.
We define CoT map Σ* - Σ* from an input string Σ. to the sequence W2...... ...... WN generated by a CoT C-RASP or CoT SMAT on the input string w. Starting from CoT generated by CoT C-RASP program, we aim to translate it to CoT generated by CoT SMAT.
We first explain the case without RPEs. We need to show that, if a CoT is generated in C-RASP COT, then there is an SMAT generating the same COT. In the case of language acceptance by single binary label computed at the final token, Theorem 9 in Huang et al. (2025) shows that C-RASP can be simulated by limit transformer without positional information. Our first observation is that, in the model of Huang et al. (2025), a limit transformer without positional information is equivalent to standard transformer without positional encodings and infinite context window, which in turn is equivalent to an SMAT as defined in our paper here. The proof of Theorem 9 in Huang et al.) (2025) builds transformer that computes the values of all boolean predicates computed in the C- RASP program at each position in the string, with one dimension in the model's s activations fo each boolean predicate. This means that the truth values of the expressions Sa, appearing in the switch condition S can also be computed. In order to evaluate the switch condition, we add another layer (whose attention heads have zero value matrices, i.e., don't contribute), then linearly project the relevant entries onto binary vector of length [1'). and apply piecewise linear function to convert this into a one-hot vector selecting the lowest-index token a, such that fo, is true. We now have a limit transformer which at each position outputs one-hot vector indicating which CoT token to output. This means, whenever a CoT is expressible in C-RASP CoT, it is also expressible by SMAT with COT.
We now consider the case with RPEs. We again build on Theorem 9 in Huang et al. (025). We first note that the definition of attention logits with RPE exactly matches the definition of attention logits in Limit Transformers with functions ó in Huang et al. (2025). where Φ(i,j) is simply || (i.)) Hence, for the purpose of expressivity, any SMAT[RPES] transformer is equivalent to limit trans- former. Then, when translating from C-RASP to SMAT, implementing an RPE into an attention head proceeds along exactly the same lines as the translation of the special case #[j & i (i. in the proof of that theorem.
Proof of 2.3 We first consider the case without RPEs. We build on Theorem 7 in Huang et al. 2025 and its variant for transformers without positional encodings, Corollary 18 in Huang et al. 2025 First, from Proposition 2.1 we know that if a language is expressible in C-RASP CoT, then is also expressible by SMAT with COT. The proof of that proposition further notes that our model of SMAT equivalent to a limit transformer without positional information. Then, by Corollary 18 in Huang al. (2025), any input-output map expressible by limit transformer without positional information is length- Songth-gnneralizbbly learnable. This proves the result for the case without RPEs.
We now consider the case with RPEs. The proof is similar to the previous case; however, need to (i) show that C-RASPIRPES] can be simulated by SMATs with RPE, (ii) length generalization for SMAT RPE transformers follows from expressibility by SMATs with RPE. First, regarding (i), we again build on Theorem 9 in Huang et al. (2025). extending our argument from the proof of Proposition 2.1 We first note that the definition of attention logits with RPE exactly matches the
15

---

Published as a conference paper at ICLR 2026
definition of attention logits in Limit Transformers with functions & in Huang et al. (2025) where ((i,j) j) is simply [ Hence, for the purpose of expressivity, any (MAT transformer is equivalent to limit transformer. Then, when translating from C-RASP SMAT, implementing an RPE into an attention head proceeds along exactly the same lines as the translation of the special case #[j i: (bi, P(j) in the proof of that theorem. Second, regarding (ii), use Corollary 18 in Huang et al. (2025) and note that the addition of fixed (not learned) RPE to attention heads in both the learned transformers and limit transformers has no impact on the argument.
A.3 MORE ON RELATIVE POSITIONAL ENCODINGS
Here, we discuss how our formalization of Relative Positional Encodings (RPEs) relates to prior work RPEs. Recall that define Relative Positional Encodings (RPEs) as subsets 9i N x N, defining attention weights as:
softmax(logn K Qv: + (()))))
(14)
RPE term
The key is the RPE term, which adds a position-dependent bias to the attention logits. Here, we interpret À as a bias term and [i as I if (i, E [[9]]] otherwise, is
Oue formalization abstracts additive relative positional encodings (additive RPEs), which add Desition-dependent term to the attention logits (Shaw et al. 2018 Dai et al. 2019 Xue et al. 202T] Press al. 2022, He al. 2021). Schemes in the literature differ in whether they parameter- free (c.g.. Press et al. (2022) or involve learnable parameters. We consider the especially simple case where R is determined a-priori, parameter-free, and independent of the task hand. Here, review relevant prior work on additive RPEs; we write qi := Qv; and ki = Kv, for brevity.
1. (Shaw et al. 2018): Here, the RPE term is of az-j. where ai-z is learned embedding depending on the relative distance - (their Eq. 5).
2. (Dai et al. embedding depending on the relative distance j. and u, are learned global vectors.
2019) Here, the RPE term of ri-; u kis + u² ri-j. where r;=j is learned
202T): Here, the RPE term b;-j. where bi-; is learned scalar bias depending 3. (uue et al. the relative distance i j.
4. (Press et al.
2022): Here, the RPE term is ([-)) where is learned scalar slope.
5. (He et al. 2021 j: Here, the RPE term is of ri-s u ky + oJ r:-ji where r:-j is learned embedding depending the relative distance i j, and u, are learned global vectors. This very similar to Dai et al. (2019).
Another popular class of RPEs are multiplicatiie RPEs, which transform the key and query vectors with position-dependen matrices (Su et al., 2024). Our RPEs are closest to those of (Xue et al.) 202T and (Press al., 2022), as they involve adding scalar bias to the attention logits. Whereas [xue et al. 2021) learn separate bias for each possible relative distance, we only require single R determined a-priori, with no learnable parameters beyond the scalar X. In our theoretical analysis, this parameter-fiee nature is useful for length generalization, ensuring that the number of learned parameters need not increase with the input length.
A.4 PRIMER ON HUANG ET AL. (025))
As our results build on Huang et al. (025), provide brief primer their key definitions and results here. We define both syntax and semantics of C-RASP in the main paper. Here, we provide simple example, illustrating the formal language I. >* taken from Huang al. (2025):
16

---

Published as a conference paper at ICLR 2026
- RASP program for = abb over = {a, b) (from Huang et al. (2025))
C.- (1) #
Q.(i)
# of immediately preceding Position holds an a
P.- : (1-(1)=
(2)
Qua(t) = Qo(i) A (a-(1)
substring ab ends at position (3)
Cat(1) = #[j < |] Qas(i)
# of substrings ab
(4)
L(t) (i) 3
At least one ab precedes position i (5)
We now introduce the key definitions and results from Huang et (2025) that we build on. As we focus on No Positional Encodings (NoPE) and Relative Positional Encodings (RPE) transformers, we only define the relevant hypothesis classes here; this makes the analysis easier than Huang et al. (2025), who also consider APE transformers, which caused substantial amount of further complexity. In particular, the assumption of "translation invariance" used by Huang et al. (2025) is not needed here.
The idealized learning procedure Huang al. (2025) centered around minimizing a regularizer R mapping transformers T to numbers, favoring simpler and smaller transformers. It is defined in terms of (i) the number heads, (ii) the precision used the transformer's attention computations, (iii) the ranks and norms of the various parameter matrices and vectors. The learning model ap- plies to the class F of ennth-preserving functions f mapping strings to sequences of vectors. The idealized learning procedure ("Inference Procedure") is then defined follows:
Definition A.1 (Inference Procedure, from Huang et al. (2025). Given function f E F, the Inference Procedure obtains a sequence of transformers Tı, T2.... as follows. Define U, as the set of transformers matching the behavior of f on all inputs of length & 2. Then choose Tn E Un such that
1 R(T,) <
inf R(T) TEU.
(6)
Here, the term is used because the class Un is infinite and the infimum may not be attained; approximate minimization of the regularizer is sufficient. Depending on whether consider NoPE or RPE transformers, the transformers T2 are taken from the corresponding hypothesis class with NoPE RPE.
Huang et al. (2025) then show that length generalization in this learning model is equivalent to expressibility by class of idealized transformers called Limit Transformers. As focus on the NoPE and RPE cases, the result simplifies to the following statement:
Theorem A.2 (Guaranteed Length Generalization in the Limit, simplified from Huang 2025
Let f E F. Then the following are equivalent:
f is expressible by single transformer that computes across all input lengths (NoPE or RPE).
2. (Guaranteed Length Generalization) Applying the Inference Procedure from Definition A. (either in the NoPE or RPE setup, matching the encoding in (1)) to f generates a sequence T1, T2.... with suPn=112.3.. R(Tx) CC, for which there is some No such that, for all m > No. Tm matches f on all inputs of any length & m.
These definitions and results concern idealized learning procedure that assumes that all data up to input length is fitted perfectly for training: recent follow-up work has expanded by providing more quantitative analyses when only finite data available (Chen et al. 2025) Izzo et al. 2025). Huang et al. (2025) further provide translation from C-RASP to transformers, which we build on our results.
B ADDITIONAL MATERIAL ON SECTION 3
In this subsection, prove Theorem 3.3 from Theorem 3.4
Suppose
Σ (a....., aa). L C at a is recursively enumerable, then so is the language K (u E Σ 7e L: (()) (v)) of all permutations of L.. Moreover, K is permutation-invant
17

---

Published as a conference paper at ICLR 2026
and thus recognized by CoT C-RASP according to Theorem 3.4 Since L Knaf a to turn that CoT C-RASP into a CoT C-RASP for L, it remains to check that the input word belongs to the set ot a Therefore, for all rules O₂ P, where P is a C-RASP expression,
O, - PA
#1Qa, A #1Qa,1 0] 0,
1siejen
where the second conjunct says that there are no positions carrying an o, that have at least one dj with to their left. Then, the modified C-RASP clearly recognizes K o af a L.
C ADDITIONAL MATERIAL ON SECTION
Details of Phase II In this section, we present the details of Phase II of the construction in Sec- tion For this, first observe that
S= (x N" (xx L}
is recursively enumerable (since is computable). is recursively enumerable, since the partial func- tion is computable. Therefore, by Theorem 3.5 there is (n + 3)-counter machine (P, A, go, F) such that for any N", we have a e S if and only if from the configuration (go. 0, 0, 0), the counter machine eventually reaches a control state in F.
We simulate a step of the counter machine using the following rule. If the CoT C-RASP finds the letter 7 as the last letter, then for each possible next transition r', it checks whether its guard fo satisfied, and if so, executes r' by outputting r'. Thus, we have
O, - (tr. (443) ^ Qr
for any two transitions T E A for which tgt(r) sre(T'). Here, ti...., tx43 the following terms:
t; X
Σ (p(
# [12
for i I,..., n, and
PEA
4
u (1)
[0p]
for i n1 1, 2,
AE
where X, is the count-valued C-RASP term from 12 For {n + 1, n. + 2, + 3), 1 is just the sum of counter effects counter i. Equivalently, 4 IS the current value of counter i after executing all these transitions. For E [1, n]. t, we also add X,, which has the effect that the counters I,..., are initialized with X₃,
Finally, our CoT C-RASP accepts if the output symbol is any 5 e with eg
Other Proofs
Proof of Lemma 4.2 If L is recognized by CoT C-RASP, then it is also recognized by an SMAT
C-RASP by Lemma 2. In fact, our model of SMAT is equivalent to the NoPE special case of the Limit Transformers of Huang et al. (2025). Now Theorem 12 in Huang et al. (2025) shows the following: Take any k. For each string the language is recognized via an SMAT. Assume Alice has access to the prefix of w F (w) of length k. and Bob has access the remainder, then Alice needs to communicate just Olog k) bits allow Bob to compute the output of the SMAT at all positions k + 1, + 2, In fact, Theorem 12 in Huang et al. (2225) is stated for the special case where half the input length, but the argument is entirely general, as it only relies on the length of Alice's part.
F let F(w) r u T be the associated CoT by which
Note that, if the CoT terminates before |u] steps, Alice can just communicate that. Now given the SMAT recognizes I. via CoT, Bob can determind from Alice's communication if given string the language or not.
Now we construct family of NFAs accepting the language follows.
"This is not decidable, but Bob in this model is computationally unconstrained agent, with communication hetween Alice and Bob the only bottleneck.
18

---

Published as a conference paper at ICLR 2026
For y, E Σ", define AAB if and only if, for all e E", Alice communicates the same to Bob on x2 and yz. By definition, each equivalence class of this relation is a subclass of a Nerode equivalence class of L (t).
Given any length bound n E N, let Qn be the set of all = AB Alccsssssss represented by at least some words of length & n. By the result described above, 1Qx is bounded by & مm 20 O(poly(n)). Now, by definition of the congruence, Qn is the state set of automaton computing FAB =AB-equivalence classes. By (f), recognizes L.
We remark that this proof also applics if we augment transformers with learned Absolute Positional Encodings (APE), because Theorem 12 in Huang et al. (2025) also applies to the APE- augmented case when the APE embeddings learned.
L
D ADDITIONAL MATERIAL ON SECTION 5
D.1 DATASET CONSTRUCTION
For each task shown Table 2, we generate paired datasets of input strings and k-CM output traces under two encoding regimes: Unary and Binary encoding.
Language
Unary Representation
Binary Representation
Prime
{ {ap e }
(bin(p) p P)
Exponential
fa? :i 0}
(bin(i)#bin())) :j 2'
Division
(a'b :ili}
(bin(i)#bin(j) :
Greatest Common Divisor
fatlet k ge)(),)) { {a'bich : i-i
(bin())bin())biin)) = god(()) (bin(1) (an()))bin()) #bin(k) -k-ixj
Multiplication
Table 2: Unary and Binary representation of arithmetic languages. Here P is the set of prime num- bers, j denotes divisibility, ged(i, is the greatest common divisor, and x multiplication.
Unary Encoding. In the unary setting, we work over small alphabets such as {a} for Prime, {a, b} for Exponential, and Division and {a, b, e) for Greatest Common Divisor and Multiplication. Here, input strings are sampled uniformly at random from these alphabets within given length ranges, without enforcing that they encode tuples of integers satisfying the intended arithmetic relation (e.g. words are not constrained to be of the form a (²c)).
Given a deterministic k-counter machine (or k-CM)
M (P,A, F0.
and a unary word w Σ², we view w simply as an impur to M. Since M is deterministic, the run of M on w is uniquely defined. Writing Wily w un| the induced computation is the sequence
(go, Co)
(g) c1)
(qp | G(w));
where (ge, ex) denotes the configuration after reading the t-th symbol of
For a transition т (p. 4 u) e A, we use the standard notation src(T) = p. tgt(r) == g. fpr s, and u, The target sequence associated with is then defined
target(w) == (TT)
where Ti the unique transition of M taken step f of the above run. Because M is deterministic, the sequence (wr) is well-defined and uniquely determined by w.
Binary Encoding. In the binary setting, integers are represented canonical binary form (with no leading zeros), alphabets Σ {00. 1), 10,1,/)} For the tasks Greatest Common Divisor and Multiplication, we construct inputs of the form bin(x) bin(y) / bin(z), while Exponential and Division binary pairs bin(w) bin(v), and Prime uses single binary encoding bin(n).
19

---

Published as a conference paper at ICLR 2026
Each binary sample is labelled positive when the intended arithmetic relation holds (e.g., y, 2 = y, 2 = ged(2, y). w c, & x², or n is prime). Negative samples are generated by replacing the inpur component with nearby but incorrect integer that satisfies the required bit- length constraints.
As in the unary setting, the imput string is fed directly to the model, and the superviston signal is given by the K-CM trace obtained by running the corresponding deterministic k-CM on this binary input; thus the target sequence uniquely defined.
D.2 DETAILS OF EXPERIMENTAL SETUP
Prompt and Predicted Output. For every input string we prepare the model input in prefix-LM format. The model receives the prompt SOS INPUT SEP where INPUT de- notes either the unary or binary representation of the original string After the separator to- ken, the model is required to autoregressively generate the target region TARGET EOS where TARGET encodes 7(w), the unique accumulator trace produced by the deterministic k-CM when executed
Thus the complete input-target sequence used during training has the form SOS INPUT SEP TARGET EOS
During training, we apply the standard autoregressive language modeling objective, but we restrict the cross-entropy loss to the TARGET region STARGET--EOSS ensuring that the model learns to generate the target trace 7(w) conditioned the INPUT prefix. At evaluation time, report exact match (EM) over the entire predicted output region: an example receives score if the model's generated sequence matches 7 7(w) exactly, and 0 otherwise.
Architecture and hyperparamters All models in this work are trained from scratch, without any pretrained weights. We use a decoder-Only Transformer architecture LLaMA, but with the standard SwiGLU activation replaced by ReLU nonlincarity in all foed-forward blocks. Beyond the acti- vation change, we also modify the positional encoding mechanism: the Unary representation uses NoPE, whereas the Binary representation uses relative positional encodings. Apart from these substitutions, the model follows the standard LLaMA design, including multi-head self-attention, layer normalization, and residual connections. Our empirical results show that the architecture per- forms robustly under both the Unary and Binary encodings considered in this work.
The hyperparameters used for each task listed in Table 3 including the number of layers, atten- tion heads, embedding dimension, learning rate, and maximum training steps.
20

---

Published as a conference paper at ICLR 2026
Language
Representation
Model Size
LR
Max Steps
Unary
layer;
head; 32 dim
le-3
30k
Prime
Binary 94
layer;
head; 64 dim
le-3
30k
Binary V
6 layer; 4
head; 256 dim
le-3
30k
Unary
layer;
head; 32 dim
le-3
30k
Exponential
Binary
layer;
head; 64 dim
le-3
30k
Binary
layer; 4 head: 256 dim
le-3
30k
Unary
4 layer; 2 head; 128 dim
le-3
30k
Division
Binary
layer; head; 64 dim
le-3
30k
Binary-V V
layer; 4 head; 256 dim
le-3
30k
Unary
layer; head; 128 dim
le-3
30k
Greatest Common Divisor
Binary
layer; head; 64 dim
1e-3
30k
Binary V
6 layer; 4 head; 256 dim
le-3
30k
Unary
layer; head; 64 dim
le-3
30k
Multiplication
Binary
layer;
head; 64 dim
le-3
30k
Binary
6 layer; 4 head; 256 dim
le-3
30k
Table Hyperparameters used for training LLaMA-style decoder-only Transformers on each task, across the Unary (NoPE) and Binary (Binary with RPEs, Binary without RPEs) representations. All models use ReLU activations and are trained from scratch with AdamW. Weight decay 0.01 for Prime, Exponential, and GCD; 0.05 for Division; and 0.03 for Multiplication.
21


Reviews:
[{"review_id": "ZJ2p9nTWEZ", "reviewer": "Reviewer_PWUm", "summary": "Previous work had shown that hardmax attention transformers are Turing-complete. (Hardmax attention usually means that activations are 1 for some token and 0 elsewhere.) This paper proves the results under the more realistic case when the softmax operation is used in the network architecture, rather than the hardmax. The result goes through different techniques than the prior literature on Turing-completeness of transformers.\n\nThe proof of Turing-completeness, at a high level, involves two steps:\n\n- Show that a language CoT C-RASP can be implemented by a softmax transformer (this mainly seems to have been done in prior work by Huang et al).\n- Show that CoT C-RASP is Turing-complete, under various conditions (if the language is letter-bounded or there are relative positional encodings).", "questions": "N/A", "limitations": "", "rating": 10, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- This paper takes a step towards proving the Turing-completeness of transformers under more realistic architecture definitions. Softmax (rather than hardmax) is differentiable, so this proof is the first one for a transformer architecture definition that is trainable via gradient methods.\n- The proof of Turing completeness goes through different techniques than previous proofs for hardmax attention. I am not familiar enough with these techniques to know if they are standard in formal language theory, but in any case bringing them to the attention of the community focused on computability in LLMs may be useful.", "weaknesses": "- Through Section 2, many proofs of the results, definitions etc. seem to taken nearly directly from Huang et al (2025). This makes it hard  to read without first reading Huang et al. There is significant setup assumed from Huang et al, some of which is never described in the paper itself. Generally, it seems worth defining notation before it is used, even if the notation is standard in formal language theory. Notation was not defined for the definition of C-RASP, CoT C-RASP and in many other places.  If this takes too much space, it would be nice to include an appendix with relevant background so that the paper is more self-contained.\n- The paper should do more to highlight to conceptual or technical challenges of moving from hardmax to softmax. What about this alternate proof strategy allowed for circumventing the need/convenience of assuming hard attention?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CYdmdFIJCn", "reviewer": "Reviewer_rteb", "summary": "This paper studies whether softmax-attention Chain-of-Thought (CoT) transformers are Turing-complete and answers this question positively. To prove this, they build upon previous work on Chain-of-Thought extensions of a declarative language called C-RASP. They first show that CoT C-RASPs with causal masking are not Turing complete over arbitrary languages, and therefore extend them to CoT C-RASPs with Relative Positional Encodings. Lastly, they support their theoretical results by training Softmax Attention Transformers on various arithmetic tasks and find that they learn these tasks very well.", "questions": "1. What do you mean by 'to provide _a kind of_ guarantee of trainability' (in the contributions)? Could you explain the usage of 'kind of' better here.\n2. Could you discuss the usage of RPEs for providing positional information in Transformers in more detail? How often are these used and what have been previous empirical findings on them?\n3. Many of your definitions and proofs seem to build upon results from Huang et al. (2025). Could you discuss the relation to this paper in more detail.\n4. Could you describe the tasks, training architecture, and loss function used in the 'Empirical Experiments' in slightly more detail again?\n5. Where can I see the results that you are referring to in this sentence:\n> These results demonstrate that unary benefits from NoPE, whereas binary requires R for length generalization.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper is able to answer the relevant question whether softmax-attention Chain-of-Thought (CoT) transformers are Turing-complete positively, thereby extending previous work that only showed Turing-completeness using hardmax-attention. Furthermore, it is insightful to see that CoT C-RASPs with causal masking are not generally Turing complete, but that they do become Turing complete when adding Relative Positional Encodings.", "weaknesses": "I think the paper could profit from additional clarity in the writing and in the explanations. I was for example slightly confused by phrases like 'to provide _a kind of_ guarantee of trainability' (in the contributions). Furthermore, I found the section on the 'Empirical Experiments' not very clearly written and would have been interested in seeing slightly more details and explanations on the tasks, the architectures used and the training. The corresponding Appendix D was very short and did not help me much. Lastly, the related work section was very short and I would have in particular been interested to see more discussion on the relation between these results and previous results using hardmax-attention and the relation between this paper and the results from Huang et al. (2025), which is cited very often throughout the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JpevSkK6ri", "reviewer": "Reviewer_b98p", "summary": "This paper proves the completeness of softmax Transformers for CoT C-RASP over a unary alphabet. The result also implies that softmax Transformers exhibit length generalization for this language. The authors further state that softmax Transformers are not Turing-complete for arbitrary languages but show that softmax Transformers with relative positional encoding are Turing-complete for arbitrary languages.", "questions": "See Weaknesses.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper consider an important theoretical question, i.e., whether Turing-completeness holds for more realistic models such as softmax Transformers.", "weaknesses": "1. The expression \"Turing-completeness for some languages\" is conceptually unclear. Turing-completeness has a strict formal definition. The results presented in the paper do not appear to fully establish the claim.\n\n2. Softmax Transformers should, in principle, approximate hard-attention arbitrarily well. Since hard-attention Transformers are known to be Turing-complete, the paper’s results suggesting a gap between softmax Transformers and Turing-completeness raise questions. The paper seems to provide no clear explanation for this discrepancy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o6oYHpnvjP", "reviewer": "Reviewer_DApH", "summary": "The paper proves, for the first time, that soft attention transformers with chain-of-thought (CoT) are Turing-complete. This is more realistic than past results, which assumed hard attention. The authors use C-RASP to demonstrate that soft attention transformers with CoT can simulate Minsky counter machines, which are known to be equivalent to Turing machines. They show that such transformers are Turing-complete for unary and letter-bounded languages, and that adding relative positional encodings (RPEs) extends this result to arbitrary languages. Empirical results on arithmetic reasoning tasks confirm the theoretical claims: transformers with RPEs achieve near-perfect accuracy and have good length generalization.", "questions": "1. How would the results of Merrill and Sabharwal (2024) translate to this setup?\n\n2. Do you think it would be possible to generalize the result to other types of positional encodings?\n\n3. Can you comment on the val_2 accuracy only approaching, but not reaching 100%? What does this imply? Could you say that the models learn a very good approximation but maybe not actually learn the underlying mechanism? Did you perform any ablation studies to see if you can improve the reported results? I think some discussion about this should be included in the paper.\n\n\nWilliam Merrill and Ashish Sabharwal. 2024. The Expressive Power of Transformers with Chain of Thought.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper resolves a major open question in the theoretical literature of transformer expressivity. This result brings us closer to understanding what CoT transformers can perform in practice.\n\n2. The proofs and constructions are rigorous and technically sound. Moreover, the main result is proven using a new proof technique---using counter machines---which strengthens the theoretical contribution.\n\n3. The paper includes experiments on arithmetic reasoning tasks, with results that align closely with the theory: unary tasks succeed without RPEs, while binary tasks require RPEs to generalize.", "weaknesses": "1. Contribution (ii) from the introduction claims to provide a guarantee on trainability; however, this seems somewhat misleading, as the paper does not present a formal analysis of learnability.\n\n2. In the current form, the paper is quite technical and, in places, hard to follow unless the reader is very familiar with related work. I believe the paper would benefit from some more high-level intuitive explanations. Additionally, a summary figure outlining the main results and their corresponding sections would improve clarity.\n\n3. I think the experimental setup would benefit from some more detail and polishing. For instance, there is no mention of the test sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)