Constant Bit-size Transformers Are Turing Complete

We sincerely thank the reviewer for the valuable feedback and questions. We will revised the related part according to the review.

Q1: Also not clear if this is relevant to practice. The claimed connection to understanding "reasoning ability" of transformers is not justified.

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.

• 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.

  As noted in Remark 1, the program need not to be task-specific; it could implement some meta-tasks, such as designing new algorithm.

• 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.

• 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.

[1] Yann Lecun. Meta AI, open source, limits of LLMs, AGI & the future of AI. 2024

[2] Goldblum et al. Position: The no free lunch theorem, Kolmogorov complexity, and the role of inductive biases in machine learning. 2024.

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).

A2:

• [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$.

• [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.

• 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.

We greatly appreciate the reviewer’s constructive comments and suggestions. We will polish the manuscript according to the review.

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).

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.

In addition, proving that fixed precision suffices also provides a justification for the use of fixed-precision formats (and even aggressive quantization) in hardwares.

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.

A2: The key ingredient is not the particular nonstandard relative PE itself but the following property of our construction:

• 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.

If 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.

In addition, the reviewer may see our response A4 to Reviewer aGq8 for an explanation of the key technical differences from previous proofs.

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).

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.

A3: We will add the following discussions on limitations and future directions:

• CoT length: Our current simulation needs $O(t(n) s(n))$ CoT steps; reducing this to $O ⁣(t(n))$ remains an open problem.
• 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.
• 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.

We 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.

• 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.

  As noted in Remark 1, the program need not to be task-specific; it could implement some meta-tasks, such as designing new algorithm.

• 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.

• 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.

[1] Yann Lecun. Meta AI, open source, limits of LLMs, AGI & the future of AI. 2024

[2] Goldblum et al. Position: The no free lunch theorem, Kolmogorov complexity, and the role of inductive biases in machine learning. 2024.

Regarding 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))$.

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.

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.

More 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.

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.

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)$.

Additionally, 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.

We sincerely thank the reviewer for the valuable comments and feedback. We provide a detailed clarification to address the reviewer’s concerns.

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.

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.

All 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.

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?

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.

We greatly value the reviewer's suggestions and recommendations. We will revise the related parts accordingly.

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).

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.

As 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).

Q2: Can you say what happens in the case of a fixed "absolute" positional encoding?

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.

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

$\mathrm{poi}(i)= i \mod p$ where $p>s(n)$.

In 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.

Q3: Is it possible to replace your use of positional encoding with a casual positional masking?

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.

Q4: Can you explain key technical differences in the proofs in your paper compared to [Perez et al. 2021] and [Li et al. 2024]?

A4:

• [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$.

• [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.

• 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.

In addition, we will also revised the other part as suggested, including adding the missing references, simplifying excessively overcomplicated definitions, and fixing typos.

We appreciate the valuable comments and feedback. We provide a detailed clarification hoping to address the reviewer’s concerns.

Q1: About Expressivity vs. Learnability.

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.

Q2: About Computational Cost of Simulation.

A2: We acknowledge this limitation, and have already cited it as an open problem in the Conclusion.

Q3: About Idealized Model Assumptions.

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$.

Layer 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.

We will make both points clearly in the next version.

Q4: About Lack of Empirical Validation.

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.

Q5: The authors do not discuss limitations of this work.

A5: In the next version, we will add more discussions on limitations and future directions:

• CoT length: Our current simulation needs $O(t(n) s(n))$ CoT steps; reducing this to $O ⁣(t(n))$ remains an open problem.
• 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.
• 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.