# A provably stable neural network Turing Machine

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

## Key facts

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

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

- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Language Models are Symbolic Learners in Arithmetic](https://mlsanity.com/paper/2410.15580/) (2024)
- [Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Network](https://mlsanity.com/paper/2402.02627/) (2024)
- [When narrower is better: the narrow width limit of Bayesian parallel branching neural networks](https://mlsanity.com/paper/2407.18807/) (2024)
- [Like a bilingual baby: The advantage of visually grounding a bilingual language model](https://mlsanity.com/paper/2210.05487/) (2022)
- [Nondeterministic Stacks in Neural Networks](https://mlsanity.com/paper/2304.12955/) (2023)

## Abstract (arXiv)

We introduce a neural stack architecture, including a differentiable parametrized stack operator that approximates stack push and pop operations for suitable choices of parameters that explicitly represents a stack. We prove the stability of this stack architecture: after arbitrarily many stack operations, the state of the neural stack still closely resembles the state of the discrete stack. Using the neural stack with a recurrent neural network, we introduce a neural network Pushdown Automaton (nnPDA) and prove that nnPDA with finite/bounded neurons and time can simulate any PDA. Furthermore, we extend our construction and propose new architecture neural state Turing Machine (nnTM). We prove that differentiable nnTM with bounded neurons can simulate Turing Machine (TM) in real-time. Just like the neural stack, these architectures are also stable. Finally, we extend our construction to show that differentiable nnTM is equivalent to Universal Turing Machine (UTM) and can simulate any TM with only seven finite/bounded precision neurons. This work provides a new theoretical bound for the computational capability of bounded precision RNNs augmented with memory.