# On the Practical Computational Power of Finite Precision RNNs for Language Recognition

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

## Key facts

- Cited by 117 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2018.

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

- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Going Beyond Linear Transformers with Recurrent Fast Weight Programmers](https://mlsanity.com/paper/2106.06295/) (2021)
- [How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding](https://mlsanity.com/paper/2303.04245/) (2023)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Mechanistic Design and Scaling of Hybrid Architectures](https://mlsanity.com/paper/2403.17844/) (2024)
- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Memory Augmented Large Language Models are Computationally Universal](https://mlsanity.com/paper/2301.04589/) (2023)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Mission: Impossible Language Models](https://mlsanity.com/paper/2401.06416/) (2024)
- [Counting Ability of Large Language Models and Impact of Tokenization](https://mlsanity.com/paper/2410.19730/) (2024)
- [Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammars](https://mlsanity.com/paper/2312.01429/) (2023)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Mechanistic?](https://mlsanity.com/paper/2410.09087/) (2024)
- [Minimum Description Length Recurrent Neural Networks](https://mlsanity.com/paper/2111.00600/) (2021)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (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)
- [Inducing Transformer's Compositional Generalization Ability via Auxiliary Sequence Prediction Tasks](https://mlsanity.com/paper/2109.15256/) (2021)
- [Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory](https://mlsanity.com/paper/2405.16674/) (2024)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Limits for Learning with Language Models](https://mlsanity.com/paper/2306.12213/) (2023)
- [Exploring Transitivity in Neural NLI Models through Veridicality](https://mlsanity.com/paper/2101.10713/) (2021)

## Abstract (arXiv)

While Recurrent Neural Networks (RNNs) are famously known to be Turing complete, this relies on infinite precision in the states and unbounded computation time. We consider the case of RNNs with finite precision whose computation time is linear in the input length. Under these limitations, we show that different RNN variants have different computational power. In particular, we show that the LSTM and the Elman-RNN with ReLU activation are strictly stronger than the RNN with a squashing activation and the GRU. This is achieved because LSTMs and ReLU-RNNs can easily implement counting behavior. We show empirically that the LSTM does indeed learn to effectively use the counting mechanism.