# On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 26 Sep 2023.

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

- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [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)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [State-Regularized Recurrent Neural Networks](https://mlsanity.com/paper/1901.08817/) (2019)
- [The Neural State Pushdown Automata](https://mlsanity.com/paper/1909.05233/) (2019)
- [Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units](https://mlsanity.com/paper/2104.02899/) (2021)
- [Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack](https://mlsanity.com/paper/2004.07623/) (2020)

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

- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Language Models are Symbolic Learners in Arithmetic](https://mlsanity.com/paper/2410.15580/) (2024)
- [Investigating Symbolic Capabilities of Large Language Models](https://mlsanity.com/paper/2405.13209/) (2024)
- [Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Network](https://mlsanity.com/paper/2402.02627/) (2024)
- [Neural Networks Generalize on Low Complexity Data](https://mlsanity.com/paper/2409.12446/) (2024)
- [Tight Stability, Convergence, and Robustness Bounds for Predictive Coding Networks](https://mlsanity.com/paper/2410.04708/) (2024)
- [Precision, Stability, and Generalization: A Comprehensive Assessment of RNNs learnability capability for Classifying Counter and Dyck Languages](https://mlsanity.com/paper/2410.03118/) (2024)
- [Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights](https://mlsanity.com/paper/2410.03154/) (2024)

## Abstract (arXiv)

Artificial neural networks (ANNs) with recurrence and self-attention have been shown to be Turing-complete (TC). However, existing work has shown that these ANNs require multiple turns or unbounded computation time, even with unbounded precision in weights, in order to recognize TC grammars. However, under constraints such as fixed or bounded precision neurons and time, ANNs without memory are shown to struggle to recognize even context-free languages. In this work, we extend the theoretical foundation for the 2nd-order recurrent network (2nd RNN) and prove there exists a class of a 2nd RNN that is Turing-complete with bounded time. This model is capable of directly encoding a transition table into its recurrent weights, enabling bounded time computation and is interpretable by design. We also demonstrate that 2nd order RNNs, without memory, under bounded weights and time constraints, outperform modern-day models such as vanilla RNNs and gated recurrent units in recognizing regular grammars. We provide an upper bound and a stability analysis on the maximum number of neurons required by 2nd order RNNs to recognize any class of regular grammar. Extensive experiments on the Tomita grammars support our findings, demonstrating the importance of tensor connections in crafting computationally efficient RNNs. Finally, we show 2nd order RNNs are also interpretable by extraction and can extract state machines with higher success rates as compared to first-order RNNs. Our results extend the theoretical foundations of RNNs and offer promising avenues for future explainable AI research.