Attention is Turing-Complete

Reference: Pérez, J., Barceló, P., & Marinkovic, J. (2021). Attention is Turing-Complete. Journal of Machine Learning Research 22(75):1–35. URL. PDF: https://www.jmlr.org/papers/volume22/20-302/20-302.pdf. Extended journal version of the conference paper On the Turing Completeness of Modern Neural Network Architectures, ICLR 2019, arXiv:1901.03429 (https://arxiv.org/abs/1901.03429), which established the result for both the Transformer and the Neural GPU.

Summary

This paper studies the computational power of the Transformer, the architecture built entirely on Self-Attention introduced in Attention Is All You Need. Despite the Transformer’s practical dominance, its theoretical computational properties had not been characterised. The authors prove that the Transformer is Turing complete: a fixed-size network can simulate an arbitrary Turing machine, and hence compute any computable function.

The construction hinges on two ingredients. First, attention is taken to be hard attention (an argmax over positions) rather than the usual softmax-weighted average, so the network can deterministically retrieve a chosen earlier symbol. Second, the internal representations use arbitrary precision rationals, letting a bounded number of vector coordinates encode the unbounded state of a Turing-machine tape and head. The Transformer is run autoregressively: it reads its own previously emitted symbols, so each decoding step corresponds to one step of the simulated machine, and running for arbitrarily many steps simulates arbitrarily long computations. Carefully chosen positional encodings (functions of the position index such as i, 1/i, and trigonometric terms) let the network address and count over the sequence, while residual connections carry the encoded configuration forward.

Beyond the completeness theorem itself, the paper isolates a minimal set of elements the Transformer needs for the result — which components (hard attention, residual connections, positional encodings, unbounded precision) are load-bearing and which are inessential. The result is a theoretical characterisation, not a claim about practical finite-precision, finitely-decoded models: it establishes the ceiling of expressive power for the attention-only architecture, complementing the empirical, engineering-driven view of Attention Is All You Need and the scaling stance of The Bitter Lesson.

Key Ideas

Main theorem: the attention-only Transformer with hard attention is Turing complete — it can simulate any Turing machine.
Hard (argmax) attention replaces softmax averaging so the network can deterministically select and copy a specific earlier position.
Arbitrary-precision internal representations let a fixed number of coordinates encode the unbounded tape/head configuration of the simulated machine.
Autoregressive decoding as computation steps: feeding the network its own output means each generated symbol advances the simulated machine one step, giving unbounded computation from a fixed-size network.
Positional encodings do real computational work — they must let the network address, count, and locate symbols in the sequence, not merely disambiguate order.
Residual connections are used to carry the running machine configuration between layers/steps.
Minimality analysis: the paper identifies which architectural elements are essential to the completeness result and which can be dropped.
Scope caveat: the result assumes unbounded numerical precision and unboundedly many decoding steps — it is a statement about expressive-power limits, not about practical fixed-precision Transformers.
Neural GPU too: the original ICLR 2019 conference version (arXiv:1901.03429) proves the same Turing-completeness result for the Neural GPU — a fully convolutional architecture — showing neither model needs an external memory to reach universal computation.

Connections

Conceptual Contribution

Claim: The self-attention Transformer is not merely a powerful function approximator but a maximally expressive one in the classical sense — with hard attention and arbitrary precision it is Turing complete, so its computational ceiling is that of a universal machine.
Mechanism: Simulate a Turing machine with a fixed-size Transformer by (i) using hard/argmax attention to deterministically retrieve earlier symbols, (ii) encoding the unbounded tape configuration into arbitrary-precision internal vectors, (iii) running the network autoregressively so each decoding step is one machine step, and (iv) using computable positional encodings and residual connections to address and carry state.
Concepts introduced/used: Turing Completeness, Hard Attention, Arbitrary Precision, Transformer, Self-Attention, Positional Encoding, Universal Turing Machine, Computability
Stance: theoretical / expressiveness result
Relates to: Gives a computability-theoretic reading of the architecture from Attention Is All You Need; sits alongside the founding computability results of Turing 1936 and the undecidability landscape of Rice’s Theorem; a formal counterpoint to the empirical scaling narrative of The Bitter Lesson.

Backlinks

index

Linked Pages

The Bitter Lesson

Reference: Sutton, R. S. (March 13, 2019). Essay on personal website, Incomplete Ideas. Not a PDF — HTML essay, captured via ar-crawl. URL

Summary

Sutton’s short but enormously influential essay argues that seventy years of AI research teach one lesson: general methods that leverage computation are ultimately most effective, by a large margin, and attempts to encode human domain knowledge tend to plateau and eventually obstruct progress. The ultimate driver is Moore’s law — the exponentially falling cost of computation — which guarantees that whatever computational budget a method can exploit will become dramatically larger on timescales shorter than a research career. Researchers, pressed for short-term gains, routinely build in human understanding; this helps locally but impedes the methods that scale.

He marshals four case studies to make the point concrete: computer chess (Deep Blue’s brute-force search beat knowledge-engineered systems in 1997, to their practitioners’ dismay); computer Go (a 20-year delay of the same pattern, culminating in search + self-play value learning); speech recognition (statistical HMMs and later deep learning displaced phoneme/vocal-tract-engineered systems); and computer vision (edges, SIFT, generalized cylinders replaced by convolutional nets). The two methods that scale arbitrarily with compute are search and learning. The deeper second lesson: the contents of minds are irredeemably complex, so we should not try to build simple theories of space, objects, multi-agent interaction, or symmetry into systems; we should instead build meta-methods that can discover that complexity themselves. “We want AI agents that can discover like we can, not which contain what we have discovered.”

Key quotes preserved for future reference:

“The biggest lesson that can be read from 70 years of AI research is that general methods that leverage computation are ultimately the most effective, and by a large margin.”

“The two methods that seem to scale arbitrarily in this way are search and learning.”

“We have to learn the bitter lesson that building in how we think we think does not work in the long run.”

Classes of Recursively Enumerable Sets and Their Decision Problems

Reference: Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74(2), 358–366. DOI 10.2307/1990888. Based on Rice’s 1951 Princeton PhD thesis under Alonzo Church.

Summary

A nine-page paper that established one of the most consequential results in computability theory — now universally known as Rice’s Theorem. Rice’s question: given a class C of recursively enumerable (r.e.) sets, is there an effective procedure that, applied to a Gödel number (index) of an r.e. set W, decides whether W ∈ C? The paper’s central result is that the answer is no whenever C is a non-trivial extensional property — i.e. whenever C is neither empty nor the whole collection of r.e. sets, and membership in C depends only on which set is described, not on how it is described. Every property of the computed function itself (as opposed to syntactic properties of the program text) is therefore undecidable.

The proof is a reduction from the halting problem (Turing’s K). Rice constructs, for an arbitrary index i, a machine whose r.e. set is either a fixed element of C or a fixed element of its complement depending on whether φ_i(i) halts; a decision procedure for C would then decide K, which is known impossible. The technique — parametric construction of “switch” machines that toggle semantic behaviour based on a halting oracle — is the template used throughout undecidability theory for subsequent results (Rogers’ isomorphism theorem, the Myhill isomorphism, the theory of m-reducibility).

Beyond the headline theorem, the paper classifies decision problems about r.e. sets by the logical complexity of the class C: some non-trivial classes are Σ₁-hard, others Π₁-hard, others fall at higher levels of the arithmetical hierarchy. This classification anticipates the later development of degree theory. The paper is short, elementary, and entirely foundational: it tells us, once and for all, that semantic questions about arbitrary programs cannot be answered by mechanical inspection. Every program-analysis, verification, and capability-bounding enterprise since has been organised around the frontier Rice drew — by restricting the class of programs considered, approximating (sound-but-incomplete), or proving properties syntactically rather than semantically.

Key Ideas

Theorem B (Rice’s Theorem): for any non-trivial class C of r.e. sets, the problem of deciding whether a given r.e. set belongs to C is undecidable.
Extensional vs. intensional properties: C must depend on what is computed (the set), not on how (the index/program text). Intensional properties (program size, presence of a given opcode) can be decidable.
Proof by reduction from the halting problem, via a parametric “switch” construction that conditionally produces an element of C or its complement depending on whether a reference computation halts.
Arithmetical hierarchy classification of classes of r.e. sets by the quantifier complexity of their defining predicates, foreshadowing Kleene’s and Rogers’ later work.
Implicit corollary: every tool that claims to decide a non-trivial semantic property of arbitrary programs must either (i) restrict the input class, (ii) approximate, or (iii) violate computability.

Connections

Conceptual Contribution

Claim: There is no uniform effective procedure that decides any non-trivial extensional property of recursively enumerable sets; equivalently, every non-trivial semantic property of the partial function computed by an arbitrary program is undecidable.
Mechanism: Given a hypothesised decision procedure for a non-trivial class C, and a distinguishing pair A ∈ C, B ∉ C, construct for each index i a machine M_i that simulates φ_i(i) and, if it halts, begins enumerating A; otherwise enumerates B. The set enumerated by M_i is in C iff φ_i(i) halts, so a decision procedure for C would decide the halting problem — contradiction.
Concepts introduced/used: Rice’s Theorem, Halting Problem, Computability, Recursive Function, Universal Turing Machine
Stance: foundational theorem paper (computability theory)
Relates to: Generalises Turing’s halting theorem from the specific property “halts on input x” to all non-trivial semantic properties; sets the decidability frontier that all subsequent work in Formal Verification, Static Analysis, and LangSec (Security Applications Of Formal Language Theory, The Halting Problems of Network Stack Insecurity) must respect; directly underwrites the Rice’s-theorem argument in House on Rock - LangSec in Ethereum Classic that Ethereum’s gas mechanism cannot deliver a semantic safety guarantee.

On Computable Numbers with an Application to the Entscheidungsproblem

On Computable Numbers, with an Application to the Entscheidungsproblem

Reference: Turing, Alan M. (1936). “On computable numbers, with an application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society, series 2, vol. 42, pp. 230–265 (read 1936, published 1937); correction in vol. 43 (1937), pp. 544–546. DOI 10.1112/plms/s2-42.1.230. Scan: cs.virginia.edu/~robins.

Summary

Turing’s 1936 paper is, with Church 1936, one of the two founding documents of computability theory. Its purpose is to make precise the informal idea of an effective procedure, and then to settle Hilbert’s Entscheidungsproblem — the question of whether there is a mechanical decision procedure for validity in first-order logic. Turing’s answer is negative, and the machinery he builds to reach it defines the field.

The central construction is the abstract computing machine (Turing’s “a-machine”, now the Turing machine): a device with a finite set of internal m-configurations, a two-way infinite tape divided into squares, and a head that reads and writes symbols and moves one square at a time according to a finite table of behaviour. A real number is computable when its digits can be written out by such a machine. Turing then shows how to encode any machine’s table as a single integer — its standard description / description number — and constructs a universal machine that, given the description number of any machine M, reproduces M’s behaviour. This is the theoretical origin of the stored-program computer: one machine that runs any program supplied as data.

From here the negative results follow by a diagonal argument. Turing distinguishes circle-free machines (which go on printing digits forever) from circular ones, and proves that no machine can decide, of an arbitrary machine’s description number, whether it is circle-free — the ancestor of the modern halting problem. Applying the same self-referential technique to logic, he shows there can be no general effective procedure deciding whether a first-order formula is provable, so the Entscheidungsproblem is unsolvable. An appendix argues that Turing-computability coincides with Church’s λ-definability (and hence with Herbrand–Gödel–Kleene general recursiveness), the equivalence that grounds the Church–Turing thesis.

Key Ideas

Turing machine (a-machine): finite m-configurations + unbounded tape + read/write head governed by a finite behaviour table — a precise model of effective calculation.
Computable numbers/functions: reals (and functions) whose digits an a-machine can generate; the computable reals are countable.
Standard description / description number: an arithmetic encoding of a machine’s table, letting machines take other machines as input.
Universal Turing Machine (U): a single machine that simulates any machine from its description number — the conceptual root of the stored-program computer.
Circle-free vs circular machines, and the undecidability of circle-freeness by diagonalisation — ancestor of the Halting Problem.
Undecidability of the Entscheidungsproblem: no effective procedure decides validity/provability in first-order logic.
Church–Turing equivalence: Turing-computability = λ-definability = general recursiveness (appendix).

Connections

Conceptual Contribution

Claim: The informal notion of effective calculability is captured exactly by the Turing machine; there is no machine that decides circle-freeness, and consequently the Entscheidungsproblem for first-order logic is unsolvable.
Mechanism: Model computation as a finite-state machine over an unbounded tape; arithmetise machines as description numbers so a universal machine can simulate any machine; diagonalise over description numbers to produce a problem no machine can decide, then transport that undecidability into first-order provability.
Concepts introduced/used: Universal Turing Machine, Computability, Halting Problem, Diagonalization, Church–Turing thesis, Entscheidungsproblem, First-Order Logic
Stance: foundational theorem paper (mathematical logic / computability)
Relates to: Independent of and contemporaneous with Church 1936, with which it is equated in the appendix; extends the self-reference lineage of Cantor 1891 and Gödel 1931; the undecidability frontier it opens is generalised by Rice 1953 and its universal machine anticipates von Neumann’s universal construction.

Attention Is All You Need

Reference: Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017). Advances in Neural Information Processing Systems 30 (NeurIPS). arXiv:1706.03762. Source file: vaswani_attention_is_all_you_need.pdf. URL

Summary

The paper introduces the Transformer, a sequence-transduction architecture that dispenses entirely with recurrence and convolution and relies solely on attention mechanisms to model dependencies between input and output tokens. An encoder stack of N=6 identical layers, each composed of a multi-head self-attention sub-layer and a position-wise feed-forward sub-layer (with residual connections and layer normalisation), encodes the source; a symmetric decoder stack augments each layer with masked self-attention and cross-attention to the encoder output. Because the architecture has no inherent notion of token order, sinusoidal positional encodings are added to the input embeddings.

The core primitive is scaled dot-product attention, Attention(Q,K,V) = softmax(QKᵀ/√dₖ)V, extended to multi-head attention by linearly projecting Q, K, V h=8 times into lower-dimensional subspaces, running attention in parallel, and concatenating the results. The motivation is computational: self-attention has O(1) sequential operations and O(1) maximum path length between any two positions — much shorter than recurrent or convolutional alternatives — enabling far greater parallelism and better gradient flow over long distances. The Transformer achieves state-of-the-art BLEU on WMT 2014 En–De (28.4) and En–Fr (41.8) at a small fraction of prior training cost and generalises to constituency parsing. It is the architectural substrate on which virtually all subsequent large language models are built.

Key Ideas

Pure attention architecture; no recurrence or convolution.
Scaled dot-product attention with 1/√dₖ scaling to stabilise softmax gradients.
Multi-head attention for attending to different representation subspaces.
Three uses of attention: encoder self-attention, decoder masked self-attention, encoder-decoder cross-attention.
Sinusoidal positional encodings enable extrapolation beyond training lengths.
O(1) path length supports learning of long-range dependencies.
Massive parallelism compared to RNNs; dramatic training cost reduction.

Connections

Conceptual Contribution

Claim: Recurrence and convolution are unnecessary for high-quality sequence transduction; an architecture built entirely from (multi-head, self-)attention and feed-forward layers outperforms prior state-of-the-art on machine translation while training in a fraction of the time.
Mechanism: Replace RNN hidden-state chains with an encoder-decoder stack of identical layers, each using scaled dot-product multi-head attention plus position-wise FFN with residual connections and layer norm; inject order via sinusoidal positional encodings; use masked self-attention in the decoder to preserve autoregression; exploit O(1) sequential complexity and O(1) max path length to parallelise across sequence positions and shorten gradient paths to long-range dependencies.
Concepts introduced/used: Transformer, Self-Attention, Multi-Head Attention, Positional Encoding, Scaled Dot-Product Attention, Encoder-Decoder Attention
Stance: empirical architecture paper
Relates to: Architectural substrate for Language Models are Few-Shot Learners, Toolformer and the entire LLM Agents literature; exemplifies the scaling-over-structure thesis of The Bitter Lesson; reshapes what “agent architecture” means relative to Intelligent Agents Theory and Practice’s 1990s taxonomy.

In this vault

Exploit Programming - From Buffer Overflows To Weird Machines
The Halting Problems of Network Stack Insecurity
Chomsky Hierarchy
An Unsolvable Problem of Elementary Number Theory — Church 1936.
General Recursive Functions of Natural Numbers — Kleene 1936.
Recursive Predicates and Quantifiers — Kleene 1943, arithmetical hierarchy.
Recursively Enumerable Sets of Positive Integers and Their Decision Problems — Post 1944.

Universal Turing Machine

A Turing machine that, given the encoding of an arbitrary machine and an input, simulates that machine’s behaviour on the input. Its existence is the foundation of general-purpose computation and of algorithmic information theory.

In this vault

Positional Encoding

Additive (sinusoidal or learned) signal that injects sequence-position information into an otherwise permutation-equivariant attention layer.

In this vault

Self-Attention

Mechanism by which each position in a sequence attends to every other position; the core primitive of the Transformer.

In this vault

Transformer

Vaswani et al. 2017 neural-network architecture built solely from attention and feed-forward layers (no recurrence or convolution). The backbone of every modern LLM.

In this vault

Arbitrary Precision

(page does not exist)

Hard Attention

(page does not exist)

Turing Completeness

(page does not exist)

Neural GPU

(page does not exist)

Scaled Dot-Product Attention

Vaswani et al.: attention weights = softmax(QK^T / √d_k) V. The single-head primitive underlying multi-head attention.

In this vault

Multi-Head Attention

Running several attention operations in parallel on different learned projections, then concatenating. Lets a Transformer layer attend to multiple relational patterns simultaneously.

Attention is Turing-Complete

Summary

Key Ideas

Connections

Conceptual Contribution

Tags

Backlinks