Sliding-window transformers without positional encodings are Turing complete because the sliding window breaks permutation symmetry and suffices to simulate Post machines via a constant-size histogram state.
The counting power of transformers.CoRR, abs/2505.11199
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.LG 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
New verification connection from C-RASP to Lustre model checkers plus local search algorithm for synthesizing C-RASP programs from examples.
citing papers explorer
-
Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
Sliding-window transformers without positional encodings are Turing complete because the sliding window breaks permutation symmetry and suffices to simulate Post machines via a constant-size histogram state.
-
Synthesis and Verification of Transformer Programs (Technical Report)
New verification connection from C-RASP to Lustre model checkers plus local search algorithm for synthesizing C-RASP programs from examples.