Turing Completeness of Bounded-Precision Recurrent Neural Networks
Authors: Stephen Chung
Hava Sieglemann
Venue: NeurIPS 2021 Poster (2021)
Keywords: Recurrent Neural Network
Stack Recurrent Neural Network
Neural Turing Machine
Turing Complete
Turing machine
Memory

Abstract: Previous works have proved that recurrent neural networks (RNNs) are Turing-complete. However, in the proofs, the RNNs allow for neurons with unbounded precision, which is neither practical in implementation nor biologically plausible. To remove this assumption, we propose a dynamically growing memory module made of neurons of fixed precision. The memory module dynamically recruits new neurons when more memories are needed, and releases them when memories become irrelevant. We prove that a 54-neuron bounded-precision RNN with growing memory modules can simulate a Universal Turing Machine, with time complexity linear in the simulated machine's time and independent of the memory size. The result is extendable to various other stack-augmented RNNs. Furthermore, we analyze the Turing completeness of both unbounded-precision and bounded-precision RNNs, revisiting and extending the theoretical foundations of RNNs.

Turing Completeness of Bounded-Preeision Recurrent Neural Networks
Stephen Chung"
Hava Siegelmann"
Department of Computer Science
Department of Computer Science University of Massachusetts Amherst
University of Massachusetts Amherst
Amherst, MA 01003 minghaaychungumass.co edu
Amherst, MA 01003
hava@umass.
Abstract
Previous works have proved that recurrent neural networks (RNNs) are Turing- complete. However, in the proofs, the RNNs allow for neurons with unbounded precision, which is neither practical in implementation nor biologically plausible. To remove this assumption, made neurons of fixed precision. The memory module dynamically recruits neurons when more memories needed, and releases them when memories become irrelevant. We prove that a 54-neuron suunded-precision RNN with growing memory modules can simulate a Universal Turing Machine, with time complexity linear in the simulated machine's time and independent of the memory size. The result is extendable various other stack-augmented RNNs. Furthermore, we analyze the Turing completeness of both unbounded-precd -peecssinn and bounded- precision RNNs, revisiting and extending the theoretical foundations of RNNs.
propose dynamically growing memory module
Introduction
Symbolic (such Turing Machines) and sub-symbolic processing (such as adaptive neural networks) are two competing methods of representing and processing information, each with its own advantages. An ultimate way combine symbolic and sub-symbolic capabilities is by enabling the running of algorithms on neural substrate, which means a neural network that can simulate a Universal Turing Machine (UTM). Previous works 2 3 have shown that this is possible there exists recurrent neural network (RNN) that can simulate a UTM. These proofs assumed couple of neurons with unbounded precision that equals the number of symbols used in the Turing tape. Here provide an alternative simulation of a UTM by RNNs with bounded neurons only.
The general idea works follows. The Turing Machine's tape is stored in a growing memory module, which is a stack of neurons with pushing and popping operations controlled by neurons in the RNN. The size of the growing memory module is determined by the usage of the Turing tape it dynamically recruits new neurons when more memories are needed and releases them when memories become irrelevant. The neurons in the stack, except for the top neuron, are not regularly updated (and hence can be referred to as passive), saving computational cost for memories that are not in the focus of the computing and do not require change. Using growing memory modules, RNN is constructed that can simulate any Turing Machine.
54-neuron
Our proposed growing memory modules inspired by biological memory systems. The process of dynamically recruiting new neurons when more memories are necessary is also observed in biological memory systems. Neurogenesis is the process by which new neurons produced in the central nervous system; it is most active during early development, but continues through life.
Both authors contributed equally.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In adult vertebrates, neurogenesis is known to occur in the dentate gyrus (DG) of the hippocampal
formation 4 and the subventricular zone (SVZ) of the lateral ventricles [5]. Since DG well-known in neuroscience for its role in pattern separation for memory encoding 6 7 this suggests that biological memory systems also dynamically recruit new neurons. The rate of neurogenesis in adult mice has been shown to be higher if they are exposed to a wider variety of experiences [8]. This further suggests a role for self-regulated neurogenesis in scaling up the number of new memory that can be encoded and stored during one's lifetime without catastrophic forgetting of previously consolidated memory, Besides the mechanism of recruiting new neurons, the process of storing neurons in growing memory modules also shares some similarities with biological memory consolidation, process by which short-term memory is transformed into long-term memory [9 10]. Compared to short-term memory, long-tern memory is more long-lastnn lasting and robust interference. This is similar to the neurons stored in growing memory modules- - the values of these neurons (except the top neuron in the stack) remain unchanged and cannot be interfered by the RNN, providing mechanism to store information stably.
Growing memory modules share similarities with other stack-augmented RNNs M2 I 14 15
In neural stacks (Α,] the RNN outputs two continuous scalars that control the strength of pushing and popping operations. and the stack is made differentiable by adding strength vector. In stack RNNs [1] and DiffStk- RNN [T3]. the RNN outputs the probability vector corresponding to pushing, popping, and operation. In NNPDA 13), the RNN outputs a continuous scalar that controls the pushing and popping operations, with the minimum value corresponding to popping and the maximum value corresponding pushing. NSPDA [4] uses discrete- valued action neurons to control pushing and popping operations. In contrast to these models, growing memory modules have simple design and do not need to be differentiable. However, it can be easily shown that growing memory modules can be simulated by these stack-augmented RNNs in linear time, and thus growing memory modules can be considered generic type of stack-augmented RNNs. Therefore, our proof on the Turing completeness of an RNN with growing memory modules can be extended to stack-augmented RNNs in general, establishing their theoretical motivation.
RNN that is fully differentiable was introduced in 1996 [66;; this feature is a prerequisite to have the network trainable by gradient descent. It was followed by the Neural Turing Machine (NTM) [77 and its improved version, the differentiable neural computer [18]. which are both differentiable and trainable RNNs equipped with memory banks. Though inspired by Turing Machines, bounded- -precisionn NTMs and differentiable neural computers are not Turing-complete due to the fixed-sized memory bank, but they can simulate space-boundee Turing Machines (see
Section 5)
Simulation of a Turing Machine by an RNN with growing memory modules represents practical and biologically inspired way to combine symbolic and sub-symbolic capabilities. All neurons in the RNN and growing memory modules have fixed precision. While the size of growing memory modules is linear in the number of symbols used in the Turing tape, the number of neurons in the RNN is still constant. Moreover, the neurons in growing memory modules (except the top neuron in the stack) are passive at most times. As a result, the time complexity of the simulation is linear in the simulated machine's 's time and independent of the memory size. By showing how simulate Turing Machine with a bounded-preg -rreddiinrreiioonn RNN and thereby constructing a bounded- prreciiine RNN that can run any algorithms, our paper proposes practical method that combines symbolic and sub-symbolic capabilities.
The remainder of the paper is structured as follows. Section 2 describes the preliminary of the paper, including the definition of Turing Machines and RNNs. Section 3 revisits and extends theories relating simulating a Turing Machine with unbounded-precision RNNs and shows the existence of a 40-neuron unbounded precissonn RNN that is Turing- Turing-complete. Section presents the growing memory modules and proves the existence of a 54-neuron mounded-precision memory modules that is Turing-complest Section5Jrelate relates the number of neurons and the precision of RNNs when simulating Turing Machines. Section @ooncludes the paper.
RNN with two growing
2 Background and Notation
Turing Machine is a 7-uple M = (Q, go. E, F), where Q is finite set of states, Σ is finite set of input symbols, I'is is finite set of tape symbols (note that Σ C I), 8: Qx (L,
2

---

is the machine's transition rule, qu E Q is the initial starting state, $ is the blank symbol (note that I but & Σ), and F C Q is the set of final state. We only consider deterministic Turing Machines in this paper.
The instantaneous description (or the configuration) of Turing Machine is typically defined tuple of state, tape, and the location of the read/write head. However, we use slightly different definition the paper. We define the left-tape symbols (or the left tape in short), denoted as sg, be the string of symbols starting at the symbol under the read/write head and extending to the left. We define the right-tape symbols (or the right tape in short). denoted as sg, to be the string of symbols starting at the symbol to the right of the read/write head and extending to the right. The first symbol in both strings is the closest to the read/write head in both sL and sy (that is, the left tape reversed in the representation) and the blank symbols at the two ends are omitted. Therefore, the length of sr. and sn combined equals to the number of symbols used in the Turing tape in each step (that is, unbounded but not infinite). Since s and 8 encode both the tape and the location of the read/write head, we define the instantaneous description of Turing Machine as a 3-tuple (g. 8L; 8n) E (Q. r", r'), where g denotes the state, 5, denotes the left-tape symbols, and sg denotes the right-tape symbols. Though the two definitions are equivalent, this definition allows easy encoding of tape symbols into neurons' values. The set of all possible instantaneous description is denoted as X' = (QTT",
In each step of a Turing Machine, the symbol under the read/write head is read and, together with the state, determines the symbol to be written under the read/write head, the direction of moving the tape, and the next state. To be precise, the complete dynamic map of M, denoted as PM : X' + X. is defined as follows: 1. Let x = (g. S1, 8n) be the input configuration, LL,(1) denote the first symbol 8, and 8 $R.(1) denote the first symbol in 8n- The transition is defined by the 3-tuple (g', y. d) ō(g, SL.())); 2. Replace the state of the machine q with q' and the first symbol in s by ys 3. Move the symbol in (1,(1)) to become the new (1,(1) if d = L, and move $n.(1) to become the new $1.(1) if d R (if there are no symbols left in SL or $R for moving, append a blank symbol : before moving). Denote the left-tape symbols and the right-tape symbols after 2. and 3. by & and s'n respectively. Then (x) = (q', ( represents one transition of the Turing Machine M from one configuration to the next. The partial input-output function of M, denoted as PM X X, is defined by applying PM repeatedly until q E F, and is undefined if it is not possible to have g E F by applying PM repeatedly.
recurrent neural network (RNN) is neural network consisting of n neurons. The value of neuron i at time t {1, 2, ). denoted as (t) E Q (Q is the set of rational numbers), is computed by an affine transformation of the values of neurons in the previous state followed by an activation function o, i.e. (1) a (Ei= (1yzr(( - 1) + b.), where Way are the weights and b; is the bias; or in vector
form:
x(t) = (Wx(( - 1)+ b),
(I)
where x(t) Q", W E Rn** and b E. This defines mapping Tw: : Q Q" which characterizes an RNN. For simplicity, we consider the saturated-linear function in this paper; that is:
0
if < 0, x
xx)
1 if >
Thus, x(f) E (Q [0, 1])" for all t > 0.
We say that neuron 2; (t) has precision p in base b if for all t > 0, xx(() can be expressed as (t) (1 (6)
El
for some strings a(I) E (0, be.,,,..,,p and c(t) E (1,...,bpP
For a string a, we use (() to denote the 2h symbol in and ((ay) to denote the string (()))))))) For function f that maps from set Y to a subset of Y. use fr to denote the mh iterate of where 1 < n < co. For any two vectors x E R" y E R", we use x @ y E Rm+* to denote the concatenation of the two vectors. We use A to denote all possible strings formed by elements from set A.
The notation is summarized in the table found in Appendix D.
3

---

3 Turing Completeness of Unbounded-Precision RNNs
To simulate Turing Machine M by an RNN, we first consider how to encode the instantaneous description (g. SL, SR) E X' by a vector of rational numbers. For the state E Q, we encode it with Doga [RI1, with each possible combination of
[logg [Q]] binary values, denoted as p/4) : Q + {0, 10
binary values representing a specific state.
Example. Let Q = 3,,2,3.4,5, 6). We can encode it by [log2 [Q] = binary values, with
pl9) (1) = [0, 0, p()) = [0,0, 11, (3) = [0, 1, pl) (4) = [0. 1, 11. (5) = [1, 0). and
(6) = [1. 0, 1].
For the left tape s1 E I and the right tape sR E I", we use fractal encoding in two rational numbers, as recommended in 2). The fractal encoding. bearing similarity to Cantor sets, enables fast manipulation of the top symbols.
Without loss of generality, assume that the tape symbols I are encoded into numbers 11,,55....7 2 1} and that the blank symbol is encoded by 1. Then, define the fractal encoding p : - Q by:
|01
(v) =
9(t)
+ (2/rI)) (2|1) - 1)
(3)
(2
Example. Let r (1,3,5, 7,. R
8L =
(3.
5,
5)).
5).
and = 1. Then p
82
5
83
8
5 + nr 57
+ 5" +...
-/ g
+
+ g
8 The last term in represents the infinite
g7
blank symbols of a tape.
This encoding requires the tape symbol neurons to have the same precision as the size of the active (non-blank) part of the tape in base 2 As the tape in Turing Machine has unbounded size, it means that we require neurons with unbounded precision. This is different from infinite precision but still not applicable. Hence, we will discuss how remove this behhounded-preiisiin assumption in Section 4
Finally, we encode the value of the top symbol in each tape neuron, 82,(1) and (1,(1), by binary tuple ((r) 1 + {0, 1-1
P (3) = B > 2
|T 1).
(4)
(y) is if and only if the symbol y has a value larger than 2i, and is That is, the i coordinate of (y)) otherwise.
Example. Let r = 7,J. Then (1) (1) [0,0,0), 0 (1,,,),,,10) [1, 1, OJ. and (7) 1,
Combining the above discussion, we define the encoding function of contigurations p : X + Q21 1Q1)+12111++ by:
p(g. SL, sn) pl (SL) pl TT (8L,(1)) e (sR. @ 0, (5)
where 0 is zero vector of size [Q|[T| + 5. Letp p(x)) + X' be the inverse function such that p (p(x)) = x for all x E X' (note that p is injective, iec p(z) = p(x') implies x = 2'); we call p
the decoder function.
should be noted that (1) @ ((L) @ (sn) is sufficient to decode the instantaneous description. We include ((r) (st.tn) @ ($R,()) ① only because facilitates the full simulation on the RNN. This completes the construction of the encoding function.
Given an instantaneous description Then, it is possible to construct the parameters of RNN such that the update given by the RNN on these neurons is the same as the update given by the Turing Machine:
X, we initialize the neurons in an RNN with values p(x).
Theorem 1. Given Turing Machine M, there exists an injective functton : + QN and an seeruundddd-reciiioon precision RNN Tw., Q" + Q", where n = 2| + [loga iQ + [Q] 55 such that for all instantaneous descriptions E X,
n-neuron unbounded
(TWbb((((=) =MM(z).
(6)
4

---

Proof. A sketch of the proof is as follows. Neurons in the RNNs are grouped by their function. Tape neurons, initialized with p()) and (()) encode the tape in fractal encoding, Readout neurons, initialized with ( and (s,)(s) encode the first symbol in the left and the right tape. State neurons, initialized with p (q), encode the state. We need to update the values of these neurons to simulate one step of the Turing Machine. Three steps (or stages) of RNN are required to simulate one step of a Turing Machine. In the first stage, entry neurons, initialized with O, compute the combination of the state and the symbol under the head. Since this combination fully determines the next transition, we use update the state neurons and the temporary tape neurons during stage two. Temporary tape neurons serve as a buffer for tape neurons when shifting the tape to the left or right. In stage three, we move the values from the temporary tape neurons to tape neurons to complete the update. The detailed proof can be found in Appendix A.
In other words, to simulate one step of a Turing Machine M, we can first encode the instantancous description x by the encoder function p. apply the RNN three times T b. and decode the values back by pー1 to obtain (z), the instantaneous description after one step of the Turing Machine. Or equivalently, for any Turing Machine M, there exists an RNN such that every three steps of the RNN yield the same result as one step of the Turing Machine.
By applying Theorem repeateddyy we simulate a Turing Machine with an RNN in a linear time. To be specific, the partial input-oulpul function funcitttooitttnnio of an RNN, denoted Tw Q + Q.V is defined by applying T repeatedly until q E F (where is the state that the RNN simulates), and is undefined if is not possible to have 9 E F by applying Twi repeatedly. Based on this definition and Theorem 1 it follows that:
Corollary 1.1. Given a Turing Machine M, there exists an injective function p =: + Q" and an
n-neuron unbounded unbisnddd-precision RNN Tw.b" Q" + Q2", where = =2 + [log2 [Q + +Q such that for all instantaneous descriptions x E X, the following holds: Pf (I) is defined, then
p- (Tw. PP)((>)
and PMM(() is not defined, then Tw. (p(x)) is also not defined. If (PM(2))) (x) is defined and computed in T steps by M, then (p(x)( is computed in 3T steps by the RNN.
Corollary I.I shares similarities with Theorem 1 in M. However, our theorem states that 37' instead of 47', is sufficient to simulate a Turing Machine. We also give the relationship between the number of neurons required by the RNN and the size of Q and I' in the Turing Machine.
small UTM with 6 states and 4 symbols, denoted by Us.4, was proposed [9] and can simulate any Turing Machine in time O where the number of steps required by the Turing Machine (the one to be simulated) to compute the result. As Ug.4 is also a Turing Machine, we apply Corollary 1.1 to simulate U6.4, leading to curpleecomplete RNN. Plugging in IQ = 6 and [ = 4, we obtain the following result:
Corollary 1.2. There exists 40-neuron unbounded unbounded-precisson RNN that can simulate any Turing Machine in O(T)), where T is the number of steps required for the Turing Machine to compute the result.
should be noted that [ focused on capabilities and proved a Turing-complete RNN with 1058 neurons; (20] proposed a Turing-complete RNN with 52 neurons. Here we provide a plug-and-play formula to simulate any Turing Machine.
4 Turing Completeness of Bounded-Preecisonn RNNs with Growing Memory
In the following, we consider how to remove the assumption of unbounded neural precision (Section 3) without reducing computational capacity. If we assume all neurons to have precision bounded by p in base 2 then the tape can be encoded by [|sşl/p] neurons using fractal encoding, where j E (I, Rt.. We do this by encoding every symbols of the tape into single neuron. Since most of these neurons do not require updates, just like symbols far from the read/write head in a Turing tape, propose to store them in separate growing memory module organized in siack-like manner:
5

---

Pushing
Popping
i. Before RNN update
ii. After RNN update
iii. Resize sequence
iv. Dynamic pointer
Stack
RNN
(a) An RNN with growing memory modulc
(b) Pushing with dynamic pointer
Figure 1: (a) An RNN with growing memory module. The RNN controls the pushing and popping of the stack by two neurons ((t) and o(t). (b) Illustration of pushing in growing memory module as dynamic pointer. Orange (dark) and gray (light) circles represent non-zero neurons and zero neurons respectively. i. Before RNN update, vlt - 1) = 0. RNN set u(() = c where e > 0 the value to be pushed. iii. One zero neuron is appended the sequence since there are no zero neurons left. iv. Both u and o point to different neurons in the sequence, ready to read by other neurons in the next update of RNN.
Definition growing memory module is stack of non-zero neurons with push and pop operations controlled by two neurons in an RNN, denoted as push newron u(t) and pop neuron o(t), in the following way: for every step t after the RNN finished updating the values of neurons, (i) if u(t) > then new neuron with the value u(t) is pushed to the stack and u(t) is set to O; (ūi) if o(t) = 0 and the stack not empty, then the top neuron is popped from the stack and o(t) is set to the value of the top neuron in the updated stack; (iii) if o()) = 0 and the stack is empty, then o(l) is set to defauls value c.
An RNN with growing memory module is mapping Tw.. (Q-V Q*) - (Q.) Q*)) where the first element the tuple corresponds to values of neurons in the RNN and the second element of the tuple corresponds to the stack of the growing memory module. We can equip RNN with multiple growing memory modules, with each module having its own push and pop neurons controlled by the RNN. An RNN with two growing memory modules will be defined by mapping Tw.b: : (QN, Q") + (Q Q", Q*))
We can view the growing memory module a way of dynamically pointing to sequence of non-zero neurons appended by one zero neuron. o(t) can be viewed the pointer for the last non-zero neuron in the sequence. and ut)) can be viewed the pointer for the zero neuron at the beginning of the sequence; see Figure
With two growing memory modules (one for the left tape and one for the right tape), we can construct an RNN with counded-precistee neurons that can simulate any Turing Machine. We first describe how to encode the instantaneous description (g. SL, SR) E X' by vector of rational numbers and two stacks, with which RNN and its growing memory modules can be initialized. In the following discussion, we assume that all neurons have precision bounded by 2 2 in base T[[; that is, each neuron can encode p symbols most.
Both the state and the top symbols $L.(1) 8R,(1) are encoded with binary values as in Section 3 For the tape 8, (j {L, R)), we define the fractal encoding ((*) I + by:
3(0)
(2
which is similar to except for the encoding of infinite blank symbols. Then, encode the tape 8y into stack of neurons as follows: First, encode the rightmost p symbols (the ones farthest from the read/write head) with p' and push it empty stack, denoted as My. Then, encode the next

---

rightmost p symbols and push it to M, again, and repeat until at least one and at most p symbols remain in the tape. Denote this encoding function for the tape plM D - Q" The remaining symbols in the tape, denoted as (),(1=((==))) where h(y) == ((V - 1) mod p) + 1, will be encoded with fractal encoding p(*) as well, but would appear in neurons inside the RNN.
The general idea is to let only the symbols closest to the read/write head (8 (,,,1, ()) reside in the RNN. If the number of symbols residing in the RNN reaches O or p. then we pop from or push to the stack respectively to ensure that at least 1 and at most p symbols reside in the tape neurons. is interesting to note that the hth neuron in the stack (from the top) requires at least kp steps of the Turing Machine before may be updated, the values of neurons near the bottom of the stack will not be changed for many steps. That is, the neurons in the stack, except for the top neurons, are passive.
Example. Let I = (,,3,5,7]...... 8T. = (3.5,7.3,) 5,3, 7) and p = Then the number of symbols to remain in the RNN and they are encoded by pl (sL, ()) + symbols are stored in the stack: (sr)) = 1 + 2 + gr
5 82 The remaining six
gr)
We encode in neuron h[1s,)), the number of symbols in 8, (j (T, RJ). In the above example, h((s = 2. These neurons help the RNN to know when pushing or popping operations are required. We use the encoding p(h):
p} + Q, defined by:
(v) p+1
y
(9)
Together, define the encoding function p p::. (Q 2 [1gg, 101++11111+1 ,", Q*) by: p(g. 8L, SR) =pp()) (q) @ p (SL,(I:t((en m)) p (sR(())(ea))) e
pl (frr,Mleeen))) (h) (N((szl) @ O, (AD) (sL), (M) (M))
+ p (SL.LL) @ (sR, @ (h) (h((sr.))
(10)
where is a zero vector of size [ + 15. The first element of the tuple is for initializing the neurons in the RNN, while the second and third element of the tuple is for initializing the two growing memory stack modules. All encoded values have precision of p. Similar to the previous section, p is injective and so we can define the decoder function p= p(X') + X.
With the new encoding function P and growing memory modules, we can prove an alternative version to Theorem that only requires bounded precision neurons:
Theorem 2. Given a Turing Machine M, there exists an injective function p X (Q", Q Q*) and an n-neuron p-precision (in base 2(T)) RNN with two growing memory modules Tw,b (Q", Q,, Q*)= (Q" "',Q"" Q²), where n 2 + [log, 1Q + +Q[[[] + 19 and p 2 2, such that for all instantaneous descriptions I E X.
(TW PM))).
(11)
Proof. The detailed proof is in Appendix B. To illustrate the construction of the RNN, the parameters for the neuron initialized with (()) (h([sz)), called the left guard neuron and denoted gr (t), will be described here.
We assume all neurons in the RNN are initialized with values from the encoder function p(x) at time t = 1. The guard neuron 9r. (t) encodes the number of left-tape symbols residing in the RNN. In three stages of an RNN, we need update its value from (1) = h(|szl)/(p + 1) to
(4) = D))s2)/(( 1), where s' is the left tape after one step of the Turing Machine. First, notice that ((s{2]) can be expressed as:
h h((s2)) - if d = L and h((s1]) 2 2,
if d L and h[s2))) = 1,
(12)
h h((sr.)) +1
if d R and h(ss..) < pp- 1,
dd R and h ([stl) = P.
where di is the direction that the Turing Machine's 's head is moved.
7

---

Example. Assume d = L and the size of the active symbols is h((sz]) = 1, which means that the Turing Machine moving left and there is only one symbol residing the RNN. Since after the move, 8z, will have one symbol less and so the corresponding neuron (1. will encode no symbols. As result, the top neuron of the left growing memory module would be popped out, and s1. (8) would assume its value. This way the neuron 8y (t) again encodes the active symbols (1 to p) of the left tape series, and h h((sz,)) is set to p. (Alternatively, one may prove it directly by the definition of h and the fact that |s% = | 1.) An analogous process holds when the Turing Machine is moving right.
We implement with an RNN as follows. Define stage neurons as:
(t + 1) a(1 (1) - oz(1)) (t + 1) = a
(13)
(14)
with both neurons initialized to be zero. Define c(t) := [cr (t), e2 ct), ct())] where ca(t) == 1 - (t) - (t)),, then c(1) [0,0, 1]: c(2)
[1 0, 0]: c(3) [0, 1, 0j. These stage neurons signal
which one of the three stages that the RNN is in.
In the construction of the RNN, there exists a linear sum of neurons, denoted as d(t) = (t), dx()))
such that if the Turing Machine is moving left, d11 = [0, 0]; d(2) = [1,0]; d = [0, 0]: and
the Turing Machine is moving right, d(1) [0, 0): (2) = [0, 1]; d(3) [0, O]: this signals which
direction the Turing Machine is moving to (formulas of dd() appear in Appendix B).
Then consider the following update rule for the left guard neurons:
( 1) a (gn + (dn(1) - (t) - (gh(() + Po' (L)) + 1)),
(15)
( = <(p + [0))))(((00) ())) + dn()) P 20) - (c)) = (2 (p + 1)
(16)
dR(t)= - -202(t) - -2c
(17)
where gz =
(1) 9 (1) = 0. It can be verified that gr (4) = h((tt)/(pp
as defined by 12). completing the proof for (t).
Example. Assume d = L and h(1sz)) = Then gL.
(0((2)1((pp]))) and -
g]( =
o' (2) (2) = 0. On the second stage, (3) = -01/0-1)-110-11)00000001111 =
a(1-p) p) = 0, and g0 (3) = (2- 1) = On the third stage, (0((4==((0+///+))===>>0))= as required.
The full proof appears in Appendix B.
Similar to Corollary I.1 it follows that:
Corollary 2.1. Given Turing Machine M, there exists an injective function p X (Q", Q Q*) and an n-neuron p-precision (in base (21l) RNN with two growing memory modules Tw.
(Q" Q+, Q*) + (Q" "*,Q**)), Q²), where n. 2|11| + [log [Q[ + [Q[[1] + 19 and p Z 2, such that for all instantaneous descriptions I E X. the following holds: If PM (z) is defined, then
((Txo(((=)) P²)()).
(18)
and (x(()) is not defined, then Tw (wo(p(() in T steps by M, then Tw (w.(((x)) (p(x)) is computed in 3T steps by the RNN
(p(x)) is also not defined. If (P)(())) is defined and computed
Finally, applying Corollary 2.1 to U6,4, we obtain:
Corollary 2.2. There exists a 54-neuron p-precision (in base 8) RNN with two growing memory modules that can simulate any Taring Machine in O where T is the number of steps required for the Turing Machine to compute the result and 2 2.
The architecture of the Turing-complete 54-neuron RNN (fully described in the proof of Theorem 2
is depicted in Figure
4.1 Relationship of the Growing Memory Modules with Stack-augmented RNNs
The proposed growing memory module belongs to the generic class of stack-augmented RNNs, which refers to any RNNs augmented with stack-like mechanism. Many different forms of stack-
augmented RNNs have been proposed III 12 13 14 15). Given the simplicity of the design,
8

---

Layer 4
states (3)
temp tapes (4)
buffers (4)
Layer
entries (23)
push-pop (4)
CC
Layer 2
readings (6)
tapes (2)
guards(6)
Left-tupe Right-tape stack stack
Layer
stages (2)
Figure 2: The architecture of the Turing-comples 54-neuron RNN with two growing memory modules. Blue (solid) lines denote bottom-up connections, and red (dotted) lines denote top-down connections. Neurons grouped according to their respective functions. Notable neurons include: state neurons represent the current state; tape neurons represent the tape symbols near the read/write head using fractal encoding; guard neurons represent the number of symbols residing in the RNN; push and pop neurons control the pushing and popping of left-tape and right-tape stacks; stage neurons represent the current stage and inhibits computation of other neurons if the neurons do require updating in stage. A detailed description of these neurons can be found in Appendix B.
the growing memory module represents the foundation form of these stack-augmented RNNs. easy to show that these aagk-au RNNs can simulate the growing memory module in linear time. For example, the growing memory modules can be simulated by the neural stack [I]] as follows. For pushing operation, 0; in the neural stack u(t) the growing memory module, and de in the neural stack to 1(u(t) > 0} in the growing memory module. For popping operation, set u, in the neural stack 1/o(t) = 1} in the growing memory module. Therefore, the proof for the Turing completeness of counded-precision extend to other stamk-ad RNNs. That is, bounded -peedisior augmened RNNs are also Turing-complete.
RNNs with growing memory modules can
Different from other stack-augmented RNNs, the proposed growing memory modules simple mechanism to control pushing and popping, as only the top neurons in the stack are included in the RNNs. This allows theories relating growing memory modules be easily extended to other forms of RNNs.
5 Bounded-Preeision RNNs and Space- Bounded Turing Machines
As discussed above, it is inefficient to update all neurons that encode tape information, but if one still wants remove the growing memory modules and focuses purely on counded-precision RNN only, then the resulting network can simulate space- bouee-b Turing Machines (that is, Turing Machines with bounded-size tape) only.
Theorem 3. Given Turing Machine M with bounded tape of size F, there exists an injective function p X + Q and an n-neuron p-precision (in base [2]]) RNN Tw.b Q" + Q", where O(FFpp) and pudp2. such that for all instantaneous descriptions x X,
p- (TH = (m)
(19)
The proof, which is constructive, can be found in Appendix C. The general idea of the proof is to implement the growing memory module in Section 4 by RNN well and place all neurons inside the RNN. The theorem shows that the number of neurons required to simulate a space-bounded Turing Machine correlates with the tape size.
To simulate a Turing Machine with an unbounded tape, we would need to add neurons to the RNN once the read/write head reaches the end of the memory. To be specific, say RNN has

---

unbounded number of neurons if the RNN either has infinite number of neurons to start with or can iecrasse the number neurons after each update step depending on the neurons' values. The UTM that simulates any Turing Machine in fast way was described in [2]] which does so with
only (T log T) slowdown. While this UTM has multiple tapes, Theorem 3 can be generalized to multipletappe Turing Machines easily. We now obtain:
-ereiddinrriiooon RNN that can simulate any Turing Machine in (T log T), where T is the number of steps required for the Turing Machine to compute the result.
Corollary 3.1. There exists an umbounded-neurg
6 Discussion and Conclusion
To construct Turing-complete RNN, we have to incorporate some encoding for the unbounded number of symbols on the Turing tape. This encoding can done by: (a) unbounded precision of some neurons (Theorem T. (b) an unbounded number of neurons (Theorem (3), or (c) a separate growing memory module (Theorem D The main contribution of this paper is spelling out the details of (c), which provides a practical way to construct RNN that runs any given algorithms. We prove the Turing completeness of a 40-neuron unbounded-preeinn Turing-complett RNN to date. We analyze the relationship between the number of neurons and the precision of an RNN when simulating Turing Machine. Most importantly, we propose 54-neuron counded-precision RNN with growing memory modules that is Turing completeness can be extended to stack-augmented RNNs in general.
RNN, which the smallest
and this proof of
This paper focuses on the computational capabilities and representability of symbolic and sub- symbolic processing via stack-augmented RNNs; does not engage yet with methods to train them. Since growing memory modules are not differentiable, we cannot train them directly by the frequently used error backpropagation algorithm. One may want to construct a differentiable version of the modules, or alternatively use different learning rule (e.g., REINFORCE (22)) to deal with the discrete pushing and popping operations. Understanding methods to train growing memory modules, incorporate symbolic information into the sub-symbolic representation efficiently, and retrieve both symbolic and non-symbolic information are the next steps towards the goal of combining symbolic and sub-symbolic capabilities in an adaptive and applicable manner.
References
[1] Hava T Siegelmann and Eduardo D Sontag. On the computational power of neural nets. Journal of computer and system sciences, 50(1):132-150, 1995.
[2] Hava T Siegelmann. Computation beyond the turing limit. Science, 268(5210):555-448. 1995.
[3] Hava Siegelmann. Neural networks and analog computation: beyond the Turing limit. Springer Science & Business Media, 2012.
[4] Georg Kuhn, Heather Diekinson-Ansow and Fred Gage. Neurogenesis the dentate gyrus of the adult rat: age-related decrease of neuronal progenitor proliferation. Journal of Neuroscience, 16(6):2027-200 1996.
[5] Arturo Alvarez-Buylla and Jose Manuel Garcia Verdugo. Neurogenesis in adult subventricular zone. Journal of Neuroscience, 22(3):629-634, 2002.
[6] David Marr, David Willshaw, and Bruce MeNaughton. Simple memory: theory for archicortex. In From the Retina the Neocortex, pages 59-128. Springer, 1991.
[7] MW Jung and BL. McNaughton. Spatial selectivity of unit activity in the hippocampal granular layer. Hippocampus, 3(2):165-182 1993.
[8] Gerd Kempermann, Georg Kuhn, and Fred H Gage. Experience-indee induced ncurogenesis in the senescent dentate gyrus. Journal of Neuroscience, 18(9)3200-32122 1998.
[9] Georg Elias Müller and Alfons Pilzecker. Experimentelle beiträge zur lehre vom gedüchuniss, volume 1. JA Barth, 1900.
10

---

[10] James L McGaugh. Memory-a a century of consolidation. Science, 287(5451) 2514 2000.
[11] Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. Advances in neural information processing systems, 28:1828-1836 2015.
[12] Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. Advances in neural information processing systems, 28:190-199 2015.
[13] Guo-Zheng Sun, C Lee Giles, Hsing-Hen Chen, and Yee-Chun Lee. The neural network pushdown automaton: Model, stack and learning simulations. arXiv preprint arXiv:1711.05738. 2017.
[14] Ankur Arjun Mali, Alexander G Ororbia II, and C Lee Giles. A neural state pushdown automata. IEFE Transactions on Artificial Intelligence, 13)):193-205, 2020.
[15] Ankur Mali, Alexander Ororbia, Daniel Kifer, and Lee Giles. Recognizing long grammati- cal sequences using recurrent networks augmented with an external differentiable stack. In International Conference on Grammatical Inference, pages 130-153. PMLR, 2021.
[16] Joe Kilian and Hava T Siegelmann. The dynamic universality of sigmoidal neural networks. Information and compulation, 128(1):48-56, 1996.
[17] Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv: 2014.
(18) Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 53877626)441-477 2016.
[19] Turlough Neary and Damien Woods. Four small universal turing machines. Fundamenta Informaticae, 9111::123-144 2009.
[20] J Nicholas Hobbs and Hava Siegelmann. Implementation of universal computation via small recurrent finite precision neural networks. In 2015 International Joint Conference on Neural
Networks (IJCNN), pages 1-5. IEEE, 2015.
[21] Fred C Hennie and Richard Edwin Stearns. Two-tape simulation of multitape turing machines. Journal of the ACM (JACM), 13(4):533 3-4:5633366., 1966.
[22] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):299-25,, 1992.


Reviews:
[{"review_id": "y0RsqF7e2_", "reviewer": "Reviewer_fUf1", "summary": "This paper analyses the Turing completeness of recurrent neural networks, and proposes a memory-augmented RNN architecture reminiscent of existing stack RNNs. \n\nSpecifically:\n\nFirst, a construction for simulating any Turing machine with an unbounded-precision RNN is presented, in which effectively the left and right sides of the Turing machine's tape (with respect to its head) are encoded as two 'stacks' in the RNN. This construction is analysed and requires less simulation time than that of Siegelmann and Sonntag [1] (3T instead of 4T+O(used tape length), where T is computation time of the simulated Turing machine). Additionally the authors analyse the exact precision of the neurons necessary (as function of the simulated Turing machine's computation length) for the simulation (as opposed to previous works, which simply note a requirement for infinite precision).\n\nSecond, noting that it is unavoidable that the precision must grow when simulating longer Turing machine computations (to maintain the contents of the tape), the authors propose augmenting the RNN with a dynamic memory module, such that the neurons themselves may have constant, bounded, precision. They theoretically analyse their proposed architecture and show how a Turing machine may be simulated in it. \n\n", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The construction of this dynamic memory module is  reminiscent of recent work on \"stack RNNs\" [2-4]. Much like the model proposed in this paper, stack RNNs push and pop to an external 'memory module' (generally referred to as a 'stack'), which allows them to simulate pushdown automata (although most of these models do not discuss 2 stacks as used here, their constructions can certainly be generalised to multiple stacks, and so it is conceivable that once sufficient success is achieved with one stack then there would be a shift to 2 stacks or more). Much of the challenge with these stack-RNNs is making this stack differentiable, so that the model can 'learn' whether it should be pushing or popping from its stack during training (i.e., the push and pop operations need to be differentiable). Multiple different methods are considered to attain this quality (see partial list of works below). In this paper it does not seem that this challenge has been addressed, and indeed the current push and pop operations appear to be happening discretely, i.e., I do not think it is possible to train the current architecture with SGD. \n\nAnother thing I would like to note is that it is not generally convincing to propose a new architecture without some practical evaluation. While the theoretical power of this architecture is shown in this work (a construction for simulating any Turing machine), its ability to learn any language, formal or natural, unfortunately has not been evaluated. I suspect that this is also why the challenge of making differentiable push and pop operations has gone unnoticed in this work.\n\nTo conclude:\n1. In itself the construction of a Turing machine simulation in RNNs is not new (e.g., it has already been done in [1]), but I appreciate the analysis showing that this construction is faster than previous constructions, and moreover the analysis of necessary precision per Turing machine and input, which (if I remember correctly) is not present in previous such works. However, I do not see this result as sufficient for accepting this paper alone: I believe the main interest of the community in this line of results is more the fact that RNNs *can* simulate Turing machines, rather than how efficiently they can do so. (Maybe if the improved construction was significantly more efficient, that would be nice, but this is only a constant-factor improvement: from 5T (we can say that the tape will never be longer than T) to 3T).\n2. I appreciate the attempt to create a memory augmented network. However at this point I would only want to accept new architectures after they have been evaluated, and this one has not (after all, if we wanted only to *encode* Turing machines in them, then we can simply use those Turing machines directly instead). Moreover I suspect that if we do come to train this architecture, we will hit many obstacles (see e.g. discreteness of push and pop operations, above).\n\nIf the authors pursue making this architecture differentiable, I strongly suggest they read more about stack RNNs (I am not an expert on these, so I give only a partial list), where I think they will find a lot of inspiration. Either way, I ask that they evaluate their architecture, and moreover compare it to existing stack RNNs and at the very least vanilla RNNs (including variants such as GRUs and LSTMs), before they resubmit.\n\n\n\nreferences:\n[1] On the computational power of neural nets (Siegelmann and Sonntag)\n\n[2] Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets (Joulin and Mikolov)\n\n[3] The Neural Network Pushdown Automaton: Model, Stack and Learning Simulations (Sun, Giles, Chen, Lee)\n\n[4] Learning to Transduce with Unbounded Memory (Grefenstette, Hermann, Suleyman, Blunsom)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none relevant", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "jPqO16WLA7Q", "reviewer": "Reviewer_jTHy", "summary": "This work proposes a dynamic-growing memory module for RNNs, which serves to simulate Turing machines of bounded precision. \nFirst, the authors prove how to encode a Turing machine to an unbounded precision RNN. The encoding uses fractal encoding for symbols, like previous work, and it replaces each step of the Turing machine as 3 steps in the RNN. Leaning in the work of [14], they prove that there is a 40-neuron unbounded precision RNN to simulate any Turing machine (i.e., showing Turing-completeness). Next, they consider the previous unbounded-precision definitions with the memory module to obtain a bounded-precision RNN.The memory module is a stack of neurons, that requires two neurons in the RNN to control it: push and pop. Then it is proven that the proposed bounded-precision RNN utilizes 2 of these stack to simulate a Turing machine. Further, each stack is divided in groups of $p$ neurons, such that the most active neurons are in the RNN (near to each side of the memory head in the Turing machine). Leaning again in [14], they can show that there is a 54-neuron with $p$-precision RNN with 2 growing memory module, that can simulate any Turing machine. This proves Turing-completeness of the precision-bounded RNN. Finally, they remove the growing memory module and simulate the memory within the neurons of an RNN, showing that an infinite number of bounded-precision RNN can simulate any Turing machine. the work finishes with an interesting discussion of the results and limitations.   \n", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theoretical results presented in this work are novel to the best of my knowledge. The ideas to build the mappings are simple and lean, citing related work as needed. The idea of using stacks with RNNs is not novel, the authors may want to have a look at the works [1],[2],[3] that apply it in practice (and require a differentiable stack).\n\nThe paper is clear and proofs look sound. The claims are properly supported and discussed, facilitating the understanding of the work. The flow of the text read smoothly (despite the number of symbols). On one hand, the results improve over the existing state-of-the-art in terms of the number of neurons for unbounded precision. On the other hand, shows that bounded-precision RNNs with memory are Turing-complete. Section 5 and the final discussion are a very interesting ending to this paper. A little more detail for Figure 2 in the main paper will be highly appreciated by this reader.\n\nSignificance: Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work? Does it advance the state of the art in a demonstrable way? Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n\nThis work is clearly very important to the NeurIPS community and the deep learning community in particular. This work does not only make solid theoretical contributions where needed, but also emphasizes the importance of memory augmentation in RNNs. \n\nIt was very pleasant to read this paper and the nice results. Thank you! \n\n\nMinor:\n* Line 112: \"without loss of generosity\" --> \"without loss of generality\"\n\nReferences\n\n[1] Mali et al. \"Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack\", 2020.\n\n[2] Mali et al. \"The Neural State Pushdown Automata\", IEEE Transactions on Artificial Intelligence, 2020.\n\n[3] Suzgin et al. \"Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages\", 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact have been addressed to the best of my understanding.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None to the best of my knowledge.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "hwgJkwMqLEj", "reviewer": "Reviewer_S4CZ", "summary": "This theoretical work shows the existence of un-bounded precision RNNs for simulating turing machines, with growing/shrinking memory module. Although the paper seems quite interesting and well-written, I am afraid I don't have the right background to make an accurate judgment on the novelty and potential impact of the work. I share few thoughts below, similarly due to lack-of-knowledge and limited reviewing time I was not able to check the proofs. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n- Most of the results seems novel and paper is very well-written.\n\n# Questions/Possible-Limitations\n- Given proof shows the existence of bounded/non-bounded precision RNNs with particular size (for simulating turing machines) and these networks are not-trainable (due to non-differentiable parts). As mentioned in the conclusion this is a limitation and I wonder (apart from inherit value of it) what other values the proposed architecture might bring to the field (practical/theoretical). This part is not clear to me and I think it would be nice to discuss this in the rebuttal. Can we train similar architectures if we make growing differentiable? What would that enable that is not already enabled? \n- I wonder whether copying experiments (like in NTM paper) is appropriate here. It would be nice to have a working implementation of proposed RNN. \n\n## Minor\n- Without loss of generosity, -> generality. \n- \"Implementing Neural Turing Machines\" https://arxiv.org/abs/1807.08518 Might be a relevant work.\n- \"https://www.nature.com/articles/nature20101\" Same with this. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work, so no societal impact I can think of. Authors also discuss limitations at the end, which I appreciated. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2E03lNFRApz", "reviewer": "Reviewer_9x9n", "summary": "The paper presents 3 main theoretical results:\n- An RNN with 40 unbounded-precision neurons is Turing-complete.\n- An RNN with 54 bounded-precision neurons and two stacks is Turing-complete.\n- An RNN with a finite number of bounded-precision neurons and no stacks can simulate a Turing machine with a bounded tape, where the maximum tape length is related to the number of RNN neurons.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has a limited practical significance.\n\nAbout unbounded-precision neurons: \n- Unbounded-precision is not practical.\n\nAbout the RNN with bounded-precision neurons and two stacks:\n- It is well known that a finite-state machine with two stacks is Turing-complete.\nAnd an RNN with bounded-precision is a finite-state machine.\n- The proposed stacks are not differentiable.\n- The original Neural Turing Machine was already Turing-complete, if using an unbounded tape.\nThe location-based addressing allows to shift the tape. By shifting a one-hot attention pattern, only the attended part of the tape needs to be accessed. This was practically used by Spatial Transformer Networks (NeurIPS 2015) and later works.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main review for limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has gone through deep discussions among the reviewers. Assuming all the proofs are correct, a major weakness of this paper is its disconnection with the community. The stack-RNNs and related models are not discussed in the paper. It is unclear what the community can learn from this work. However, the contribution that fixed precision RNN models with stacks are as powerful as a Turing machine is novel and significant. The analyzed RNN model is more or less practical. The theory may have a wide impact. Meanwhile, Meanwhile, the authors are highly encouraged to complete the connection to existing related work.
Decision: Accept (Poster)