- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper shows that transformers without positional encoding using adaptive sliding window attention can simulate Post machines, hence are Turing-complete.
Critical strengths
This paper is well written for the most part and easy to follow. It has a clear contribution and its proofs seem valid.
Critical weaknesses
My main concern with this work is the fact that they consider transformers with adaptive window size, which do not correspond to the architectures used in practice. Related to this Table 1 suggests that the window size is an architectural parameter, which seems to be contradictory.
While the paper is generally well-written, I would encourage the authors to do a few modifications to make it even stronger. These do not modify my assessment of this work.
- Related to the point above, the terms "window" and "queue" seem to be interchanged in the beginning of Section 3, which makes it a bit confusing.
- I feel like the paragraph from lines 76 to 80 is confusing.
- It would be nice to compare the assumptions of Remark 4 to those of previous work.
- Some abbreviations and notations (such as TM for Turing Machine, or for the set of words) are not introduced.
- Mainly, Section 5 could be improved by adding a sketch of the proof or intuition. As a side note, it would be better to introduce the purpose of the "finite control-label set" before introducing it, and you forgot to mention the window in Theorem 8.
- It would be useful to have a table showing the exact changes between the architectural parameters of a Post machine and that of the HIST simulating it (eg , ), and the same thing for HIST$\rightarrow$transformer.
Questions for authors
Can you adapt your proof to fixed window size?
Additionally, what prevents you from reducing the CoT size and the precision? Why can't you adapt techniques from Li & Wang (2025/2026) for instance?
2 comments
I thank the authors for their answer. I would encourage them to discuss the window size question more clearly in their manuscript. As is, it might be confusing for readers not familiar with complexity theory, who are unaware that it is standard for the parameters to scale with the size of the problem.
This paper has a modest but clear contribution: positional encoding can be replaced by sliding window to prove the universality of transformers. It is also clear and well-written. I moved my score to 3 as a result.
We thank the reveiwer for the constructive feedback. Below we address the two main questions. As for other detailed suggestions for improving the writing and overall presentation, we will adopt them in late revisions.
Q1: Can you adapt your proof to fixed window size?
A1: Our completeness result also holds with a window whose length is fixed throughout the computation. To simulate a Turing machine using space S=O(s(n)), we can choose a window length before generation, initialize the window with the required padding, and keep the window length fixed throughout the entire computation. The transformer weights do not depend on n or S. Here “fixed” means fixed during a run; S may grow with input length, since an absolute constant window for all inputs would indeed yield only a finite-state system.
The adaptive window length is an optional strengthening, introduced to address the limitation of the fixed-window length already discussed in Remark 3 (also posed as an open problem in [Li and Wang, NeurIPS 2025]): a fixed-window simulation requires an a priori upper bound s(n), usually a worst-case bound over all inputs of length n. Adaptive growth removes this requirement and lets the window grow according to the space actually used by a particular computation.
Q2: Reducing CoT length and precision; comparison with Li & Wang.
A2: The O(s) CoT overhead arises in the Turing-machine-to-queue reduction: a leftward tape move can require rotating through the queue. Subsequent simulations add constant overhead; Theorem 8 uses at most four tokens per HIST transition. Improving that constant would leave the queue-simulation factor unchanged.
Uniform attention represents individual contributions at scale 1/m for context length m. The front-recovery signal and exact output gap have this scale. Appendix A.3 shows that O(logs)-bit arithmetic is sufficient.
Li & Wang (2025, 2026) use PE to select specific queue locations, whereas we do not use PE. We note that the PEs used in Li & Wang (2025, 2026) are carefully designed and depend on the input length n, which does not reflect the PEs used in practice.