An autoregressive transformer is trivially a finite state machine with the state being the k input tokens. The state update just discards the leftmost token of

An autoregressive transformer is trivially a finite state machine with the state being the k input tokens. The state update just discards the leftmost token of the context and adds the predicted token to the right. It is somewhat tempting to look at the entire token sequence as a tape but that is misleading, once a token fell out of the context it is lost forever whereas a Turing machine always maintains access to the entire tape as it can just move as far left as it likes. As said, for this question it is really more useful to think of the state as a fixed size array or queue of tokens where in each step everything gets pushed one position to the left by the newly predicted token and the leftmost token gets discarded.