An RNN with infinite-precision rational weights can implement a counter with a bounded number of neurons. With finite precision the number of neurons scales lin

An RNN with infinite-precision rational weights can implement a counter with a bounded number of neurons. With finite precision the number of neurons scales linearly in your desired depth of matching brackets: https://arxiv.org/pdf/2010.07515.pdf https://arxiv.org/pdf/2010.07515.pdf For a Transformer you need to add a new layer of self-attention to increase bracket matching depth by 1. https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306/43545/Theoretical-Limitations-of-Self-Attention-in https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306... Transformers are formally a lot weaker than RNNs/LSTMs.