Looped Transformers as Programmable Computers

Some ideas from this paper.

Binary positional encodings. Memory index $i$ is represented by a binary vector $p_i \in \{-1, 1\}^{\log(n)}$ . This has the property that $p_i^Tp_i = \log n$ for any $i$, and $p_i^Tp_j \le \log n - 1$ for any $i \ne j$.