PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Turing Completeness of Modern Neural Network Architectures

Jorge Pérez, Javier Marinković, Pablo Barceló

arXiv:1901.03429v1cs.LGcs.FLstat.ML

TL;DR

The paper asks whether attention- and convolution-based neural architectures have sufficient computational power to implement arbitrary algorithms. It formally analyzes Transformers and Neural GPUs by constructing simulations of Turing machines or sequence-to-sequence RNNs. It shows both architectures are Turing complete without external memory, while identifying dependence on internal representations and, for the Transformer proof, arbitrary precision.

  • Problem

    The computational properties of Transformer and Neural GPU architectures, despite their growing use for sequence processing, had not been fully explored.

  • Method

    The paper proves completeness by directly simulating Turing machines with Transformers and simulating standard sequence-to-sequence RNNs with Neural GPUs.

  • Results

    The Transformer with positional encodings and the uniform Neural GPU are Turing complete, while uniform Neural GPUs with circular convolutions are not.

  • Takeaways & Limitations

    Turing completeness can arise from computing and accessing internal dense representations without requiring external additional memory.

  • Takeaways & Limitations

    The Transformer completeness proof relies on arbitrary-precision internal representations, whereas fixed-precision implementations reduce positional encodings to a finite input-alphabet effect.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies whether attention- and convolution-based sequence architectures can be Turing complete without external memory. It proves this for Transformers and Neural GPUs using internal dense representations, while formalizing a comparison previously treated informally.

  • Motivation: Turing completeness is required for neural architectures intended to learn arbitrary algorithms from examples.Such architectures must be capable of implementing arbitrary algorithms.
  • Background: RNNs can be Turing complete with bounded neurons and weights by computing and accessing internal dense representations.This perspective differs from approaches that rely on an explicit unbounded external memory.
  • Scope: The paper examines Turing completeness for non-recurrent sequence architectures based on attention or convolutions, focusing on the Transformer and Neural GPU.These architectures manipulate sequences without directly applying recurrence to process input symbols sequentially.
  • Contributions: The Transformer and Neural GPU are shown Turing complete using internal dense representations, without external additional memory, under bounded architecture size and arbitrary-precision rational activations.The Transformer directly simulates a Turing machine, whereas the Neural GPU simulates standard sequence-to-sequence RNNs.
  • Contributions: The paper provides a formal comparison of Transformer and Neural GPU computational power after prior work had used both architectures only informally.The paper also reports minimal element sets sufficient for the completeness results.

2 PRELIMINARIES

The preliminaries formalize sequence-to-sequence recognizers and Turing completeness, establish the RNN result used later, and state the rational-arithmetic assumptions underlying the analysis.

  • Assumptions: The analysis assumes rational weights and activations with arbitrary precision, using rational functions and a piecewise-linear sigmoidal activation in most positive results.The activation is defined over rational numbers.
  • Seq-to-seq formalization: A sequence-to-sequence network maps an input sequence of rational vectors and a seed vector to an output sequence, whose length is controlled by a stopping criterion.The input and output vectors have a fixed dimension d.
  • Seq-to-seq formalization: A language recognizer combines a finite alphabet, an embedding function, a sequence-to-sequence network, a seed vector, and a set of final vectors.A string is accepted when some generated output ends in the final-vector set.
  • Recognizer restrictions: The embedding and final-vector membership tests are required to be computable in time linear in the relevant input or representation size.These restrictions cover one-hot or fixed-network embeddings and equality checks against fixed terminal vectors.
  • Turing completeness: A network class is Turing complete when its recognizers accept exactly the languages recognized by Turing machines.The definition applies to the language class induced by the network architecture class.
  • RNN formalization: Encoder-decoder RNNs use an encoder recurrence to construct a final hidden state and a decoder recurrence to generate the output sequence.The formalization includes the encoder and decoder recursions, with the decoder initialized from the encoder state.
  • RNN completeness: Encoder-decoder RNNs remain Turing complete even when recurrent matrix R and biases are zero, the output is the identity, and both activations are piecewise-linear sigmoids.This restricted theorem supplies the RNN completeness result used in later simulations.

3 THE TRANSFORMER ARCHITECTURE

The section formalizes Transformer encoders, decoders, and attention, then characterizes their computational power with and without positional encodings. Without positional encodings, Transformers are proportion-invariant; with them, they are Turing complete under arbitrary-precision assumptions.

  • Architecture: The formalized Transformer repeatedly applies encoder and decoder layers to sequences of rational vectors, producing outputs through attention-based transformations.The encoder returns key-value sequences, while the decoder autoregressively generates output vectors from encoded inputs and prior outputs.
  • Architecture: Attention computes a weighted combination of value vectors whose weights depend on query-key scores and normalization.Under the specified normalization, the output is a convex combination of the value vectors; hard attention selects maximal-score positions.
  • Invariance under proportions: Without positional encodings, Transformer outputs are invariant to symbol order and, more strongly, to preserving every symbol’s proportion.Consequently, the architecture cannot recognize every order-invariant regular language, including strings with an even number of a symbols.
  • Invariance under proportions: Despite these limitations, a Transformer without positional encodings can recognize the non-regular language of strings containing more a symbols than b symbols.Thus, its unencoded computational power is weaker than full regular-language recognition but not characterized by regularity alone.
  • Positional encodings and completeness: Adding positional encodings makes the class of Transformer networks Turing complete.The proof constructs a Transformer that simulates the complete execution of any Turing machine using encoded machine states, tape symbols, and positions.
  • Positional encodings and completeness: The completeness proof requires arbitrary-precision internal representations; with fixed precision, positional encodings have finite range and the resulting Transformer is not Turing complete.The fixed-precision case is reduced to a Transformer over an enlarged finite input alphabet.

4 NEURAL GPUS

The Neural GPU combines gated convolutions over tensors with a seq-to-seq interpretation, and uniform Neural GPUs are Turing complete. The result depends on specific architectural choices, including kernel extent, padding, and gating.

  • Architecture: Neural GPUs combine convolutions and gated recurrences over tridimensional tensors, with update, reset, and transformation functions applied recursively.The state update uses element-wise gating, while these functions are implemented with convolutions, biases, and point-wise transformations.
  • Architecture: The convolution treats the tensor as a grid of vector-valued cells updated from neighboring cells, making the architecture similar to a cellular automaton.Zero-padding is used outside the tensor boundaries.
  • Seq-to-seq formulation: Neural GPUs can be cast as seq-to-seq recognizers by placing input vectors in the first tensor column and reading outputs from a designated cell.The construction uses a fixed tensor width and selects the last cell of the first column as the output location.
  • Turing completeness: Uniform Neural GPUs have a constant number of parameters independent of input length, enabling the completeness theorem for a finitely specified architecture.Uniformity requires each bias tensor to repeat the same matrix across the input-length dimension.
  • Turing completeness: The completeness proof simulates an RNN encoder-decoder by sequentially updating encoder and decoder cells with gated convolutional operations.The construction uses a kernel shape of (2, 1, 3d + 3, 3d + 3) and keeps decoder updates one iteration behind encoder updates.
  • Architectural boundaries: Kernel shape (1, 1, d, d) is insufficient for Turing completeness because each cell then depends only on its own previous value.The proof instead uses kernels of shape (2, 1, d, d).
  • Architectural boundaries: Uniform Neural GPUs with circular convolutions are not Turing complete because they cannot distinguish periodic sequences of different lengths.Zero padding lets the construction distinguish internal cells from sequence endpoints; circular convolution removes that distinction.
  • Architectural boundaries: Neural GPUs that solve difficult problems can still struggle on highly symmetric, nearly periodic inputs, including repeated-one multiplication examples.The paper leaves the relationship between this empirical behavior and its theoretical result for future work.

5 FINAL REMARKS AND FUTURE WORK

The paper establishes theoretical completeness results for the Transformer and Neural GPU while identifying architectural and numerical assumptions that remain to be tested or relaxed. It also points to possible practical implications and several directions for future work.

  • Conclusions: The analysis covers the Transformer and Neural GPU, with completeness proofs relying on residual connections in the former and gating in the latter.The authors plan to investigate whether these features are essential.
  • Scope and assumptions: The proofs use abstract architectural variants, notably hard attention for the Transformer and piecewise linear activations for both architectures.More experimentation is needed to determine the practical implications of these Transformer choices.
  • Practical implications: The theoretical results may inform practical analyses because Turing completeness has been linked to undecidability of some probabilistic language-modeling problems.Such problems can therefore be approached in practice through heuristic solutions, according to the cited RNN work.
  • Limitations and future work: The results assume internal representations can be computed with arbitrary precision, leaving finite-precision analysis as future work.The paper identifies finite-precision studies of RNNs as a precedent for this direction.

A.1 PROOF OF THEOREM 2.3

The proof of RNN Turing completeness encodes input strings as rational-valued internal states, uses affine transformations and threshold activations for stack operations, and combines encoder and decoder networks to simulate a two-stack machine.

  • String encoding: The construction first encodes a binary input string as a rational number stored in an RNN’s internal state.The encoding uses base 4, placing every finite binary string between 0 and 1.
  • Stack simulation: Stack operations can be simulated by affine transformations followed by threshold activation; for example, top(w) is computed as y = σ(4x_w − 2).The activation returns 1 exactly when the top bit is 1 and 0 when it is 0.
  • Machine simulation: A second network simulates the two-stack machine while receiving zero inputs for the required number of computation steps.To run for r steps, the input includes a sequence of r zeros.
  • Encoder-decoder construction: The combined network uses an input format whose components carry the string bits, an activity indicator, and a marker for the first inactive step.The first phase runs the encoder, after which the inactive marker initiates the simulation phase.
  • Encoder-decoder construction: The construction can be recast as an encoder-decoder RNN with a language recognizer that detects acceptance through a designated decoder neuron.The encoder network becomes N1, the decoder becomes N2, and the output neuron is activated upon reaching an accepting state.
  • Complexity: The basic construction uses 10m + 30 neurons to simulate a machine with m states, with a constant-factor slowdown.A refinement described by Siegelmann and Sontag achieves real-time simulation instead.

B.1 PROOF OF PROPOSITION 3.1

The proof shows that Transformer computations are invariant under sequences preserving the same values and relative proportions, because attention and decoder steps depend only on corresponding transformed representations.

  • Proposition setup: PropInv groups sequences that contain the same vectors with identical relative proportions.The definition requires equal value sets and equal normalized occurrence counts for every vector.
  • Encoder invariance: The proof compares two sequences X and X′ in PropInv(X), together with their encoded sequences Z and Z′.The encoder outputs are analyzed position by position for corresponding occurrences of equal input vectors.
  • Attention invariance: Equal input vectors receive corresponding equal attention contributions after the encoder, establishing the key local invariance property.The argument uses the residual form z_i = O(a_i) + a_i and reduces equality to matching attention outputs.
  • Proposition setup: The resulting attention outputs are equal for the two encoded sequences, completing the proof of the intermediate invariance property.The equality is stated explicitly after the corresponding key and value contributions are matched.
  • Attention invariance: The encoder induces mappings from input values to corresponding key and value vectors, allowing attention outputs to be compared by value counts rather than positions.Mappings M_K and M_V preserve the correspondence between repeated values in the two sequences.
  • Decoder invariance: Decoder computations preserve the same invariance because each step accesses the encoder only through attention and can therefore be handled inductively.The first decoder step follows from equal attention outputs, and subsequent steps follow by induction on k.

B.2 PROOF OF COROLLARY 3.2

The proof derives a contradiction by showing that a Transformer recognizer must give the same answer to two strings that the target language separates.

  • w1 = aabb belongs to PropInv(w2) for w2 = aaabbb, so the recognizer must accept w1 if and only if it accepts w2.

B.3 PROOF OF PROPOSITION 3.3

The proof constructs a Transformer recognizer whose decoder maintains the simulated machine’s state, scanned symbol, and movement history, then derives the next configuration inductively. Attention retrieves input symbols and previously written tape information, enabling simulation of a Turing machine.

  • Inductive simulation: The construction proceeds by induction, producing each next decoder vector from prior vectors and thereby simulating the complete execution of the machine.The initial vector encodes the initial state and blank symbol; each subsequent vector encodes the next configuration.
  • Encoder and decoder construction: The construction represents each input symbol and position with encoder keys and values, allowing the decoder to retrieve specific input symbols.Keys encode positional information, while values encode the corresponding input symbols.
  • Encoder and decoder construction: At each time step, the decoder stores the machine state, scanned symbol, written symbol, and head direction needed to reconstruct its computation history.The output sequence encodes q(i), s(i), v(i), and m(i) across successive decoder steps.
  • Inductive simulation: A two-layer feed-forward network mimics the Turing machine transition function, producing the next state, written symbol, and head movement from the current state and scanned symbol.The transition computation supplies q(i+1), v(i), and m(i), while attention supplies the relevant tape symbol.
  • Inductive simulation: The scanned symbol is determined from the input or from the most recent symbol written at the current tape position, with blanks used for untouched cells.The proof separates input-reading, never-written, and previously visited tape positions.

B.4.2 DETAILS OF THE ARCHITECTURE OF TransM

The TransM architecture combines positional encodings, hard attention, residual connections, and feed-forward transformations to generate a sequence encoding a simulated Turing-machine execution. Its attention mechanism retrieves input information by position and handles ties by averaging value vectors.

  • Attention mechanism: Hard attention selects the value whose key maximizes the scoring function, while tied maxima produce the average of the corresponding value vectors.The proof uses both unique selection and averaging behavior.
  • Embeddings and positional encodings: TransM uses one-hot symbol embeddings combined with positional encodings containing 1, i, 1/i, and 1/i^2.The resulting vectors are the encoder inputs for the simulated machine.
  • Encoder architecture: The encoder produces keys containing positions and values containing symbols, using a single layer with trivial self-attention, residual connections, and linear transformations.This representation supports position-specific retrieval by decoder attention.
  • Decoder architecture: Decoder vectors encode the machine state, scanned symbol, and previous head direction, beginning from an initial vector containing qinit and the blank symbol.Positional encodings are added to every decoder vector before attention is applied.
  • Decoder architecture: The first decoder layer retrieves the relevant encoder information and uses a two-layer feed-forward network to compute the next state, written symbol, and movement direction.Residual connections preserve the current decoder representation while attention adds position-specific input data.
  • Decoder architecture: Two additional decoder layers aggregate movement information and use attention to recover the tape symbol needed for the next simulated step.The construction first obtains the relevant cell position and then retrieves the associated symbol.

B.4.3 DETAILED PROOFS OF INTERMEDIATE LEMMAS

The intermediate lemmas establish that feed-forward networks and attention can implement the discrete transformations required by TransM. These transformations recover state-symbol pairs, apply the transition function, aggregate head movements, and select the symbol at the next tape position.

  • Tape-position recovery: A third attention construction selects the most recent time associated with the next tape position and returns the symbol written there.The selected index is the last visit to the relevant cell, allowing the decoder to reconstruct the scanned symbol.
  • Intermediate transformations: One-hot state-symbol pairs can be constructed from separate one-hot state and symbol vectors using an affine transformation followed by a piecewise-linear activation.The resulting vector has a one at the coordinate representing the pair and nonpositive values elsewhere.
  • Intermediate transformations: A matrix transformation maps the one-hot representation of a state-symbol pair to the one-hot representation of the Turing-machine transition output.This output encodes the next state, written symbol, and movement direction.
  • Intermediate transformations: A further linear transformation extracts the state, symbol, and movement components from the transition representation.Together, these transformations implement the transition computation used by the decoder.
  • Feed-forward implementation: The composed construction uses one nonlinearity and otherwise affine transformations, so the required transition module is implementable by a two-layer feed-forward network.The intermediate functions convert the current configuration into the next state, written symbol, and movement data.
  • Tape-position recovery: Uniform attention over decoder history computes normalized cumulative head movements, yielding representations of the current and next tape-cell positions.The averages encode c(i) and c(i+1) after summing movement directions.

C.1 PROOF OF THEOREM 4.1

The construction builds a Neural GPU that simulates an RNN encoder-decoder by organizing tensor components and gates to reproduce the RNN’s sequential computation. The proof establishes this simulation inductively and concludes that the decoder behavior is recovered.

  • Construction: The Neural GPU construction simulates an RNN encoder-decoder by transforming an input sequence into an augmented tensor representation.The augmented vectors include the original encoding, zero blocks, and three additional gate-control components.
  • Construction: The Neural GPU update uses convolutional kernel banks, biases, and piecewise-linear gates to implement the required update, reset, and candidate transformations.The kernel banks KU, KR, and KF are defined as block matrices, while the biases are set to zero and the gates use σ.
  • Correctness: An induction over time proves that each tensor position maintains the required encoder, intermediate, and decoder states relative to the simulated RNN.The proof computes the U, R, and F updates and verifies that the resulting tensor satisfies the target invariant at every step.
  • Construction: The tensor channels are partitioned to represent the encoder, encoder-decoder communication, decoder, and sequential-control gadgets.The construction uses the first d, next d, and next d components for these computational roles, with three final components controlling sequential reading and hidden-state behavior.
  • Correctness: The construction recovers the RNN decoder state and therefore simulates the complete network N with a Neural GPU.The proof identifies the relevant output slice as the decoder part of the RNN.

C.2 PROOF OF PROPOSITION 4.2

The proposition shows that uniform Neural GPUs preserve periodicity through circular convolutions and recurrent updates. Consequently, they cannot recognize input length for periodic inputs, including the language of all even-length strings.

  • Periodicity preservation: Circular convolution preserves a tensor’s period when the input is periodic along its first dimension.The convolution output at position i equals the output at position i+p when the input has period p.
  • Periodicity preservation: Induction over Neural GPU updates shows that every subsequent tensor state remains periodic with the same period.The argument applies the periodicity property to the update, reset, and candidate computations at each time step.
  • Limitation: Uniform Neural GPUs cannot recognize the length of periodic inputs, so they cannot recognize all even-length strings.For an odd-period string u, the inputs uu and uuu have different parity but produce the same output under the periodicity argument, yielding a contradiction.
Loading 1901.03429v1…