On the Turing Completeness of Modern Neural Network Architectures

Introduction

There is an increasing interest in designing neural network architectures capable of learning algorithms from examples (Graves et al., 2014; Grefenstette et al., 2015; Joulin & Mikolov, 2015; Kaiser & Sutskever, 2016; Kurach et al., 2016; Dehghani et al., 2018). A key requirement for any such an architecture is thus to have the capacity of implementing arbitrary algorithms, that is, to be Turing complete. Turing completeness often follows for these networks as they can be seen as a control unit with access to an unbounded memory; as such, they are capable of simulating any Turing machine.

On the other hand, the work by Siegelmann & Sontag (1995) has established a different way of looking at the Turing completeness of neural networks. In particular, their work establishes that recurrent neural networks (RNNs) are Turing complete even if only a bounded number of resources (i.e., neurons and weights) is allowed. This is based on two conditions: (1) the ability of RNNs to compute internal dense representations of the data, and (2) the mechanisms they use for accessing such representations. Hence, the view proposed by Siegelmann & Sontag shows that it is possible to release the full computational power of RNNs without arbitrarily increasing its model complexity.

Most of the early neural architectures proposed for learning algorithms correspond to extensions of RNNs – e.g., Neural Turing Machines (Graves et al., 2014) –, and hence they are Turing complete in the sense of Siegelmann & Sontag. However, a recent trend has shown the benefits of designing networks that manipulate sequences but do not directly apply a recurrence to sequentially process their input symbols. Architectures based on attention or convolutions are two prominent examples of this approach. In this work we look at the problem of Turing completeness à la Siegelmann & Sontag for two of the most paradigmatic models exemplifying these features: the Transformer (Vaswani et al., 2017) and the Neural GPU (Kaiser & Sutskever, 2016).

The main contribution of our paper is to show that the Transformer and the Neural GPU are Turing complete 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 additional memory to become Turing complete. Thus the completeness holds for bounded architectures (bounded number of neurons and parameters). To prove this we assume that internal activations are represented as rational numbers with arbitrary precision. For the case of the Transformer we provide a direct simulation of a Turing machine, while for the case of the Neural GPU our result follows by simulating standard sequence-to-sequence RNNs. Our study also reveals some minimal sets of elements needed to obtain these completeness results. The computational power of Transformers and of Neural GPUs has been compared in the current literature (Dehghani et al., 2018), but both are only informally used. Our paper provides a formal way of approaching this comparison.

For the sake of space, we only include sketch of some proofs in the body of the paper. The details for every proof can be found in the appendix.

The study of the computational power of neural networks can be traced back to McCulloch & Pitts (1943) which established an analogy between neurons with hard-threshold activations and first order logic sentences, and Kleene (1956) that draw a connection between neural networks and finite automata. As mentioned earlier, the first work showing the Turing completeness of finite neural networks with linear connections was carried out by Siegelmann & Sontag (1992; 1995). Since being Turing complete does not ensure the ability to actually learn algorithms in practice, there has been an increasing interest in enhancing RNNs with mechanisms for supporting this task. One strategy has been the addition of inductive biases in the form of external memory, being the Neural Turing Machine (NTM) (Graves et al., 2014) a paradigmatic example. To ensure that NTMs are differentiable, their memory is accessed via a soft attention mechanism (Bahdanau et al., 2014). Other examples of architectures that extend RNNs with memory are the Stack-RNN (Joulin & Mikolov, 2015), and the (De)Queue-RNNs (Grefenstette et al., 2015). By Siegelmann & Sontag’s results, all these architectures are Turing complete.

The Transformer architecture (Vaswani et al., 2017) is almost exclusively based on the attention mechanism, and it has achieved state of the art results on many language-processing tasks. While not initially designed to learn general algorithms, Dehghani et al. (2018) have advocated the need for enriching its architecture with several new features as a way to learn general procedures in practice. This enrichment is motivated by the empirical observation that the original Transformer architecture struggles to generalize to input of lengths not seen during training. We, in contrast, show that the original Transformer architecture is Turing complete, based on different considerations. These results do not contradict each other, but show the differences that may arise between theory and practice. For instance, Dehghani et al. (2018) assume fixed precision, while we allow arbitrary internal precision during computation. We think that both approaches can be complementary as our theoretical results can shed light on what are the intricacies of the original architecture, which aspects of it are candidates for change or improvement, and which others are strictly needed. For instance, our proof uses hard attention while the Transformer is often trained with soft attention (Vaswani et al., 2017). See Section 3.3 for a discussion on these differences.

The Neural GPU is an architecture that mixes convolutions and gated recurrences over tridimensional tensors. It has been shown that NeuralGPUs are powerful enough to learn decimal multiplication from examples (Freivalds & Liepins, 2018), being the first neural architecture capable of solving this problem end-to-end. The similarity of Neural GPUs and cellular automata has been used as an argument to state the Turing completeness of the architecture (Kaiser & Sutskever, 2016; Price et al., 2016). Cellular automata are Turing complete (Smith III, 1971; Ollinger, 2012) and their completeness is established assuming an unbounded number of cells. In the Neural GPU architecture, in contrast, the number of cells that can be used during a computation is proportional to the size of the input sequence (Kaiser & Sutskever, 2016). One can cope with the need for more cells by padding the Neural GPU input with additional (dummy) symbols, as much as needed for a particular computation. Nevertheless, this is only a partial solution, as for a Turing-complete model of computation, one cannot decide a priori how much memory is needed to solve a particular problem. Our results in this paper are somehow orthogonal to the previous argument; we show that one can leverage the dense representations of the Neural GPU cells to obtain Turing completeness without requiring to add cells beyond the ones used to store the input.

Preliminaries

Finally, a class $\mathcal{N}$ of seq-to-seq neural network architectures defines the class $\mathcal{L}_{\mathcal{N}}$ composed of all the languages accepted by language recognizers that use networks in $\mathcal{N}$. From these notions, the formalization of Turing completeness of a class $\mathcal{N}$ naturally follows.

A class $\mathcal{N}$ of seq-to-seq neural network architectures is Turing Complete if $\mathcal{L}_{\mathcal{N}}$ is exactly the class of languages recognized by Turing machines.

where ${\bm{V}},{\bm{W}},{\bm{U}},{\bm{R}}$ are matrices, ${\bm{b}}_{1}$ and ${\bm{b}}_{2}$ are vectors, $O(\cdot)$ is an output function, and $f_{1}$ and $f_{2}$ are activations functions. Equation (2) is called the RNN-encoder and (3) the RNN-decoder.

The next Theorem follows by inspection of the proof by Siegelmann & Sontag (1992; 1995) after adapting it to our formalization of encoder-decoder RNNs.

The class of encoder-decoder RNNs is Turing complete. Turing completeness holds even if we restrict to the class in which ${\bm{R}}$ is the zero matrix, ${\bm{b}}_{1}$ and ${\bm{b}}_{2}$ are the zero vector, $O(\cdot)$ is the identity function, and $f_{1}$ and $f_{2}$ are the piecewise-linear sigmoidal activation $\sigma$.

The Transformer architecture

In this section we present a formalization of the Transformer architecture (Vaswani et al., 2017), abstracting away from specific choices of functions and parameters. Our formalization is not meant to produce an efficient implementation of the Transformer, but to provide a simple setting over which its mathematical properties can be established in a formal way.

In practice $Q(\cdot)$, $K(\cdot)$, $V(\cdot)$ are typically matrix multiplications, and $O(\cdot)$ a feed-forward network. The $+\ {\bm{x}}_{i}$ and $+\ {\bm{a}}_{i}$ summands are usually called residual connections (He et al., 2016a; b). When the particular functions used as parameters are not important, we simply write ${\bm{Z}}=\operatorname{Enc}({\bm{X}})$.

We use $({\bm{K}},{\bm{V}})=\operatorname{TEnc}_{L}({\bm{X}})$ to denote an $L$-layer Transformer encoder over the sequence ${\bm{X}}$.

A single-layer decoder is similar to a single-layer encoder but with additional attention to an external pair of key-value vectors $({{\bm{K}}}^{\textbf{e}},{{\bm{V}}}^{\textbf{e}})$. The input for the single-layer decoder is a sequence ${\bm{Y}}=({\bm{y}}_{1},\ldots,{\bm{y}}_{k})$ plus the external pair $({{\bm{K}}}^{\textbf{e}},{{\bm{V}}}^{\textbf{e}})$, and the output is a sequence ${\bm{Z}}=({\bm{z}}_{1},\ldots,{\bm{z}}_{k})$. When defining a decoder layer we denote by ${\bm{Y}}_{j}$ the sequence $({\bm{y}}_{1},\ldots,{\bm{y}}_{j})$, for $1\leq j\leq k$. The layer is also parameterized by four functions $Q(\cdot)$, $K(\cdot)$, $V(\cdot)$ and $O(\cdot)$ and is defined as follows.

Notice that the first (self) attention over $(K({\bm{Y}}_{i}),V({\bm{Y}}_{i}))$ considers the subsequence of ${\bm{Y}}$ only until index $i$ and is used to generate a query ${\bm{p}}_{i}$ to attend the external pair $({{\bm{K}}}^{\textbf{e}},{{\bm{V}}}^{\textbf{e}})$. We denote the single-decoder layer by $\operatorname{Dec}(({{\bm{K}}}^{\textbf{e}},{{\bm{V}}}^{\textbf{e}}),{\bm{Y}};{\bm{\theta}})$.

We use ${\bm{z}}=\operatorname{TDec}_{L}(({{\bm{K}}}^{\textbf{e}},{{\bm{V}}}^{\textbf{e}}),{\bm{Y}})$ to denote an $L$-layer Transformer decoder.

We denote the output sequence of the transformer as ${\bm{Y}}=({\bm{y}}_{1},{\bm{y}}_{2},\ldots,{\bm{y}}_{r})=\operatorname{Trans}({\bm{X}},{\bm{y}}_{0},r)$.

1 Invariance under proportions

The Transformer, as defined above, is order-invariant: two input sequences that are permutations of each other produce exactly the same output. This is a consequence of the following property of the attention function: if ${\bm{K}}=({\bm{k}}_{1},\ldots,{\bm{k}}_{n})$, ${\bm{V}}=({\bm{v}}_{1},\ldots,{\bm{v}}_{n})$, and $\pi:\{1,\dots,n\}\to\{1,\dots,n\}$ is a permutation, then $\operatorname{Att}({\bm{q}},{\bm{K}},{\bm{V}})=\operatorname{Att}({\bm{q}},\pi({\bm{K}}),\pi({\bm{V}}))$ for every query ${\bm{q}}$. This weakness has motivated the need for including information about the order of the input sequence by other means; in particular, this is often achieved by using the so-called positional encodings (Vaswani et al., 2017; Shaw et al., 2018), which we study below.

But before going into positional encodings, a natural question is what languages the Transformer can recognize without them. As a standard yardstick we use the well-studied class of regular languages, i.e., languages recognized by finite automata. Order-invariance implies that not every regular language can be recognized by a Transformer network. As an example, there is no Transformer network that can recognize the regular language $(ab)^{*}$, as the latter is not order-invariant. A reasonable question then is whether the Transformer can express all regular languages which are order-invariant. It is possible to show that this is not the case by proving that the Transformer actually satisfies a stronger invariance property, which we call proportion invariance.

For a string $w\in\Sigma^{*}$ and a symbol $a\in\Sigma$, we use $\operatorname{prop}(a,w)$ to denote the ratio between the number of times that $a$ appears in $w$ and the length of $w$. Consider now the set $\operatorname{PropInv}(w)=\{u\in\Sigma^{*}\mid\operatorname{prop}(a,{w})=\operatorname{prop}({a},{u})\text{ for every }a\in\Sigma\}$.

As an immediate corollary we obtain the following.

Consider the order-invariant regular language $L=\{w\in\{a,b\}^{*}\mid$ $w$ has an even number of $a$ symbols$\}$. Then $L$ cannot be recognized by a Transformer network.

On the other hand, languages recognized by Transformer networks are not necessarily regular.

There is a Transformer network that recognizes the non-regular language $S=\{w\in\{a,b\}^{*}\mid$ $w$ has strictly more symbols $a$ than symbols $b\}$.

That is, the computational power of Transformer networks without positional encoding is both rather weak (they do not even contain order-invariant regular languages) and not so easy to capture (as they can express counting properties that go beyond regularity). As we show in the next section, the inclusion of positional encodings radically changes the picture.

2 Positional Encodings and Completeness of the Transformer

to the Transformer encoder. Similarly, the Transformer decoder instead of receiving the sequence ${\bm{Y}}=({\bm{y}}_{0},{\bm{y}}_{1},\ldots,{\bm{y}}_{t})$ as input, it receives now the sequence

As for the case of the embedding functions, we require the positional encoding $\operatorname{pos}(i)$ to be computable by a Turing machine working in linear time w.r.t. the size (in bits) of $i$.

The main result of this section is the completeness of Transformers with positional encodings.

The class of Transformer networks with positional encodings is Turing complete.

We show that for every Turing machine $M=(Q,\Sigma,\delta,q_{\text{init}},F)$ there exists a transformer that simulates the complete execution of $M$. We represent a string $w=s_{1}s_{2}\cdots s_{n}\in\Sigma^{*}$ as a sequence ${\bm{X}}$ of one-hot vectors with their corresponding positional encodings. Denote by $q^{(t)}\in Q$ the state of $M$ at time $t$ when processing $w$, and $s^{(t)}\in\Sigma$ the symbol under $M$’s head at time $t$. Similarly, $v^{(t)}\in\Sigma$ is the symbol written by $M$ and $m^{(t)}\in\{\leftarrow,\to\}$ the head direction. We next describe how to construct a transformer $\operatorname{Trans}_{M}$ that with input ${\bm{X}}$ produces a sequence ${\bm{y}}_{0},{\bm{y}}_{1},{\bm{y}}_{2},\ldots$ such that ${\bm{y}}_{i}$ contains information about $q^{(i)}$ and $s^{(i)}$ (encoded as one-hot vectors).

The construction and proof goes by induction. Assume the decoder receives ${\bm{y}}_{0},\ldots,{\bm{y}}_{t}$ such that ${\bm{y}}_{i}$ contains $q^{(i)}$ and $s^{(i)}$. To construct ${\bm{y}}_{t+1}$, in the first layer we just implement $M$’s transition function $\delta$; note that $\delta(q^{(i)},s^{(i)})=(q^{(i+1)},v^{(i)},m^{(i)})$ thus, we use $(q^{(i)},s^{(i)})$ to compute $(q^{(i+1)},v^{(i)},m^{(i)})$ for every $i$ and store them in the sequence ${\bm{z}}_{0}^{1},\ldots,{\bm{z}}_{t}^{1}$. This computation can be done with a two-layer feed-forward network. For the next layer, lets denote by $c^{(i)}$ the index of the cell that $M$ is pointing to at time $i$. It can be proved that given ${\bm{z}}_{0}^{1},\ldots,{\bm{z}}_{t}^{1}$ one can compute (a representation of) $c^{(i)}$ and $c^{(i+1)}$ for every $i\leq t$ with a self-attention layer, and store them in ${\bm{z}}_{0}^{2},\ldots,{\bm{z}}_{t}^{2}$. In particular, ${\bm{z}}_{t}^{2}$ contains $c^{(t+1)}$ which is the index to which $M$ is going to be pointing to in the next time step. By using the residual connections we also store $q^{(i+1)}$ and $v^{(i)}$ in ${\bm{z}}_{i}^{2}$. The final piece of our construction is to compute the symbol that the tape holds at index $c^{(t+1)}$, that is, the symbol under $M$’s head at time $t+1$. For this we use the following observation: the symbol at index $c^{(t+1)}$ in time $t+1$ coincides with the last symbol written by $M$ at index $c^{(t+1)}$. Thus, we need to find the maximum value $i^{\star}\leq t$ such that $c^{(i^{\star})}=c^{(t+1)}$ and then copy $v^{(i^{\star})}$ which is the symbol that was written by $M$ at time step $i^{\star}$. This last computation can also be done with a self-attention layer. Thus, we attend directly to position $i^{\star}$ (hard attention plus positional encodings) and copy $v^{(i^{\star})}$ which is exactly $s^{(t+1)}$. We finally copy $q^{(t+1)}$ and $s^{(t+1)}$ into the output to construct ${\bm{y}}_{t+1}$. Figure 1 shows a high-level diagram of the decoder computation.

There are several other details in the construction, in particular, at the beginning of the computation (first $n$ steps), the decoder needs to attend to the encoder and copy the input symbols so they can later be processed as described above. Another detail is when $M$ reaches a cell that has not been visited before, then the symbol under the head has to be set as $\#$ (the blank symbol). We show that all these decisions can be implemented with feed-forward networks plus attention. The complete construction uses one encoder layer, three decoder layers and vectors of dimension $d=2|Q|+4|\Sigma|+11$ to store one-hot representations of states, symbols and some additional working space. All details can be found in the appendix. ∎

3 Differences with Vaswani et al. (2017)’s framework

Neural GPUs

where $\odot$ denotes the element-wise product, and $\bm{\mathsfit{1}}$ is a tensor with only $1$’s. Neural GPUs force functions $U(\cdot)$ and $R(\cdot)$ to produce a tensor of the same shape as its input with all values in $$. Thus, a Neural GPU resembles a gated recurrent unit (Cho et al., 2014), with${\bm{\mathsfit{U}}}$working as the update gate and${\bm{\mathsfit{R}}}$as the reset gate. Functions$U(\cdot)$,$R(\cdot)$, and$F(\cdot)$are defined as a convolution of its input with a 4-dimensional kernel bank with shape$(k_{H},k_{W},d,d)$ plus a bias tensor, followed by a point-wise transformation

with different kernels and biases for $U(\cdot)$, $R(\cdot)$, and $F(\cdot)$.

To have an intuition on how the convolution ${\bm{\mathsfit{K}}}*{\bm{\mathsfit{S}}}$ works, it is illustrative to think of ${\bm{\mathsfit{S}}}$ as an $(h\times w)$-grid of (row) vectors and ${\bm{\mathsfit{K}}}$ as a $(k_{H}\times k_{W})$-grid of $(d\times d)$ matrices. More specifically, let ${\bm{s}}_{ij}={\bm{\mathsfit{S}}}_{i,j,:}$, and ${\bm{K}}_{ij}={\bm{\mathsfit{K}}}_{i,j,:,:}$, then ${\bm{\mathsfit{K}}}*{\bm{\mathsfit{S}}}$ is a regular two-dimensional convolution in which scalar multiplication has been replaced by vector-matrix multiplication as in the following expression

where $\Delta_{1}(u)=u-\lfloor{k_{H}/2}\rfloor-1$ and $\Delta_{2}(v)=v-\lfloor{k_{W}/2}\rfloor-1$. This intuition makes evident the similarity between Neural GPUs and cellular automata: ${\bm{\mathsfit{S}}}$ is a grid of cells, and in every iteration each cell is updated considering the values of its neighbors according to a fixed rule given by ${\bm{\mathsfit{K}}}$ (Kaiser & Sutskever, 2016). As customary, we assume zero-padding when convolving outside ${\bm{\mathsfit{S}}}$.

The class of uniform Neural GPUs is Turing complete.

The proof above makes use of kernels of shape $(2,1,d,d)$ to obtain Turing completeness. This is, in a sense, optimal, as one can easily prove that Neural GPUs with kernels of shape $(1,1,d,d)$ are not Turing complete, regardless of the size of $d$. In fact, for kernels of this shape the value of a cell of ${\bm{\mathsfit{S}}}$ at time $t$ depends only on the value of the same cell in time $t-1$.

Uniform Neural GPUs with circular convolutions are not Turing complete.

Related to this last result is the empirical observation by Price et al. (2016) that Neural GPUs that learn to solve hard problems, e.g., binary multiplication, and which generalize to most of the inputs, struggle with highly symmetric (and nearly periodic) inputs. Actually, Price et al. (2016) exhibit examples of the form $11111111\times 11111111$ failing for all inputs with eight or more $1$s. We leave as future work to explore the implications of our theoretical results on this practical observation.

Freivalds & Liepins (2018) simplified Neural GPUs and proved that, by considering piecewise linear activations and bidimensional input tensors instead of the original smooth activations and tridimensional tensors used by Kaiser & Sutskever (2016), it is possible to achieve substantially better results in terms of training time and generalization. Our Turing completeness proof also relies on a bidimensional tensor and uses piecewise linear activations, thus providing theoretical evidence that these simplifications actually retain the full expressiveness of Neural GPUs while simplifying its practical applicability.

Final Remarks and Future Work

We have presented an analysis of the Turing completeness of two popular neural architectures for sequence-processing tasks; namely, the Transformer, based on attention, and the Neural GPU, based on recurrent convolutions. We plan to further refine this analysis in the future. For example, our proof of Turing completeness for the Transformer requires the presence of residual connections, i.e., the $+{\bm{x}}_{i}$, $+{\bm{a}}_{i}$, $+{\bm{y}}_{i}$, and $+{\bm{p}}_{i}$ summands in Equations (6-11), while our proof for Neural GPUs heavily relies on the gating mechanism. We will study whether these features are actually essential to obtain completeness.

We presented general abstract versions of both architectures in order to prove our theoretical results. Although we closely follow their original definitions, some choices for functions and parameters in our positive results are different to the usual choices in practice, most notably, the use of hard attention for the case of the Transformer, and the piecewise linear activation functions for both architectures. As we have mentioned, Freivalds & Liepins (2018) showed that for Neural GPUs piecewise linear activations actually help in practice, but for the case of the Transformer architecture more experimentation is needed to have a conclusive response. This is part of our future work.

Although our results are mostly of theoretical interest, they might lead to observations of practical interest. For example, Chen et al. (2018) have established the undecidability of several practical problems related to probabilistic language modeling with RNNs. This means that such problems can only be approached in practice via heuristics solutions. Many of the results in Chen et al. (2018) are, in fact, a consequence of the Turing completeness of RNNs as established by Siegelmann & Sontag (1995). We plan to study to what extent our analogous undecidability results for Transformers and Neural GPUs imply undecidability for language modeling problems based on these architectures.

Finally, our results rely on being able to compute internal representations of arbitrary precision. It would be interesting to perform a theoretical study of the main properties of both architectures in a setting in which only finite precision is allowed, as have been recently carried out for RNNs (Weiss et al., 2018). We also plan to tackle this problem in our future work.

This work was supported by the Millennium Institute for Foundational Research on Data (IMFD).

References

Appendix A Proofs for Section 2

We first sketch the main idea of Siegelmann & Sontag’s proof. We refer the reader to the original paper for details. Siegelmann & Sontag show how to simulate a two-stack machine $M$ (and subsequently, a Turing machine) with a single RNN $N$ with $\sigma$ as activation. They first construct a network $N_{1}$ that, with ${\bm{0}}$ as initial state (${\bm{h}}^{N_{1}}_{0}={\bm{0}}$) and with a binary string $w\in\{0,1\}^{*}$ as input sequence, produces a representation of $w$ as a rational number and stores it as one of its internal values. Their internal representation of strings encodes every $w$ as a rational number between and $1$. In particular, they use base $4$ such that, for example, a string $w=100110$ is encoded as $(0.311331)_{4}$ that is, its encoding is

This representation allows one to easily simulate stack operations as affine transformations plus $\sigma$ activations. For instance, if $x_{w}$ is the value representing string $w=b_{1}b_{2}\cdots b_{n}$ seen as a stack, then the $\operatorname{top}(w)$ operation can be defined as simply $y=\sigma(4x_{w}-2)$, since $y=1$ if and only if $b_{1}=1$, and $y=0$ if and only if $b_{1}=0$. Other stack operations can de similarly simulated. Using this representation, they construct a second network $N_{2}$ that simulates the two-stacks machine by using one neuron value to simulate each stack. The input $w$ for the simulated machine $M$ is assumed to be at an internal value given to $N_{2}$ as an initial state $({\bm{h}}_{0}^{N_{2}})$. Thus, $N_{2}$ expects only zeros as input. Actually, to make $N_{2}$ work for $r$ steps, an input of the form $0^{r}$ should be provided.

Finally, they combine $N_{1}$ and $N_{2}$ to construct a network $N$ which expects an input of the following form: $(b_{1},1,0)(b_{2},1,0)\cdots(b_{n},1,0)(0,0,1)(0,0,0)(0,0,0)\cdots(0,0,0)$. The idea is that the first component contains the input string $w=b_{1}b_{2}\cdots b_{n}$, the second component states when the input is active, and the third component is $1$ only when the input is inactive for the first time. Before the input vector $(0,0,1)$ the network $N_{1}$ is working. The input $(0,0,1)$ is used to simulate a change from $N_{1}$ to $N_{2}$, and the rest of input vectors $(0,0,0)$ are provided to continue with $N_{2}$ for as many steps as needed. The number neurons that this construction needs to simulate a machine $M$ with $m$ states, is $10m+30$. The idea presented above allows one to linearly simulate $M$, that is, each step of $M$ is simulated with a constant number of steps of the corresponding RNN. Siegelmann & Sontag show that, with a refinement of the above encoding one can simulate $M$ in real-time, that is, a single step of $M$ is simulated with a single step of the recurrent network. The $10m+30$ is the bound given by a simulation with slow-down of two. See the original paper for details (Siegelmann & Sontag, 1995).

It is clear that Siegelmann & Sontag’s proof resembles a modern encoder-decoder RNN architecture, where $N_{1}$ is the encoder and $N_{2}$ is the decoder, thus it is straightforward to use the same construction to provide an RNN encoder-decoder $N^{\prime}$ and a language recognizer $A$ that uses $N^{\prime}$ and simulates the two-stacks machine $M$. There are some details that is important to notice. Assume that $N^{\prime}$ is given by the formulas in Equations (2) and (3). First, since $N_{2}$ in the above construction expects no input, we can safely assume that ${\bm{R}}$ in Equation (3) is the null matrix. Moreover, since $A$ defines its own embedding function, we can ensure that every vector that we provide for the encoder part of $N^{\prime}$ has a $1$ in a fixed component, and thus we do not need the bias ${\bm{b}}_{1}$ in Equation (2) since it can be simulated with one row of matrix ${\bm{V}}$. We can do a similar construction for the bias ${\bm{b}}_{2}$ (Equation (3)). Finally, Siegelmann & Sontag show that its construction can be modified such that a particular neuron of $N_{2}$, say $n^{\star}$, is always except for the first time an accepting state of $M$ is reached, in which case $n^{\star}=1$. Thus, one can consider $O(\cdot)$ (Equation (3)) as the identity function and add to $A$ the stopping criterion that just checks if $n^{\star}$ is $1$. This completes the proof sketch of Theorem 2.3.

Appendix B Proofs for Section 3

We extend the definition of the function $\operatorname{PropInv}$ to sequences of vectors. Given a sequence ${\bm{X}}=({\bm{x}}_{1},\ldots,{\bm{x}}_{n})$ we use $\operatorname{vals}({\bm{X}})$ to denote the set of all vectors occurring in ${\bm{X}}$. Similarly as for strings, we use $\operatorname{prop}({\bm{v}},{\bm{X}})$ as the number of times that ${\bm{v}}$ occurs in ${\bm{X}}$ divided by the length of ${\bm{X}}$. Now we are ready to extend $\operatorname{PropInv}$ with the following definition:

We now have all the necessary to proceed with the proof of Proposition 3.1. We will prove it by proving the property in (16). Let ${\bm{X}}=({\bm{x}}_{1},\ldots,{\bm{x}}_{n})$ be an arbitrary sequence of vectors, and let ${\bm{X}}^{\prime}=({\bm{x}}^{\prime}_{1},\ldots,{\bm{x}}^{\prime}_{m})\in\operatorname{PropInv}({\bm{X}})$. Moreover, let ${\bm{Z}}=({\bm{z}}_{1},\ldots,{\bm{z}}_{n})=\operatorname{Enc}({\bm{X}};{\bm{\theta}})$ and ${\bm{Z}}^{\prime}=({\bm{z}}^{\prime}_{1},\ldots,{\bm{z}}^{\prime}_{m})=\operatorname{Enc}({\bm{X}}^{\prime};{\bm{\theta}})$. We first prove the following property:

Lets $(i,j)$ be a pair of indices such that ${\bm{x}}_{i}={\bm{x}}_{j}^{\prime}$. From Equations (6-7) we have that ${\bm{z}}_{i}=O({\bm{a}}_{i})+{\bm{a}}_{i}$ where ${\bm{a}}_{i}=\operatorname{Att}(Q({\bm{x}}_{i}),K({\bm{X}}),V({\bm{X}}))+{\bm{x}}_{i}$. Thus, since ${\bm{x}}_{i}={\bm{x}}^{\prime}_{j}$, in order to prove ${\bm{z}}_{i}={\bm{z}}_{j}^{\prime}$ it is enough to prove that $\operatorname{Att}(Q({\bm{x}}_{i}),K({\bm{X}}),V({\bm{X}}))=\operatorname{Att}(Q({\bm{x}}_{j}^{\prime}),K({\bm{X}}^{\prime}),V({\bm{X}}^{\prime}))$. By equations (4-5) and the restriction over the form of normalization functions we have that

with $\alpha=\sum_{{\bm{v}}\in\operatorname{vals}({\bm{X}})}p_{{\bm{v}}}^{{\bm{X}}}f_{\rho}(\operatorname{score}(Q({\bm{v}}),K({\bm{v}})))$. By a similar reasoning we can write

Which completes the proof of Property (17) above.

Consider now the complete encoder $\operatorname{TEnc}$. Let $({\bm{K}},{\bm{V}})=\operatorname{TEnc}({\bm{X}})$ and $({\bm{K}}^{\prime},{\bm{V}}^{\prime})=\operatorname{TEnc}({\bm{X}}^{\prime})$, and let ${\bm{q}}$ be an arbitrary vector. We will prove now that $\operatorname{Att}({\bm{q}},{\bm{K}},{\bm{V}})=\operatorname{Att}({\bm{q}},{\bm{K}}^{\prime},{\bm{V}}^{\prime})$. By following a similar reasoning as for proving Property (17) (plus induction on the layers of $\operatorname{TEnc}$) we obtain that if ${\bm{x}}_{i}={\bm{x}}^{\prime}_{j}$ then ${\bm{k}}_{i}={\bm{k}}^{\prime}_{j}$ and ${\bm{v}}_{i}={\bm{v}}^{\prime}_{j}$, for every $i\in\{1,\ldots,n\}$ and $j\in\{1,\ldots,m\}$. Thus, there exists a mapping $M_{K}:\operatorname{vals}({\bm{X}})\to\operatorname{vals}({\bm{K}})$ such that $M_{K}({\bm{x}}_{i})={\bm{k}}_{i}$ and $M_{K}({\bm{x}}^{\prime}_{j})={\bm{k}}^{\prime}_{j}$ and similarly a mapping $M_{V}:\operatorname{vals}({\bm{X}})\to\operatorname{vals}({\bm{V}})$ such that $M_{V}({\bm{x}}_{i})={\bm{v}}_{i}$ and $M_{V}({\bm{x}}^{\prime}_{j})={\bm{v}}^{\prime}_{j}$, for every $i\in\{1,\ldots,n\}$ and $j\in\{1,\ldots,m\}$. Lets focus now on $\operatorname{Att}({\bm{q}},{\bm{K}},{\bm{V}})$. We have:

with $\alpha=\sum_{i=1}^{n}f_{\rho}(\operatorname{score}({\bm{q}},{\bm{k}}_{i})).$ Similarly as before, we can rewrite this as

with $\alpha=\sum_{{\bm{v}}\in\operatorname{vals}({\bm{X}})}p_{{\bm{v}}}^{{\bm{X}}}f_{\rho}(\operatorname{score}({\bm{q}},M_{K}({\bm{v}}))).$ Similarly for $\operatorname{Att}({\bm{q}},{\bm{K}}^{\prime},{\bm{V}}^{\prime})$ we have

And finally using that ${\bm{X}}^{\prime}\in\operatorname{PropInv}({\bm{X}})$ we obtain

To complete the rest proof, consider $\operatorname{Trans}({\bm{X}},{\bm{y}}_{0},r)$ which is defined by the recursion

To prove that $\operatorname{Trans}({\bm{X}},{\bm{y}}_{0},r)=\operatorname{Trans}({\bm{X}}^{\prime},{\bm{y}}_{0},r)$ we use an inductive argument. We know that

Now $\operatorname{TDec}$ only access $({\bm{K}},{\bm{V}})$ via attentions of the form $\operatorname{Att}({\bm{q}},{\bm{K}},{\bm{V}})$ and for the case of ${\bm{y}}_{1}$ the vector ${\bm{q}}$ can only depend on ${\bm{y}}_{0}$, thus, from $\operatorname{Att}({\bm{q}},{\bm{K}},{\bm{V}})=\operatorname{Att}({\bm{q}},{\bm{K}}^{\prime},{\bm{V}}^{\prime})$ we have that

The rest of the steps follow by a simple induction on $k$.

B.2 Proof of Corollary 3.2

To obtain a contradiction, assume that there is a language recognizer $A$ that uses a Transformer network and such that $L=L(A)$. Now consider the strings $w_{1}=aabb$ and $w_{2}=aaabbb$. Since $w_{1}\in\operatorname{PropInv}(w_{2})$ by Proposition 3.1 we have that $w_{1}\in L(A)$ if and only if $w_{2}\in L(A)$ which is a contradiction since $w_{1}\in L$ but $w_{2}\notin L$. This completes the proof of the corollary.

B.3 Proof of Proposition 3.3

Assume that the output for the encoder part of the transformer is ${\bm{X}}=({\bm{x}}_{1},\ldots,{\bm{x}}_{n})$. First we use an encoder layer that implements the identity function. This can be trivially done using null functions for the self attention and through the residual connections this encoder layer shall preserve the original ${\bm{x}}_{i}$ values. For the final $V(\cdot)$ and $K(\cdot)$ functions of the Transformer encoder (Equation (8)), we use $V({\bm{x}})={\bm{x}}$ the identity function and $K({\bm{x}})=$, giving ${\bm{V}}^{\bm{e}}={\bm{X}}$ and ${\bm{K}}^{\bm{e}}=(,,\ldots,)$.

For the decoder we use a similar approach. We consider the identity in the self attention plus the residual (which can be done by just using the null functions for the self attention). Considering the external attention, that is the attention over $({\bm{K}}^{\bm{e}},{\bm{V}}^{\bm{e}})$, we let $\operatorname{score}$ and $\rho$ be arbitrary scoring and normalization functions. And finally for the function $O(\cdot)$ (Equation (11)) we use a single layer neural network implementing the affine transformation $O([x,y])=[y-x,-y]$ such that $O([x,y])+[x,y]=[y,0]$. The final function $F(\cdot)$ is just the identity function.

In order to complete the proof we introduce some notation. Lets denote by $\#_{a}(w)$ as the number of $a$’s in $w$, and similarly $\#_{b}(w)$ for the number of $b$’s in $w$. Lets call $c_{w}$ as the value $\frac{\#_{a}(w)-\#_{b}(w)}{n}$. We now prove that, for any string $w\in\{a,b\}^{*}$ if we consider $f(w)={\bm{X}}=({\bm{x}}_{1},\ldots,{\bm{x}}_{n})$ as the input sequence for $\operatorname{Trans}$ and we use initial value ${\bm{s}}=$ for the decoder, the complete network shall compute a sequence ${\bm{y}}_{1},{\bm{y}}_{2},\ldots,{\bm{y}}_{r}$ such that:

We proceed by induction. The base case trivially holds since ${\bm{y}}_{0}={\bm{s}}=$. Assume now that we are at step $r$ and the input for the decoder is $({\bm{y}}_{0},{\bm{y}}_{1},\ldots,{\bm{y}}_{r})$. We will show that ${\bm{y}}_{r+1}=[c_{w},0]$. Since we consider the identity in the self attention (Equation (9)), we have that ${\bm{p}}_{i}={\bm{y}}_{i}$ for every $i$ in $\{0,\ldots,i\}$. Now considering the external attention, that is the attention over $({\bm{K}}^{\bm{e}},{\bm{V}}^{\bm{e}})$, Since all key vectors in ${\bm{K}}^{\bm{e}}$ are $$, the external attention will produce the same score value for all positions. That is,$\operatorname{score}({\bm{p}}_{i},{\bm{k}}_{j_{1}})=\operatorname{score}({\bm{p}}_{i},{\bm{k}}_{j_{2}})$for every$j_{1},j_{2}$. Lets call this value$s^{\star}$. Thus we have that

Then, since ${\bm{V}}^{\bm{e}}={\bm{X}}$ we have that

for every $i\in\{0,\ldots,r\}$. The last equality holds since our embedding are $f(a)=$ and $f(b)=$, and so every $a$ in $w$ sums one and every $b$ subtracts one. Thus, we have that

for every $i\in\{0,\ldots,r\}$. In the next step, after the external attention plus the residual connection (Equation (10)) we have

Applying function $O(\cdot)$ plus the residual connection (Equation (11)) we have

Finally, ${\bm{y}}_{r+1}=F({\bm{z}}_{r})={\bm{z}}_{r}=[c_{w},0]$ which is exactly what we wanted to prove.

B.4 Proof of Theorem 3.4

Let $M=(Q,\Sigma,\delta,q_{\text{init}},F)$ be a Turing machine with a infinite tape and assume that the special symbol $\#\in\Sigma$ is used to mark blank positions in the tape. We make the following assumptions about how $M$ works when processing an input string:

$M$ always moves its head either to the left or to the right (it never stays at the same cell).

$M$ begins at state $q_{\text{init}}$ pointing to the cell immediately to the left of the input string.

$M$ never makes a transition to the left of the initial position.

$Q$ has a special state $q_{\text{read}}$ used to read the complete input.

Initially (time ), $M$ makes a transition to state $q_{\text{read}}$ and move its head to the right.

While in state $q_{\text{read}}$ it moves to the right until symbol $\#$ is read.

There are no transitions going out from accepting states (states in $F$).

It is easy to prove that every general Turing machine is equivalent to one that satisfies the above assumptions. We prove that one can construct a transformer network $\operatorname{Trans}_{M}$ that is able to simulate $M$ on every possible input string.

The construction is somehow involved and uses several helping values, sequences and intermediate results. To make the reading more easy we divide the construction and proof in three parts. We first give a high-level view of the strategy we use. Then we give some details on the architecture of the encoder and decoder needed to implement our strategy, and finally we formally prove that every part of our architecture can be actually implemented.

In the encoder part of $\operatorname{Trans}_{M}$ we receive as input the string $w=s_{1}s_{2}\ldots s_{n}$. We first use an embedding function to represent every $s_{i}$ as a one-hot vector and add a positional encoding for every index. The encoder produces output $({\bm{K}}^{\bm{e}},{\bm{V}}^{\bm{e}})$ where ${\bm{K}}^{\bm{e}}=({\bm{k}}^{\bm{e}}_{1},\ldots,{\bm{k}}^{\bm{e}}_{n})$ and ${\bm{V}}^{\bm{e}}=({\bm{v}}^{\bm{e}}_{1},\ldots,{\bm{v}}^{\bm{e}}_{n})$ are sequences of keys and values such that ${\bm{v}}^{\bm{e}}_{i}$ contains the information of $s_{i}$ and ${\bm{k}}^{\bm{e}}_{i}$ contains the information of the $i$-th positional encoding. We later show that this allows us to attend to every specific position and copy every input symbol from the encoder to the decoder (Lemma B.1).

In the decoder part of $\operatorname{Trans}_{M}$ we simulate a complete execution of $M$ over $w=s_{1}s_{2}\cdots s_{n}$. For this we define the following sequences (for $i\geq 0$):

For the case of $m^{(i)}$ we assume that $-1$ represents a movement to the left and $1$ represents a movement to the right. In our construction we show how to build a decoder that computes all the above values for every time step $i$ using self attention plus attention over the encoder part. Since the above values contain all the needed information to reconstruct the complete history of the computation, we can effectively simulate $M$.

In particular our construction produces the sequence of output vectors ${\bm{y}}_{1},{\bm{y}}_{2},\ldots$ such that, for every $i$, the vector ${\bm{y}}_{i}$ contains information about $q^{(i)}$ and $s^{(i)}$ encoded as one-hot vectors. The construction and proof goes by induction. We begin with an initial vector ${\bm{y}}_{0}$ that represents the state of the computation before it has started, that is $q^{(0)}=q_{\text{init}}$ and $s^{(0)}=\#$. For the induction step we assume that we have already computed ${\bm{y}}_{1},\ldots,{\bm{y}}_{r}$ such that ${\bm{y}}_{i}$ contains information about $q^{(i)}$ and $s^{(i)}$, and we show how with input $({\bm{y}}_{0},{\bm{y}}_{1},\ldots,{\bm{y}}_{r})$ the decoder produces the next vector ${\bm{y}}_{r+1}$ containing $q^{(r+1)}$ and $s^{(r+1)}$.

The overview of the construction is as follows. First notice that the transition function $\delta$ relates the above values with the following equation:

We prove that we can use a two-layer feed-forward network to mimic the transition function $\delta$ (Lemma B.2). Thus, given that the input vector ${\bm{y}}_{i}$ contains $q^{(i)}$ and $s^{(i)}$, we can produce the values $q^{(i+1)}$, $v^{(i)}$ and $m^{(i)}$ (and store them as values in the decoder). In particular, since ${\bm{y}}_{r}$ is in the input, we can produce $q^{(r+1)}$ which is part of what we need for ${\bm{y}}_{r+1}$. In order to complete the construction we also need to compute the value $s^{(r+1)}$, that is, we need to compute the symbol under the head of machine $M$ at the next time step (time $r+1$). We next describe at a high level, how this symbol can be computed with two additional decoder layers.

We first make some observations about $s^{(i)}$ that are fundamental in our computation. Assume that at time $i$ the head of $M$ is pointing to the cell at index $k$. Then we have three possibilities:

If $i\leq n$, then $s^{(i)}=s_{i}$ since $M$ is still reading its input string.

If $i>n$ and $M$ has never written at index $k$, then $s^{(i)}=\#$, the blank symbol.

In other case, that is, if $i>n$ and time $i$ is not the first time that $M$ is pointing to index $k$, then $s^{(i)}$ is the last symbol written by $M$ at index $k$.

For the case (1) we can produce $s^{(i)}$ by simply attending to position $i$ in the encoder part. Thus, if $r+1\leq n$ to produce $s^{(r+1)}$ we can just attend to index $r+1$ in the encoder and copy this value to ${\bm{y}}_{r+1}$. For cases (2) and (3) the solution is a bit more complicated, but almost all the important work is to compute what is the index that $M$ is going to be pointing to in time $r+1$.

Notice that value $c^{(i)}$ satisfies that $c^{(i)}=c^{(i-1)}+m^{(i-1)}$. If we unroll this equation and assuming that $c^{(0)}=0$ we obtain that

Then, at the step $i$ in the decoder we have all the necessary to compute value $c^{(i)}$ but also the necessary to compute $c^{(i+1)}$. We actually show that the computation (of a representation) of $c^{(i)}$ and $c^{(i+1)}$ can be done by using one layer of self attention (Lemma B.3).

We have described at a high-level a decoder that, with input $({\bm{y}}_{0},{\bm{y}}_{1},\ldots,{\bm{y}}_{r})$, computes the values $q^{(r+1)}$ and $s^{(r+1)}$ which is what we need to produce ${\bm{y}}_{r+1}$. We next show all the details of this construction.

In this section we give more details on the architecture of the encoder and decoder needed to implement our strategy. We let several intermediate claims as lemmas that we formally prove in Section B.4.3.

Attention mechanism

For our attention mechanism we use the following non-linear function:

Thus, when computing hard attention with the function $\operatorname{score}_{\varphi}(\cdot)$ we essentially select the vector ${\bm{v}}_{j}$ such that the dot product $\langle{\bm{q}},{\bm{k}}_{j}\rangle$ is as close to as possible. If there is more than one index, say indexes $j_{1},j_{2},\ldots,j_{r}$, that minimizes the dot product $\langle{\bm{q}},{\bm{k}}_{j}\rangle$ then we have that

Thus, in the extreme case in which all dot products are equal $\langle{\bm{q}},{\bm{k}}_{j}\rangle$ for every index $j$, attention behaves just as an average of all value vectors, that is $\operatorname{Att}({\bm{q}},{\bm{K}},{\bm{V}})=\frac{1}{n}\sum_{j=1}^{n}{\bm{v}}_{j}$. We use all these properties of the hard attention in our proof.

Vectors and encodings

Embeddings and positional encodings

Thus, given an input sequence $s_{1}s_{2}\cdots s_{n}\in\Sigma^{*}$, we have that

We denote this last vector by ${{\bm{x}}}_{i}$. That is, if $M$ receives the input string $w=s_{1}s_{2}\cdots s_{n}$, then the input for $\operatorname{Trans}_{M}$ is the sequence $({{\bm{x}}}_{1},{{\bm{x}}}_{2},\ldots,{{\bm{x}}}_{n})$. The need for using a positional encoding having values $1/i$ and $1/i^{2}$ will be clear when we formally prove the correctness of our construction.

We need a final preliminary notion. In the formal construction of $\operatorname{Trans}_{M}$ we also use the following helping sequences:

These are used to identify when $M$ is still reading the input string.

The encoder part of $\operatorname{Trans}_{M}$ is very simple. For $\operatorname{TEnc}_{M}$ we use a single-layer encoder, such that $\operatorname{TEnc}_{M}({{\bm{x}}}_{1},\ldots,{{\bm{x}}}_{n})=({{\bm{K}}}^{\textbf{e}},{{\bm{V}}}^{\textbf{e}})$ where ${{\bm{K}}}^{\textbf{e}}=({\bm{k}}_{1},\ldots,{\bm{k}}_{n})$ and ${{\bm{V}}}^{\textbf{e}}=({{\bm{v}}}_{1},\ldots,{{\bm{v}}}_{n})$ such that

It is straightforward to see that these vectors can be produced with a single encoder layer by using a trivial self attention, taking advantage of the residual connections in Equations (6) and (7), and then using linear transformations for $V(\cdot)$ and $K(\cdot)$ in Equation (8).

When constructing the decoder we use the following property.

We next show how to construct the decoder part of $\operatorname{Trans}_{M}$ to produce the sequence of outputs ${\bm{y}}_{1},{\bm{y}}_{2},\ldots$, where ${\bm{y}}_{i}$ is given by:

That is, ${\bm{y}}_{i}$ contains information about the state of $M$ at time $i$, the symbol under the head of $M$ at time $i$, and the last direction followed by $M$ (the direction of the head movement at time $i-1$). The need to include $m^{(i-1)}$ will be clear in the construction.

We consider as the starting vector for the decoder the vector

We are assuming that $m^{(-1)}=0$ to represent that previous to time there was no head movement. Our construction resembles a proof by induction; we describe the architecture piece by piece and at the same time we show how for every $r\geq 0$ our architecture constructs ${\bm{y}}_{r+1}$ from the previous vectors $({\bm{y}}_{0},\ldots,{\bm{y}}_{r})$.

Thus, assume that ${\bm{y}}_{0},\ldots,{\bm{y}}_{r}$ satisfy the properties stated above. Since we are using positional encodings, the actual input for the first layer of the decoder is the sequence

We denote by $\overline{{\bm{y}}}_{i}$ the vector ${\bm{y}}_{i}$ plus its positional encoding. Thus we have that

For the first self attention in Equation (9) we just produce the identity which can be easily implemented with a trivial attention plus the residual connection. Thus, we produce the sequence of vectors $({\bm{p}}^{1}_{0},{\bm{p}}^{1}_{1},\ldots,{\bm{p}}^{1}_{r})$ such that ${{\bm{p}}}^{1}_{i}=\overline{{\bm{y}}}_{i}$.

Since ${\bm{p}}^{1}_{i}$ is of the form $[\underline{\phantom{A}},\ldots,\underline{\phantom{A}},1,i+1,\underline{\phantom{A}},\underline{\phantom{A}}]$ by Lemma B.1 we know that if we use ${\bm{p}}^{1}_{i}$ to attend over the encoder we obtain

Thus in Equation (10) we finally produce the vector ${\bm{a}}^{1}_{i}$ given by

As the final piece of the first decoder layer we use a function $O_{1}(\cdot)$ (Equation (11)) that satisfies the following lemma.

That is, function $O_{1}(\cdot)$ simulates transition $\delta(q^{(i)},s^{(i)})$ to construct $\llbracket\ q^{(i+1)}\ \rrbracket$, $\llbracket\ v^{(i)}\ \rrbracket$, and $m^{(i)}$ besides some other linear transformations.

We finally produce as the output of the first decoder layer, the sequence $({\bm{z}}^{1}_{0},{\bm{z}}^{1}_{1},\ldots,{\bm{z}}^{1}_{r})$ such that

Notice that ${\bm{z}}^{1}_{r}$ already holds info about $q^{(r+1)}$ and $m^{(r)}$ which we need for constructing vector ${\bm{y}}_{r+1}$. The single piece of information that we still need to construct is $s^{(r+1)}$, that is, the symbol under the head of machine $M$ at the next time step (time $r+1$). We next describe how this symbol can be computed with two additional decoder layers.

Recall that $c^{(i)}$ is the cell to which $M$ is pointing to at time $i$, and that it satisfies that $c^{(i)}=m^{(0)}+m^{(1)}+\cdots+m^{(i-1)}$. We can take advantage of this property to prove the following lemma.

Let ${\bm{Z}}^{1}_{i}=({\bm{z}}^{1}_{0},{\bm{z}}^{1}_{1},\ldots,{\bm{z}}^{1}_{i})$. There exists functions $Q_{2}(\cdot)$, $K_{2}(\cdot)$, and $V_{2}(\cdot)$ defined by feed-forward networks such that

Lemma B.3 essentially shows that one can construct a representation for values $c^{(i)}$ and $c^{(i+1)}$ for every possible index $i$. In particular we will know the value $c^{(r+1)}$ that represents the cell to which the machine is pointing to in the next time step.

Continuing with the decoder layer, when using the self attention above and after adding the residual in Equation (9) we obtain the sequence of vectors $({\bm{p}}^{2}_{0},{\bm{p}}^{2}_{1},\ldots,{\bm{p}}^{2}_{r})$ such that:

From vectors $({\bm{p}}^{2}_{0},{\bm{p}}^{2}_{1},\ldots,{\bm{p}}^{2}_{r})$ and by using the residual connection in Equation (10) plus the output function $O(\cdot)$ in Equation (11) it is not difficult to produce the sequence of vectors $({\bm{z}}^{2}_{0},{\bm{z}}^{2}_{1},\ldots,{\bm{z}}^{2}_{r})$ such that ${\bm{z}}^{2}_{i}={\bm{p}}^{2}_{i}$, as the output of the second decoder layer. That is, we have that

There exists functions $Q_{3}(\cdot)$, $K_{3}(\cdot)$, and $V_{3}(\cdot)$ defined by feed-forward networks such that

From vectors $({\bm{p}}^{3}_{0},{\bm{p}}^{3}_{1},\ldots,{\bm{p}}^{3}_{r})$ and by using the residual connection in Equation (10) plus the output function $O(\cdot)$ in Equation (11)) it is not difficult to produce the sequence of vectors $({\bm{z}}^{3}_{0},{\bm{z}}^{3}_{1},\ldots,{\bm{z}}^{3}_{r})$ such that ${\bm{z}}^{3}_{i}={\bm{p}}^{3}_{i}$, as the output of the third and final decoder layer, and thus we have that

We finish our construction by using the final transformation function $F(\cdot)$ in Equation (12) in the following lemma.

We prove Lemma B.5 as follows (details in the next section). We show that one can construct a feed-forward network that with input ${\bm{z}}^{3}_{r}$ implements the following to produce ${\bm{y}}_{r+1}$. We move $\llbracket\ q^{(r+1)}\ \rrbracket$ and $m^{(r)}$ to its corresponding position in ${\bm{y}}_{r+1}$. Then

if $\beta^{(r+1)}=r+1$ then we let $\llbracket\ s^{(r+1)}\ \rrbracket=\llbracket\ \alpha^{(r+1)}\ \rrbracket$,

Final step

where $\alpha^{(j)}$ and $\beta^{(j)}$ are defined as

Recall that ${{\bm{K}}}^{\textbf{e}}=({\bm{k}}_{1},\ldots,{\bm{k}}_{n})$ is such that ${\bm{k}}_{i}=[\ 0,\ldots,0,i,-1,0,0\ ]$. Then we have that

Notice that, if $j\leq n$, then the above expression is maximized when $i=j$. Otherwise, if $j>n$ then the expression is maximized when $i=n$. Then $\operatorname{Att}({\bm{q}},{{\bm{K}}}^{\textbf{e}},{{\bm{V}}}^{\textbf{e}})={\bm{v}}_{i^{\star}}$ where $i^{\star}=j$ if $j\leq n$ and $i^{\star}=n$ if $j>n$. We note that $i^{\star}$ as just defined is exactly $\beta^{(j)}$. Thus, given that ${\bm{v}}_{i}$ is defined as

In order to prove the lemma we need some intermediate notions and properties. Assume that the enumeration $\pi_{1}:\Sigma\to\{1,\ldots,|\Sigma|\}$ is the one used to construct the one-hot vectors $\llbracket\ s\ \rrbracket$ for $s\in\Sigma$, and that $\pi_{2}:Q\to\{1,\ldots,|Q|\}$ is the one used to construct $\llbracket\ q\ \rrbracket$ with $q\in Q$. Using $\pi_{1}$ and $\pi_{2}$ one can construct an enumeration for the pairs in $Q\times\Sigma$ and then construct one-hot vectors for pairs in this set. Formally, given $(q,s)\in Q\times\Sigma$ we denote by $\llbracket\ (q,s)\ \rrbracket$ a one-hot vector with a $1$ in position $(\pi_{1}(s)-1)|Q|+\pi_{2}(q)$ and a in every other position. To simplify the notation we use $\pi(q,s)$ to denote $(\pi_{1}(s)-1)|Q|+\pi_{2}(q)$. One can similarly construct an enumeration $\pi^{\prime}$ for $Q\times\Sigma\times\{-1,1\}$ such that $\pi^{\prime}(q,s,m)=\pi(q,s)$ if $m=-1$ and $\pi^{\prime}(q,s,m)=|Q||\Sigma|+\pi(q,s)$ if $m=1$. We denote by $\llbracket\ (q,s,m)\ \rrbracket$ the corresponding one-hot vector for every $(q,s,m)\in Q\times\Sigma\times\{-1,1\}$. We next prove three helping properties. In every case $q\in Q$, $s\in\Sigma$, $m\in\{-1,1\}$, and $\delta(\cdot,\cdot)$ is the transition function of machine $M$.