# On the Representational Capacity of Recurrent Neural Language Models

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 19 Oct 2023.

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Pre-trained Models for Natural Language Processing: A Survey](https://mlsanity.com/paper/2003.08271/) (2020)
- [Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies](https://mlsanity.com/paper/1611.01368/) (2016)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [RecurrentGPT: Interactive Generation of (Arbitrarily) Long Text](https://mlsanity.com/paper/2305.13304/) (2023)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [RNNs can generate bounded hierarchical languages with optimal memory](https://mlsanity.com/paper/2010.07515/) (2020)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [Consistency of a Recurrent Language Model With Respect to Incomplete Decoding](https://mlsanity.com/paper/2002.02492/) (2020)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [A Measure-Theoretic Characterization of Tight Language Models](https://mlsanity.com/paper/2212.10502/) (2022)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [Context-Free Transductions with Neural Stacks](https://mlsanity.com/paper/1809.02836/) (2018)

## Built on by (most cited first, 1 of 1)

- [Data-driven Machine Learning Cannot Reach Symbolic-level Logical Reasoning -- The Limit of the Scaling Law](https://mlsanity.com/paper/2606.26454/) (2026)

## Abstract (arXiv)

This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. However, LMs define weightings over strings in addition to just (unweighted) language membership and the analysis of the computational power of RNN LMs (RLMs) should reflect this. We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMs. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.