Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete

Qian Li, Xinyu Mao, Shang-Hua Teng

Positional encoding (PE) is widely viewed as necessary for transformers to process ordered sequences: without them, the next-token map appears permutation-invariant in its context…