The paper covers that. They only test to a finite size, but the models that fail can't generalize significantly beyond the size of explicit examples they were trained on.

Formally transformers should be capable of modeling it with the right weights, but they show good evidence those weights can't be learned with gradient descent. Whereas a neural turing machine or stack machine can learn them with gradient descent.