On the Turing Completeness of Modern Neural Network Architectures
Open accessThe DOI matches its OpenAlex record; 11 of the 11 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 · cited 1×
“Although having arbitrary precision is a standard assumption when studying the expressive power of neural networks (Cybenko (1989); Siegelmann & Sontag (1995)) practical implementations rely on fixed precision hardware.”
BackgroundIdentity 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).”
BackgroundInfluentialDehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., & Kaiser, Ł. (2018) · arXiv · doi:10.48550/arxiv.1807.03819 · Cited by 467
On 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
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
“Furthermore, it has been shown in the literature how self-attention (with positional encodings) is theoretically a more flexible operation that can model the behaviour of convolutional models toward encoding local features [157].”
BackgroundTransformers 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).”
BackgroundTheoretical 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
“The one prior theoretical study of transformers (Pérez et al., 2019) assumes hard attention.”
InfluentialTowards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective
Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., & Wang, L. (2023) · arXiv · doi:10.48550/arxiv.2305.15408 · Cited by 69
“, 2048 in GPT), avoiding the unrealistic (but crucial) assumption of infinite precision made in several prior works [43, 17].”
ResultOn 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
“Recently, it has been shown that Transformers are Turing-complete (Pérez et al., 2019; Bhattamishra et al., 2020) and are universal approximators of sequence-to-sequence functions given arbitrary precision (Yun et al.”
BackgroundSaturated 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
“Building on results of Pérez et al. (2019), we demonstrate in §6 that saturated transformers with float activations transcend the theoretical limitations of hard-attention transformers.”
ResultThe Parallelism Tradeoff: Limitations of Log-Precision Transformers
Merrill, W., & Sabharwal, A. (2023) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00562 · Cited by 22
“Prior formal characterizations of transformers either make unrealistically strong assumptions (Pérez et al., 2019; Dehghani et al., 2019) or place unrealistic restrictions (Hahn, 2020; Hao et al., 2022; Mer-rill et al., 2022).”
BackgroundFirst-person experience cannot rescue causal structure theories from the unfolding argument
Herzog, M. H., Schurger, A., & Doerig, A. (2022) · Consciousness and Cognition · doi:10.1016/j.concog.2021.103261 · Cited by 14
“…of universal function approximators, many of which are also Turing Complete, such as different varieties of recurrent networks, transformers and neural GPUs (i.e., modern neural network architectures; P ´ erez et al., 2019), cellular automata (Cook, 2004), many programming languages, and computers.”
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
- 11
- 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
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.