On the Turing Completeness of Modern Neural Network Architectures
Open accessThe DOI matches its OpenAlex record; 10 of the 10 references it cites were found in a registry or an index.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474
A logical calculus of the ideas immanent in nervous activity
McCulloch, W. S., & Pitts, W. (1943) · The Bulletin of Mathematical Biophysics · doi:10.1007/bf02478259 · Cited by 18,566
Approximation by superpositions of a sigmoidal function
Cybenko, G. (1989) · Mathematics of Control, Signals, and Systems · doi:10.1007/bf02551274 · Cited by 13,883
Identity mappings in deep residual networks
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46493-0_38 · Cited by 10,741
Identity Mappings in Deep Residual Networks
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · arXiv · doi:10.48550/arxiv.1603.05027 · Cited by 10,665 · cited 2×
“)) + x i (6) z i = O(a i) + a i (7) In practice Q(), K(), V() are typically matrix multiplications, and O() a feed-forward network. The + x iand + a isummands are usually called residual connections (He et al., 2016a;b). When the particular functions used as parameters are not important, we simply write Z= Enc(X). The…”
BackgroundMethodSelf-Attention with Relative Position Representations
Shaw, P., Uszkoreit, J., & Vaswani, A. (2018) · Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers) · doi:10.18653/v1/n18-2074 · Cited by 2,505 · cited 1×
“This weakness has motivated the need for including information about the order of the input sequence by other means; in particular, this is often achieved by using the so-called positional encodings (Vaswani et al., 2017; Shaw et al., 2018), which we study below.”
MethodGraves, A., Wayne, G., & Danihelka, I. (2014) · arXiv · doi:10.48550/arxiv.1410.5401 · Cited by 1,058 · cited 4×
“There is an increasing interest in designing neural network architectures capable of learning algorithms from examples (Graves et al., 2014; Grefenstette et al., 2015; Joulin & Mikolov, 2015; Kaiser & Sutskever, 2016; Kurach et al., 2016; Dehghani et al., 2018).”
BackgroundInfluentialOn the computational power of neural nets
Siegelmann, H. T., & Sontag, E. D. (1992) · Proceedings of the fifth annual workshop on Computational learning theory · doi:10.1145/130385.130432 · Cited by 238
On the Practical Computational Power of Finite Precision RNNs for Language Recognition
Weiss, G., Goldberg, Y., & Yahav, E. (2018) · Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) · doi:10.18653/v1/p18-2117 · Cited by 226
Recurrent Neural Networks as Weighted Language Recognizers
Chen, Y., Gilroy, S., Maletti, A., May, J., & Knight, K. (2018) · Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers) · doi:10.18653/v1/n18-1205 · Cited by 49
Cited by
Transformers in Vision: A Survey
Khan, S., Naseer, M., Hayat, M., Zamir, S. W., Khan, F. S., & Shah, M. (2022) · ACM Computing Surveys · doi:10.1145/3505244 · Cited by 3,595
Transformers in Vision: A Survey
Khan, S., Naseer, M., Hayat, M., Zamir, S. W., Khan, F. S., & Shah, M. (2021) · arXiv · doi:10.48550/arxiv.2101.01169 · Cited by 3,594
Big Bird: Transformers for Longer Sequences
Zaheer, M., Guruganesh, G., Dubey, A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang, L., et al. (2020) · arXiv · doi:10.48550/arxiv.2007.14062 · Cited by 1,349
Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth
Dong, Y., Cordonnier, J.-B., & Loukas, A. (2021) · arXiv · doi:10.48550/arxiv.2103.03404 · Cited by 195
Transformer Dissection: An Unified Understanding for Transformer’s Attention via the Lens of Kernel
Tsai, Y.-H. H., Bai, S., Yamada, M., Morency, L.-P., & Salakhutdinov, R. (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-1443 · Cited by 173
“In other words, previous work did not consider the mask between queries and keys when discussing the order-invariance problem (Pérez et al., 2019).”
Background
Metadata
- Authors
- Pérez, J. E. P., Marinković, J., & Barceló, P.
- Venue
- arXiv (Cornell University)
- Publisher
- Cornell University
- Published
- 2019-01-10
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1901.03429
- OpenAlex
- W2908802752
- Cited by
- 78
- References
- 10
- Type
- posted content
- Language
- en
- Open access
- green
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On the Turing Completeness of Modern Neural Network Architectures. https://app.cochat.ai/papers/10.48550/arxiv.1901.03429
- The paper
- Pérez, J. E. P., Marinković, J., & Barceló, P. (2019). On the Turing Completeness of Modern Neural Network Architectures. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1901.03429
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.