On the Turing Completeness of Modern Neural Network Architectures

Abstract

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.

arXiv commentICLR2019 camera ready

References in corpus (6)

• Universal Transformers
• Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets
• Learning to Transduce with Unbounded Memory
• Improving the Neural GPU Architecture for Algorithm Learning
• Neural Random-Access Machines
• Extensions and Limitations of the Neural GPU

Cited by in corpus (22)

• Transformers in Vision: A Survey
• Big Bird: Transformers for Longer Sequences
• Theoretical Limitations of Self-Attention in Neural Sequence Models
• What Can Neural Networks Reason About?
• Vector Symbolic Architectures as a Computing Framework for Emerging Hardware
• Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth
• An RNA-Based Theory of Natural Universal Computation
• Addressing Some Limitations of Transformers with Feedback Memory
• What graph neural networks cannot learn: depth vs width
• What Formal Languages Can Transformers Express? A Survey
• Handcrafted Backdoors in Deep Neural Networks
• How Powerful are Decoder-Only Transformer Neural Models?
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers
• It's Not What Machines Can Learn, It's What We Cannot Teach
• When FastText Pays Attention: Efficient Estimation of Word Representations using Constrained Positional Weighting
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Lipschitz Normalization for Self-Attention Layers with Application to Graph Neural Networks
• Symbolic integration by integrating learning models with different strengths and weaknesses
• On Learning the Transformer Kernel
• Self-Attention Networks Can Process Bounded Hierarchical Languages
• On the Representational Capacity of Recurrent Neural Language Models
• How Can Self-Attention Networks Recognize Dyck-n Languages?