Attention is Turing Complete: Decoding the Computational Universality of Transformers

[JMLR 2021] Deep dive into the theoretical foundations of self-attention architectures and their ability to simulate any algorithm.

Executive Summary

TL;DR: This research provides the formal mathematical proof that the Transformer architecture belongs to the class of Turing complete models. Unlike recurrent neural networks (RNNs) that achieve this through sequential hidden states, Transformers achieve universality through their ability to compute and address internal dense representations.

Background: Since "Attention is All You Need" (2017), Transformers have dominated SOTA leaderboards. However, the theoretical limits of their "reasoning" were poorly understood. This paper closes that gap, positioning the Transformer not just as a powerful sequence model, but as a general-purpose computational device capable of simulating any Turing Machine (TM).

Problem & Motivation: The "Proportion-Invariance" Trap

The authors first point out a glaring weakness: standard Transformers (without positional encodings) are order-invariant. If you shuffle the input sequence, the output remains the same. Even worse, the authors prove a stronger property called Proportion Invariance.

Theorem: A Transformer without positional encodings cannot distinguish between two strings if they have the same ratio of symbols (e.g., "aabb" vs "aaabbb").

This means a vanilla Transformer cannot even recognize the simplest regular languages (like "even number of a's"). To solve this, researchers typically add positional encodings, but this paper explores whether this addition, combined with the attention mechanism, is enough to reach the gold standard of computation: Turing Completeness.

Methodology: Building a Neural Turing Machine

The authors' strategy is to simulate a 1-tape Turing Machine $M$ using the Transformer's encoder-decoder structure.

1. The Encoder as Initial Tape

The encoder takes the input string and maps it into a sequence of keys ($K^e$) and values ($V^e$). Crucially, these values store the symbol and its position $i$.

2. The Decoder as Control Unit

The simulation happens in the decoder over $r$ steps. The authors design a 3-layer decoder to handle the "fetch-decode-execute" cycle of a Turing Machine:

• Layer 1 (The Transition): Computes the next state $q$, the symbol to write $v$, and the head movement $m$ based on the current state and symbol.
• Layer 2 (The Pointer): Computes the absolute position of the tape head $c(i)$ by summing up all previous moves.
• Layer 3 (The Memory Access): Uses hard-attention to "look back" at the history of the decoder's output to find the last symbol written at the current head position.

Note: The decoder uses hard-attention to simulate an "addressable" memory, finding the 'last step' the head visited a specific cell.

3. Key Mathematical Levers

• Hard Attention: Instead of the probabilistic softmax, the authors use hardmax, selecting exactly one "memory" position.
• Arbitrary Precision: The proof assumes activations are rational numbers with arbitrary precision, allowing the model to encode positions like $1/n^2$ without overlap.

Experiments & Results: Theoretical SOTA

The paper is a theoretical proof rather than a benchmark-chasing experiment. However, its findings are profound:

1. Complexity Mapping: The authors show that for any language in the complexity class $Time(T(n))$, there exists a $T(n)$-bounded Transformer that can recognize it.
2. Structural Requirements: The proof shows that Residual Connections are not just for training stability—they are functionally necessary to pass the "tape state" forward through layers.

Note: The paper demonstrates that by using specific positional values (n, 1/n, 1/n²), the model can uniquely resolve any tape position in the TM simulation.

Critical Analysis & Conclusion

Takeaway

The Transformer is more than a statistical language model; it is a Neural Execution Engine. Its ability to attend to any past state allows it to function like a computer with a random-access memory (RAM) where the "time" steps of the decoder serve as the memory addresses.

Limitations

• Soft vs. Hard Attention: Most real-world Transformers use Soft Attention. The authors note that while Soft Attention is more differentiable, it might not reach Turing Completeness under fixed-precision constraints.
• The Precision Trap: In practice, we use 16-bit or 32-bit floats. The authors acknowledge that with fixed precision, Transformers are actually not Turing complete because they revert to being finite-state devices.

Future Outlook

This research justifies the move toward "Universal Transformers" and suggests that if we want models to truly "calculate," we should pay closer attention to how we implement positional encodings and precision in memory access.

References:

• Vaswani et al. (2017). Attention is All You Need.
• Siegelmann & Sontag (1995). On the computational power of neural nets.