# On the Computational Power of RNNs

arXiv: https://arxiv.org/abs/1906.06349 · HTML: https://mlsanity.com/paper/1906.06349/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2019.

## Built on by (most cited first, 30 of 35)

- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Theoretical Foundations of Deep Selective State-Space Models](https://mlsanity.com/paper/2402.19047/) (2024)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [Autoregressive Large Language Models are Computationally Universal](https://mlsanity.com/paper/2410.03170/) (2024)
- [Rethinking Transformers in Solving POMDPs](https://mlsanity.com/paper/2405.17358/) (2024)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)
- [Compositional Reasoning with Transformers, RNNs, and Chain of Thought](https://mlsanity.com/paper/2503.01544/) (2025)
- [Fixed-Point RNNs: Interpolating from Diagonal to Dense](https://mlsanity.com/paper/2503.10799/) (2025)
- [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024)
- [A Tensor Decomposition Perspective on Second-order RNNs](https://mlsanity.com/paper/2406.05045/) (2024)
- [Synthesizing Context-free Grammars from Recurrent Neural Networks (Extended Version)](https://mlsanity.com/paper/2101.08200/) (2021)
- [A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks](https://mlsanity.com/paper/2505.24110/) (2025)
- [An Algebraic View of the Expressivity of Recurrent Language Models](https://mlsanity.com/paper/2606.01765/) (2026)
- [On the Representational Capacity of Recurrent Neural Language Models](https://mlsanity.com/paper/2310.12942/) (2023)
- [On Efficiently Representing Regular Languages as RNNs](https://mlsanity.com/paper/2402.15814/) (2024)
- [Universal computation is intrinsic to language model decoding](https://mlsanity.com/paper/2601.08061/) (2026)
- [Learning and Generalization in RNNs](https://mlsanity.com/paper/2106.00047/) (2021)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [Language models as tools for investigating the distinction between possible and impossible natural languages](https://mlsanity.com/paper/2512.09394/) (2025)
- [Large language models have learned to use language](https://mlsanity.com/paper/2512.12447/) (2025)
- [Large language models are not about natural language](https://mlsanity.com/paper/2512.13441/) (2025)
- [Linguists should learn to love speech-based deep learning models](https://mlsanity.com/paper/2512.14506/) (2025)

## Abstract (arXiv)

Recent neural network architectures such as the basic recurrent neural network (RNN) and Gated Recurrent Unit (GRU) have gained prominence as end-to-end learning architectures for natural language processing tasks. But what is the computational power of such systems? We prove that finite precision RNNs with one hidden layer and ReLU activation and finite precision GRUs are exactly as computationally powerful as deterministic finite automata. Allowing arbitrary precision, we prove that RNNs with one hidden layer and ReLU activation are at least as computationally powerful as pushdown automata. If we also allow infinite precision, infinite edge weights, and nonlinear output activation functions, we prove that GRUs are at least as computationally powerful as pushdown automata. All results are shown constructively.