Hard Attention Transformers and BSS-Machines

We define a new variant of transformers called recursive transformers, which generate sequences of vectors without discretisation in each step. We show that over ordered ring extensions of the integers recursive transformers with circuit activation functions and hard attention are computationally equivalent to the well-established algebraic model of BSS-machines. If the transformers use feedforward networks instead, they are equivalent to linear BSS-machines with degree-2 branching.