On the Practical Computational Power of Finite Precision RNNs for Language Recognition
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Transformers with O(n) decoding steps can solve any problem a Turing machine can solve in O(n) time.
“Thus, simulating an automaton (cf.Theorem 1) is not the only new capability unlocked with O(n) decoding steps: rather, such transformers can solve any problem a Turing machine can solve in O(n) time, such as simulating real-time counter machines (Weiss et al., 2018).”
From The expressive power of transformers with chain of thought (2023) · cites this paper as Weiss et al., 2018
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Greff, K., Srivastava, R. K., Koutnik, J., Steunebrink, B. R., & Schmidhuber, J. (2017) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2016.2582924 · Cited by 6,955 · see citing works
Flagged first, then by citations
Research works printed but not linked: 17
- Roee Aharoni and Yoav Goldberg. 2017. Towards string-to-tree neural machine translation. In Pro- ceedings of the 55th Annual Meeting of the Associa- tion for Computational Linguistics (Volume 2: Short Papers), pages 132-140, Vancouver, Canada. Asso- ciation for Computational Linguistics.
- Yining Chen, Sorcha Gilroy, Kevin Knight, and Jonathan May. 2017. Recurrent neural net- works as weighted language recognizers. CoRR, abs/1711.05408. · arXiv
- Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning Phrase Representations using RNN En- coder-Decoder for Statistical Machine Translation. In Proceedings of the 2014 Conference on Em- pirical Methods in Natural Language Processing (EMNLP), pages 1724-1734, Doha, Qatar. Associ- ation for Computational Linguistics.
- Do Kook Choe and Eugene Charniak. 2016. Parsing as language modeling. In Proceedings of the 2016 Conference on Empirical Methods in Natural Lan- guage Processing, pages 2331-2336, Austin, Texas. Association for Computational Linguistics.
- Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. 2014. Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling. arXiv:1412.3555 [cs]. · arXiv
- Jeffrey L. Elman. 1990. Finding Structure in Time. Cognitive Science, 14(2):179-211. · DOI · Paper page
- Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. 1968. Counter machines and counter languages. Mathematical systems theory, 2(3):265- 283. · DOI
- F. A. Gers and E. Schmidhuber. 2001. Lstm recur- rent networks learn simple context-free and context- sensitive languages. Transactions on Neural Net- works, 12(6):1333-1340. · DOI
- F. A. Gers and J. Schmidhuber. 2000. Recurrent nets that time and count. In Proceedings of the IEEE- INNS-ENNS International Joint Conference on Neu- ral Networks. IJCNN 2000. Neural Computing: New Challenges and Perspectives for the New Millen- nium, volume 3, pages 189-194 vol. · DOI
- Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735-1780.
- Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. 2016. Bina- rized neural networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 4107-4115.
- Quoc V. Le, Navdeep Jaitly, and Geoffrey E. Hinton. 2015. A Simple Way to Initialize Recurrent Net- works of Rectified Linear Units. arXiv:1504.00941 [cs]. · arXiv
- Hava Siegelmann. 1999. Neural Networks and Analog Computation: Beyond the Turing Limit, 1 edition. Birkhäuser Basel. · DOI
- Hava T. Siegelmann. 1996. Recurrent neural networks and finite automata. Computational Intelligence, 12:567-574. · DOI
- Hava T. Siegelmann and Eduardo D. Sontag. 1992. On the computational power of neural nets. In Pro- ceedings of the Fifth Annual ACM Conference on Computational Learning Theory, COLT 1992, Pitts- burgh, PA, USA, July 27-29, 1992., pages 440-449. · DOI · Paper page
- Hava T. Siegelmann and Eduardo D. Sontag. 1994. Analog computation via neural networks. Theor. Comput. Sci., 131(2):331-360. · DOI
- Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Gram- mar as a foreign language. In Proceedings of the 28th International Conference on Neural Informa- tion Processing Systems -Volume 2, NIPS'15, pages 2773-2781, Cambridge, MA, USA. MIT Press.
Cited by
Sorted by citations
GuacaMol: Benchmarking Models for de Novo Molecular Design
Brown, N., Fiscato, M., Segler, M. H. S., & Vaucher, A. C. (2019) · Journal of Chemical Information and Modeling · doi:10.1021/acs.jcim.8b00839 · Cited by 895 · see citing works
Do NLP Models Know Numbers? Probing Numeracy in Embeddings
Wallace, E., Wang, Y., Li, S., Singh, S., & Gardner, M. (2019) · Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) · doi:10.18653/v1/d19-1534 · Cited by 227 · see citing works
Theoretical Limitations of Self-Attention in Neural Sequence Models
Hahn, M. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00306 · Cited by 165 · see citing works
On the Ability and Limitations of Transformers to Recognize Formal Languages
Bhattamishra, S., Ahuja, K., & Goyal, N. (2020) · Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.576 · Cited by 48 · see citing works
Seidel, R., Jahn, N., Seo, S., Goerttler, T., & Obermayer, K. (2022) · IEEE Open Journal of Intelligent Transportation Systems · doi:10.1109/ojits.2021.3139393 · Cited by 28 · see citing works
Saturated Transformers are Constant-Depth Threshold Circuits
Merrill, W., Sabharwal, A., & Smith, N. A. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00493 · Cited by 25 · see citing works
On the Linguistic Capacity of Real-Time Counter Automata
Merrill, W. (2020) · arXiv · doi:10.48550/arxiv.2004.06866 · Cited by 12 · see citing works
The expressive power of transformers with chain of thought
Merrill, W., & Sabharwal, A. (2023) · arXiv · doi:10.48550/arxiv.2310.07923 · Cited by 4 · see citing works
- Authors
- Weiss, G., Goldberg, Y., & Yahav, E.
- Affiliations
- Technion – Israel Institute of Technology (IL)
- Bar-Ilan University (IL)
- Venue
- Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)
- Published
- 2018
- Pages
- 740-745
- ISSN
- 0736-587X (ISSN-L)
- OpenAlex
- W2798579706
- Cited by
- 226
- References
- 1
- Citations by year
- 2026: 4 · 2025: 8 · 2024: 11 · 2023: 21 · 2022: 28 · 2021: 47 · 2020: 60 · 2019: 34 · 2018: 13
- FWCI
- 42.22
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- Locations
- Proceedings of the conference - Association for Computational Linguistics. Meeting (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Allen Institute for Artificial Intelligence
- European Commission
- FP7 Ideas: European Research Council (615688)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- finite precision arithmetic, recurrent neural networks, computational power, Turing completeness, language identification, LSTM, GRU, ReLU activation, linear-time computation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
