On the Practical Computational Power of Finite Precision RNNs for Language Recognition

Introduction

Recurrent Neural Network (RNNs) emerge as very strong learners of sequential data. A famous result by Siegelmann and Sontag Siegelmann and Sontag (1992, 1994), and its extension in Siegelmann (1999), demonstrates that an Elman-RNN Elman (1990) with a sigmoid activation function, rational weights and infinite precision states can simulate a Turing-machine in real-time, making RNNs Turing-complete. Recently, Chen et al Chen et al. (2017) extended the result to the ReLU activation function. However, these constructions (a) assume reading the entire input into the RNN state and only then performing the computation, using unbounded time; and (b) rely on having infinite precision in the network states. As argued by Chen et al Chen et al. (2017), this is not the model of RNN computation used in NLP applications. Instead, RNNs are often used by feeding an input sequence into the RNN one item at a time, each immediately returning a state-vector that corresponds to a prefix of the sequence and which can be passed as input for a subsequent feed-forward prediction network operating in constant time. The amount of tape used by a Turing machine under this restriction is linear in the input length, reducing its power to recognition of context-sensitive language. More importantly, computation is often performed on GPUs with 32bit floating point computation, and there is increasing evidence that competitive performance can be achieved also for quantized networks with 4-bit weights or fixed-point arithmetics Hubara et al. (2016). The construction of Siegelmann (1999) implements pushing 0 into a binary stack by the operation $g\leftarrow g/4+1/4$. This allows pushing roughly 15 zeros before reaching the limit of the 32bit floating point precision. Finally, RNN solutions that rely on carefully orchestrated mathematical constructions are unlikely to be found using backpropagation-based training.

In this work we restrict ourselves to input-bound recurrent neural networks with finite-precision states (IBFP-RNN), trained using back-propagation. This class of networks is likely to coincide with the networks one can expect to obtain when training RNNs for NLP applications. An IBFP Elman-RNN is finite state. But what about other RNN variants?

In particular, we consider the Elman RNN (SRNN) Elman (1990) with squashing and with ReLU activations, the Long Short-Term Memory (LSTM) Hochreiter and Schmidhuber (1997) and the Gated Recurrent Unit (GRU) Cho et al. (2014); Chung et al. (2014).

The common wisdom is that the LSTM and GRU introduce additional gating components that handle the vanishing gradients problem of training SRNNs, thus stabilizing training and making it more robust. The LSTM and GRU are often considered as almost equivalent variants of each other.

We show that in the input-bound, finite-precision case, there is a real difference between the computational capacities of the LSTM and the GRU: the LSTM can easily perform unbounded counting, while the GRU (and the SRNN) cannot. This makes the LSTM a variant of a k-counter machine Fischer et al. (1968), while the GRU remains finite-state. Interestingly, the SRNN with ReLU activation followed by an MLP classifier also has power similar to a k-counter machine.

These results suggest there is a class of formal languages that can be recognized by LSTMs but not by GRUs. In section 5, we demonstrate that for at least two such languages, the LSTM manages to learn the desired concept classes using back-propagation, while using the hypothesized control structure. Figure 1 shows the activations of 10-d LSTM and GRU trained to recognize the languages $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$. It is clear that the LSTM learned to dedicate specific dimensions for counting, in contrast to the GRU.Is the ability to perform unbounded counting relevant to “real world” NLP tasks? In some cases it might be. For example, processing linearized parse trees Vinyals et al. (2015); Choe and Charniak (2016); Aharoni and Goldberg (2017) requires counting brackets and nesting levels. Indeed, previous works that process linearized parse trees report using LSTMs and not GRUs for this purpose. Our work here suggests that this may not be a coincidence.

The RNN Models

An RNN is a parameterized function $R$ that takes as input an input vector $x_{t}$ and a state vector $h_{t-1}$ and returns a state vector $h_{t}$:

The RNN is applied to a sequence $x_{1},...,x_{n}$ by starting with an initial vector $h_{0}$ (often the 0 vector) and applying R repeatedly according to equation (1). Let $\Sigma$ be an input vocabulary (alphabet), and assume a mapping $E$ from every vocabulary item to a vector $x$ (achieved through a 1-hot encoding, an embedding layer, or some other means). Let $RNN(x_{1},...,x_{n})$ denote the state vector $h$ resulting from the application of $R$ to the sequence $E(x_{1}),...,E(x_{n})$. An RNN recognizer (or RNN acceptor) has an additional function $f$ mapping states $h$ to ${0,1}$. Typically, $f$ is a log-linear classifier or multi-layer perceptron. We say that an RNN recognizes a language L$\subseteq\Sigma^{*}$ if $f(RNN(w))$ returns 1 for all and only words $w=x_{1},...,x_{n}\in L$.

In the Elman-RNN Elman (1990), also called the Simple RNN (SRNN), the function $R$ takes the form of an affine transform followed by a tanh nonlinearity:

Elman-RNNs are known to be at-least finite-state. Siegelmann Siegelmann (1996) proved that the tanh can be replaced by any other squashing function without sacrificing computational power.

IRNN

The IRNN model, explored by Le et al. (2015), replaces the $\tanh$ activation with a non-squashing ReLU:

The computational power of such RNNs (given infinite precision) is explored in Chen et al. (2017).

Gated Recurrent Unit (GRU)

In the GRU Cho et al. (2014), the function $R$ incorporates a gating mechanism, taking the form:

Where $\sigma$ is the sigmoid function and $\circ$ is the Hadamard product (element-wise product).

Long Short Term Memory (LSTM)

In the LSTM Hochreiter and Schmidhuber (1997), $R$ uses a different gating component configuration:

where $g$ can be either tanh or the identity.

Equivalences

The GRU and LSTM are at least as strong as the SRNN: by setting the gates of the GRU to $z_{t}=0$ and $r_{t}=1$ we obtain the SRNN computation. Similarly by setting the LSTM gates to $i_{t}=1$,$o_{t}=1$, and $f_{t}=0$. This is easily achieved by setting the matrices $W$ and $U$ to 0, and the biases $b$ to the (constant) desired gate values.

Thus, all the above RNNs can recognize finite-state languages.

Power of Counting

Power beyond finite state can be obtained by introducing counters. Counting languages and k-counter machines are discussed in depth in Fischer et al. (1968). When unbounded computation is allowed, a 2-counter machine has Turing power. However, for computation bound by input length (real-time) there is a more interesting hierarchy. In particular, real-time counting languages cut across the traditional Chomsky hierarchy: real-time k-counter machines can recognize at least one context-free language ($a^{n}b^{n}$), and at least one context-sensitive one ($a^{n}b^{n}c^{n}$). However, they cannot recognize the context free language given by the grammar $S\rightarrow x|aSa|bSb$ (palindromes).

For our purposes, we consider a simplified variant of k-counter machines (SKCM). A counter is a device which can be incremented by a fixed amount (Inc), decremented by a fixed amount (Dec) or compared to 0 (Comp0). Informally,Formal definition is given in Appendix A. an SKCM is a finite-state automaton extended with $k$ counters, where at each step of the computation each counter can be incremented, decremented or ignored in an input-dependent way, and state-transitions and accept/reject decisions can inspect the counters’ states using Comp0. The results for the three languages discussed above hold for the SKCM variant as well, with proofs provided in Appendix A.

RNNs as SKCMs

In what follows, we consider the effect on the state-update equations on a single dimension, $h_{t}[j]$. We omit the index $[j]$ for readability.

Finally, the counter values are exposed through $h_{t}=o_{t}g(c_{t})$, making it trivial to compare the counter’s value to 0.Some further remarks on the LSTM: LSTM supports both increment and decrement in a single dimension. The counting dimensions in $c_{t}$ are exposed through a function $g$. For both $g(x)=x$ and $g(x)=\tanh(x)$, it is trivial to do compare 0. Another operation of interest is comparing two counters (for example, checking the difference between them). This cannot be reliably achieved with $g(x)=\tanh(x)$, due to the non-linearity and saturation properties of the $\tanh$ function, but is possible in the $g(x)=x$ case. LSTM can also easily set the value of a counter to 0 in one step. The ability to set the counter to 0 gives slightly more power for real-time recognition, as discussed by Fischer et al. (1968). Relation to known architectural variants: Adding peephole connections Gers and Schmidhuber (2000) essentially sets $g(x)=x$ and allows comparing counters in a stable way. Coupling the input and the forget gates ($i_{t}=1-f_{t}$) Greff et al. (2017) removes the single-dimension unbounded counting ability, as discussed for the GRU.

We note that this implementation of the SKCM operations is achieved by saturating the activations to their boundaries, making it relatively easy to reach and maintain in practice.

SRNN

The finite-precision SRNN cannot designate unbounded counting dimensions.

By properly setting U and W, one can get certain dimensions of $h$ to update according to the value of $x$, by $h_{t}[i]=\tanh(h_{t-1}[i]+w_{i}x+b[i])$. However, this counting behavior is within a $\tanh$ activation. Theoretically, this means unbounded counting cannot be achieved without infinite precision. Practically, this makes the counting behavior inherently unstable, and bounded to a relatively narrow region. While the network could adapt to set $w$ to be small enough such that counting works for the needed range seen in training without overflowing the $\tanh$, attempting to count to larger $n$ will quickly leave this safe region and diverge.

IRNN

Finite-precision IRNNs can perform unbounded counting conditioned on input symbols. This requires representing each counter as two dimensions, and implementing Inc as incrementing one dimension, Dec as incrementing the other, and Comp0 as comparing their difference to 0. Indeed, Appendix A in Chen et al. (2017) provides concrete IRNNs for recognizing the languages $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$. This makes IBFP-RNN with ReLU activation more powerful than IBFP-RNN with a squashing activation. Practically, ReLU-activated RNNs are known to be notoriously hard to train because of the exploding gradient problem.

GRU

Summary

We show that LSTM and IRNN can implement unbounded counting in dedicated counting dimensions, while the GRU and SRNN cannot. This makes the LSTM and IRNN at least as strong as SKCMs, and strictly stronger than the SRNN and the GRU.One can argue that other counting mechanisms—involving several dimensions—are also possible. Intuitively, such mechanisms cannot be trained to perform unbounded counting based on a finite sample as the model has no means of generalizing the counting behavior to dimensions beyond those seen in training. We discuss this more in depth in Appendix B, where we also prove that an SRNN cannot represent a binary counter.

Experimental Results

Can the LSTM indeed learn to behave as a k-counter machine when trained using backpropagation? We show empirically that:

LSTMs can be trained to recognize $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$.

These LSTMs generalize to much higher $n$ than seen in the training set (though not infinitely so).

The trained LSTM learn to use the per-dimension counting mechanism.

The GRU can also be trained to recognize $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$, but they do not have clear counting dimensions, and they generalize to much smaller $n$ than the LSTMs, often failing to generalize correctly even for $n$ within their training domain.

Trained LSTM networks outperform trained GRU networks on random test sets for the languages $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$.

Similar empirical observations regarding the ability of the LSTM to learn to recognize $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$ are described also in Gers and Schmidhuber (2001).

We train 10-dimension, 1-layer LSTM and GRU networks to recognize $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$. For $a^{n}b^{n}$ the training samples went up to $n=100$ and for $a^{n}b^{n}c^{n}$ up to $n=50$.Implementation in DyNet, using the SGD Optimizer. Positive examples are generated by sampling $n$ in the desired range. For negative examples we sample 2 or 3 $n$ values independently, and ensuring at least one of them differs from the others. We dedicate a portion of the examples as the dev set, and train up to 100% dev set accuracy.

On $a^{n}b^{n}$, the LSTM generalizes well up to $n=256$, after which it accumulates a deviation making it reject $a^{n}b^{n}$ but recognize $a^{n}b^{n+1}$ for a while, until the deviation grows.These fluctuations occur as the networks do not fully saturate their gates, meaning the LSTM implements an imperfect counter that accumulates small deviations during computation, e.g.: increasing the counting dimension by 0.99 but decreasing only by 0.98. Despite this, we see that the its solution remains much more robust than that found by the GRU — the LSTM has learned the essence of the counting based solution, but its implementation is imprecise. The GRU does not capture the desired concept even within its training domain: accepting $a^{n}b^{n+1}$ for $n>38$, and also accepting $a^{n}b^{n+2}$ for $n>97$. It stops accepting $a^{n}b^{n}$ for $n>198$.

On $a^{n}b^{n}c^{n}$ the LSTM recognizes well until $n=100$. It then starts accepting also $a^{n}b^{n+1}c^{n}$. At $n>120$ it stops accepting $a^{n}b^{n}c^{n}$ and switches to accepting $a^{n}b^{n+1}c^{n}$, until at some point the deviation grows. The GRU accepts already $a^{9}b^{10}c^{12}$, and stops accepting $a^{n}b^{n}c^{n}$ for $n>63$.

Figure 1a plots the activations of the 10 dimensions of the $a^{n}b^{n}$-LSTM for the input $a^{1000}b^{1000}$. While the LSTM misclassifies this example, the use of the counting mechanism is clear. Figure 1b plots the activation for the $a^{n}b^{n}c^{n}$ LSTM on $a^{100}b^{100}c^{100}$. Here, again, the two counting dimensions are clearly identified—indicating the LSTM learned the canonical 2-counter solution—although the slightly-imprecise counting also starts to show. In contrast, Figures 1c and 1d show the state values of the GRU-networks. The GRU behavior is much less interpretable than the LSTM. In the $a^{n}b^{n}$ case, some dimensions may be performing counting within a bounded range, but move to erratic behavior at around $t=1750$ (the network starts to misclassify on sequences much shorter than that). The $a^{n}b^{n}c^{n}$ state dynamics are even less interpretable.

All of this empirically supports our result, showing that IBFP-LSTMs can not only theoretically implement “unbounded” counters, but also learn to do so in practice (although not perfectly), while IBFP-GRUs do not manage to learn proper counting behavior, even when allowing floating point computations.

Conclusions

We show that the IBFP-LSTM can model a real-time SKCM, both in theory and in practice. This makes it more powerful than the IBFP-SRNN and the IBFP-GRU, which cannot implement unbounded counting and are hence restricted to recognizing regular languages. The IBFP-IRNN can also perform input-dependent counting, and is thus more powerful than the IBFP-SRNN.

We note that in addition to theoretical distinctions between architectures, it is important to consider also the practicality of different solutions: how easy it is for a given architecture to discover and maintain a stable behavior in practice. We leave further exploration of this question for future work.

Acknowledgments

The research leading to the results presented in this paper is supported by the European Union’s Seventh Framework Programme (FP7) under grant agreement no. 615688 (PRIME), The Israeli Science Foundation (grant number 1555/15), and The Allen Institute for Artificial Intelligence.

Appendix

Appendix A Simplified K-Counter Machines

We use a simplified variant of the k-counter machines (SKCM) defined in Fischer et al. (1968), which has no autonomous states and makes classification decisions based on a combination of its current state and counter values. This variant consumes input sequences on a symbol by symbol basis, updating at each step its state and its counters, the latter of which may be manipulated by increment, decrement, zero, or no-ops alone, and observed only by checking equivalence to zero. To define the transitions of this model its accepting configurations, we will introduce the following notations:

We now define the model. An SKCM is a tuple $M=\langle\Sigma,Q,q_{o},k,\delta,u,F\rangle$ containing:

A counter update function We note that in this definition, the counter update function depends only on the input symbol. In practice we see that the LSTM is not limited in this way, and can also update according to some state-input combinations — as can be seen when it it is taught, for instance, the language $a^{n}ba^{n}$ We do not explore this here however, leaving a more complete characterization of the learnable models to future work.

A set of accepting maskedi.e., counters are observed only by zero-ness. configurations

The language recognized by a k-counter machine is the set of words $w$ for which the machine reaches an accepting configuration — a configuration $c=(q,n)$ for which $(q,z(n))\in F$.

Note that while the counters can and are increased to various non-zero values, the transition function $\delta$ and the accept/reject classification of the configurations observe only their zero-ness.

We show that the SKCM model can recognize the context-free and context-sensitive languages $a^{n}b^{n}$ and $a^{n}b^{n}c^{n}$, but not the context free language of palindromes, meaning its computational power differs from the language classes defined in the Chomsky hierarchy. Similar proofs appear in Fischer et al. (1968) for their variant of the k-counter machine.

We define the following SKCM over the alphabet $\{a,b\}$:

for any $z\in\{0,1\}$: $\delta(q_{a},a,z)=q_{a},\;\;\;\;\;\delta(q_{a},b,z)=q_{b},\\ \delta(q_{b},a,z)=q_{r},\;\;\;\;\;\delta(q_{b},b,z)=q_{b}\\ \delta(q_{r},a,z)=q_{r},\;\;\;\;\;\delta(q_{r},b,z)=q_{r}$

The state $q_{r}$ is a rejecting sink state, and the states $q_{a}$ and $q_{b}$ keep track of whether the sequence is currently in the “$a$” or “$b$” phase. If an $a$ is seen after moving to the $b$ phase, the machine moves to (and stays in) the rejecting state. The counter is increased on input $a$ and decreased on input $b$, and the machine accepts only sequences that reach the state $q_{b}$ with counter value zero, i.e., that have increased and decreased the counter an equal number of times, without switching from $b$ to $a$. It follows easily that this machine recognizes exactly the language $a^{n}b^{n}$.

We define the following SKCM over the alphabet $\{a,b\}$. As its state transition function ignores the counter values, we use the shorthand $\delta(q,\sigma)$ for $\delta(q,\sigma,z)$, for all $z\in\{0,1\}^{2}$.

$u(a)=(+1,\emptyset),\\ u(b)=(-1,+1),\\ u(c)=(\emptyset,-1)$

for any $z\in\{0,1\}$: $\delta(q_{a},a)=q_{a},\;\delta(q_{a},b)=q_{b},\;\;\delta(q_{a},c)=q_{r},\\ \delta(q_{b},a)=q_{r},\;\;\delta(q_{b},b)=q_{b},\;\;\delta(q_{b},c)=q_{c},\\ \delta(q_{c},a)=q_{r},\;\;\delta(q_{c},b)=q_{r},\;\;\delta(q_{c},c)=q_{c},\\ \delta(q_{r},a)=q_{r},\;\;\delta(q_{r},b)=q_{r},\;\;\delta(q_{r},c)=q_{r}$

By similar reasoning as that for $a^{n}b^{n}$, we see that this machine recognizes exactly the language $a^{n}b^{n}c^{n}$. We note that this construction can be extended to build an SKCM for any language of the sort $a_{1}^{n}a_{2}^{n}...a_{m}^{n}$, using $k=m-1$ counters and $k+1$ states.

Palindromes:

We prove that no SKCM can recognize the language of palindromes defined over the alphabet $\{a,b,x\}$ by the grammar $S\rightarrow x|aSa|bSb$. The intuition is that in order to correctly recognize this language in an one-way setting, one must be able to reach a unique configuration for every possible input sequence over $\{a,b\}$ (requiring an exponential number of reachable configurations), whereas for any SKCM, the number of reachable configurations is always polynomial in the input length.This will hold even if the counter update function can rely on any state-input combination.

Let $M$ be an SKCM with $k$ counters. As its counters are only manipulated by steps of 1 or resets, the maximum and minimum values that each counter can attain on any input $w\in\Sigma^{*}$ are $+|w|$ and $-|w|$, and in particular the total number of possible values a counter could reach at the end of input $w$ is $2|w|+1$. This means that the total number of possible configurations $M$ could reach on input of length $n$ is $c(n)=|Q|\cdot(2n+1)^{k}$.

$c(n)$ is polynomial in $n$, and so there exists a value $m$ for which the number of input sequences of length $m$ over $\{a,b\}$ — $2^{m}$ — is greater than $c(m)$. It follows by the pigeonhole principle that there exist two input sequences $w_{1}\neq w_{2}\in\{a,b\}^{m}$ for which $M$ reaches the same configuration. This means that for any suffix $w\in\Sigma^{*}$, and in particular for $w=x\cdot w_{1}^{-1}$ where $w_{1}^{-1}$ is the reverse of $w_{1}$, $M$ classifies $w_{1}\cdot w$ and $w_{2}\cdot w$ identically—despite the fact that $w_{1}\cdot x\cdot w_{1}^{-1}$ is in the language and $w_{2}\cdot x\cdot w_{1}^{-1}$ is not. This means that $M$ necessarily does not recognize this palindrome language, and ultimately that no such $M$ exists.

Note that this proof can be easily generalized to any palindrome grammar over $2$ or more characters, with or without a clear ‘midpoint’ marker.

Appendix B Impossibility of Counting in Binary

While we have seen that the SRNN and GRU cannot allocate individual counting dimensions, the question remains whether they can count using a more elaborate mechanism, perhaps over several dimensions. We show here that one such mechanism — a binary counter — is not implementable in the SRNN.

For the purposes of this discussion, we first define a binary counter in an RNN.

In an RNN with hidden state values in the range $(-1,1)$, the binary interpretation of a sequence of dimensions $d_{1},...,d_{n}$ of its hidden state is the binary number obtained by replacing each positive hidden value in the sequence with a ‘1’ and each negative value with a ‘0’. For instance: the binary interpretation of the dimensions 3,0,1 in the hidden state vector $(0.5,-0.1,0.3,0.8)$ is 110, i.e., 6.

Binary Counting

We say that the dimensions $d_{1},d_{2},...,d_{n}$ in an RNN’s hidden state implement a binary counter in the RNN if, in every transition, their binary interpretation either increases, decreases, resets to 0, or doesn’t change.We note that the SKCMs presented here are more restricted in their relation between counter action and transition, but prefer here to give a general definition. Our proof will be relevant even within the restrictions.

A similar pair of definitions can be made for state values in the range $(0,1)$.

We first note intuitively that an SRNN would not generalize binary counting to a counter with dimensions beyond those seen in training — as it would have no reason to learn the ‘carry’ behavior between the untrained dimensions. We prove further that we cannot reasonably implement such counters regardless.

We now present a proof sketch that a single-layer SRNN with hidden size $n\geq 3$ cannot implement an $n$-dimensional binary counter that will consistently increase on one of its input symbols. After this, we will prove that even with helper dimensions, we cannot implement a counter that will consistently increase on one input token and decrease on another — as we might want in order to classify the language of all words $w$ for which $\#_{a}(w)=\#_{b}(w)$.Of course a counter could also be ‘decreased’ by incrementing a parallel, ‘negative’ counter, and implementing compare-to-zero as a comparison between these two. As intuitively no RNN could generalize binary counting behavior to dimensions not used in training, this approach could quickly find both counters outside of their learned range even on a sequence where the difference between them is never larger than in training.

Consistently Increasing Counter: The proof relies on the linearity of the affine transform $Wx+Uh+b$, and the fact that ‘carry’ is a non-linear operation. We work with state values in the range $(-1,1)$, but the proof can easily be adapted to $(0,1)$ by rewriting $h$ as $h^{\prime}+0.5$, where $h^{\prime}=h-0.5$ is a vector with values in the range $(-0.5,0.5)$.

Suppose we have a single-layer SRNN with hidden size $n=3$, such that its entire hidden state represents a binary counter that increases every time it receives the input symbol $a$. We denote by $x_{a}$ the embedding of $a$, and assume w.l.o.g. that the hidden state dimensions are ordered from MSB to LSB, e.g. the hidden state vector $(1,1,-1)$ represents the number 110=6.

Recall that the binary interpretation of the hidden state relies only on the signs of its values. We use $p$ and $n$ to denote ‘some’ positive or negative value, respectively. Then the number 6 can be represented by any state vector $(p,p,n)$.

Recall also that the SRNN state transition is

As tanh is sign-preserving, this simplifies to:

Noting the linearity of matrix multiplication and that $(1,-1,-1)=-(-1,1,1)$, we obtain:

Similarly, for $(-1,-1,1)$ and $(1,1,-1)$, we obtain

We note that this proof does not extend to the case where additional, non counting dimensions are added to the RNN — at least not without further assumptions, such as the assumption that the counter behave correctly for all values of these dimensions, reachable and unreachable. One may argue then that, with enough dimensions, it could be possible to implement a consistently increasing binary counter on a subset of the SRNN’s state.(By storing processing information on the additional, ‘helper’ dimensions) We now show a counting mechanism that cannot be implemented even with such ‘helper’ dimensions.

Bi-Directional Counter: We show that for $n\geq 3$, no SRNN can implement an $n$-dimensional binary counter that increases for one token, $\sigma_{up}$, and decreases for another, $\sigma_{down}$. As before, we show the proof explicitly for $n=3$, and note that it can be simply expanded to any $n>3$ by padding.

Assume by contradiction we have such an SRNN, with $m\geq 3$ dimensions, and assume w.l.o.g. that a counter is encoded along the first 3 of these. We use the shorthand $(v_{1},v_{2},v3)c$ to show the values of the counter dimensions explicitly while abstracting the remaining state dimensions, e.g. we write the hidden state $(-0.5,0.1,1,1,1)$ as $(-0.5,0.1,1)c$ where $c=(1,1)$.

(i.e., $\sigma_{up}$ increases the counter and updates the additional dimensions to the values $c_{1}$, while $\sigma_{down}$ decreases and updates to $c_{2}$.) Removing the sign-preserving function tanh we obtain the constraints

i.e. $(b_{up}-b_{down})[0:2]=(n,p,n)-(n,n,n)$, and in particular $(b_{up}-b_{down})>0$. Now consider a reachable state $h_{3}$ for which the counter value is $3$. Similarly to before, we now obtain

from which we get $(b_{up}-b_{down})[0:2]=(p,n,n)-(n,p,n)$, and in particular $(b_{up}-b_{down})<0$, a contradiction to the previous statement. Again we conclude that no such SRNN can exist.

References