On the Turing Completeness of Modern Neural Network Architectures

By Jorge Pérez, Javier Marinkovic, Pablo Barceló. 2019

183 citations recorded by the source corpus.

Alternatives to recurrent neural networks, in particular, architectures based on attention or convolutions, have been gaining momentum for processing input sequences. In spite of their relevance, the computational properties of these alternatives have not yet been fully explored. We study the computational power of two of the most paradigmatic architectures exemplifying these mechanisms: the Transformer (Vaswani et al., 2017) and the Neural GPU (Kaiser & Sutskever, 2016). We show both models to be Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. In particular, neither the Transformer nor the Neural GPU requires access to an external memory to become Turing complete. Our study also reveals some minimal sets of elements needed to obtain these completeness results.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Model Architectures

Citations in the corpus

Big Bird: Transformers for Longer Sequences (2020, methodology): “Most of the construction of Pérez et al. [72] goes through for sparse attentions, except for their addressing scheme to point back in history (Lemma B.4 in [72]).”
On the Relationship between Self-Attention and Convolutional Layers (2019, background): “Indeed, P´erez et al. (2019) showed that a multi-layer attention-based architecture with additive positional encodings is Turing complete under some strong theoretical assumptions, such as unbounded precision arithmetic.”
Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth (2021, background): “There have been other recent advances in understanding the theory behind transformers: [PMB19, DGV + 19] proved Turing universality, [CLJ20b] provided necessary and sufficient conditions for attention to simulate convolution.”
Transformers in Vision: A Survey (2021, background): “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].”
Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, result): “, 2048 in GPT), avoiding the unrealistic (but crucial) assumption of infinite precision made in several prior works [43, 17].”
Can Transformers Learn to Solve Problems Recursively? (2023, background): “Understanding Transformers Work on understanding the underlying mechanisms of transformers spans many angles, from categorizing computational capabilities [10, 44, 45, 43] by measuring performance on synthetic tasks, to deriving theoretical arguments [22, 25, 30, 31, 18], to analyzing the functional”
$O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers (2020, background): “Naturally, the self-attention layer also plays the key role in the analysis of Transformers [3, 4, 12, 20, 33]; for example, Yun et al.”
Transformer Dissection: An Unified Understanding for Transformer’s Attention via the Lens of Kernel (2019, background): “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).”
Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (2024, methodology): “…output of each arithmetic operation is rounded to the closest floating point number representable by a fixed number of digits following IEEE 754 standard (Definition 3.2), thus avoiding the unrealistic infinite precision assumption made by prior works (Pérez et al., 2019; Dehghani et al., 2018).”
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes (2022, background): “There is a long line of work investigating the capabilities [69, 15, 77, 51, 76, 7, 78], limitations [25, 6], applications [37, 17, 49], and internal workings [19, 65, 71, 18, 48] of Transformer models.”
Theoretical Limitations of Self-Attention in Neural Sequence Models (2019, unknown): “The one prior theoretical study of transformers (Pérez et al., 2019) assumes hard attention.”
Looped Transformers as Programmable Computers (2023, methodology): “Constructive arguments have demonstrated that Transformers can simulate Turing Machines with enough depth or recursive links between attention layers (Pérez et al., 2021; Pérez et al., 2019; Wei et al., 2022a).”
LLM Web Dynamics: Tracing Model Collapse in a Network of LLMs (2025, unknown): “The discrepancy arises because a B -component GMM is restricted to a finite parametrization, while a Transformer-based LLM occupies an effectively infinite-dimensional func-7 tion space (Pérez et al., 2019; Yang, 2020).”