summaries: The paper presents 3 main theoretical results: - An RNN with 40 unbounded-precision neurons is Turing-complete. - An RNN with 54 bounded-precision neurons and two stacks is Turing-complete. - 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. This paper analyses the Turing completeness of recurrent neural networks, and proposes a memory-augmented RNN architecture reminiscent of existing stack RNNs.   Specifically:  First, 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).  Second, 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.    This work proposes a dynamic-growing memory module for RNNs, which serves to simulate Turing machines of bounded precision.  First, 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.     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. 
abstractText: Previous works have proved that recurrent neural networks (RNNs) are Turingcomplete. 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 boundedprecision RNNs, revisiting and extending the theoretical foundations of RNNs.
authors.name: Stephen Chung
authors.name: Hava Siegelmann
references.authors: Hava T Siegelmann Eduardo D Sontag
references.title: On the computational power of neural nets
references.venue: Journal of computer and system sciences,
references.authors: Hava T Siegelmann
references.title: Computation beyond the turing limit
references.venue: Science, 268(5210):545–548,
references.authors: Hava T Siegelmann
references.title: Neural networks and analog computation: beyond the Turing limit
references.venue: Springer Science & Business Media,
references.authors: H Georg Kuhn Heather Dickinson-Anson Fred H Gage
references.title: Neurogenesis in the dentate gyrus of the adult rat: age-related decrease of neuronal progenitor proliferation
references.venue: Journal of Neuroscience,
references.authors: Arturo Alvarez-Buylla Jose Manuel Garcıa-Verdugo
references.title: Neurogenesis in adult subventricular zone
references.venue: Journal of Neuroscience,
references.authors: David Marr David Willshaw Bruce McNaughton
references.title: Simple memory: a theory for archicortex
references.venue: In From the Retina to the Neocortex,
references.authors: MW Jung BL McNaughton
references.title: Spatial selectivity of unit activity in the hippocampal granular layer. Hippocampus
references.authors: Gerd Kempermann H Georg Kuhn Fred H Gage
references.title: Experience-induced neurogenesis in the senescent dentate gyrus
references.venue: Journal of Neuroscience,
references.authors: Georg Elias Müller Alfons Pilzecker
references.title: Experimentelle beiträge zur lehre vom gedächtniss, volume 1
references.venue: JA Barth,
references.authors: Edward Grefenstette Karl Moritz Hermann Mustafa Suleyman Phil Blunsom
references.title: Learning to transduce with unbounded memory
references.venue: Advances in neural information processing systems,
references.authors: Armand Joulin Tomas Mikolov
references.title: Inferring algorithmic patterns with stack-augmented recurrent nets
references.venue: Advances in neural information processing systems,
references.authors: Guo-Zheng Sun C Lee Giles Hsing-Hen Chen Yee-Chun Lee
references.title: The neural network pushdown automaton: Model, stack and learning simulations
references.venue: arXiv preprint arXiv:1711.05738,
references.authors: Ankur Arjun Mali Alexander G Ororbia II C Lee Giles
references.title: A neural state pushdown automata
references.venue: IEEE Transactions on Artificial Intelligence,
references.authors: Ankur Mali Alexander Ororbia Daniel Kifer Lee Giles
references.title: Recognizing long grammatical sequences using recurrent networks augmented with an external differentiable stack
references.venue: In International Conference on Grammatical Inference,
references.authors: Joe Kilian Hava T Siegelmann
references.title: The dynamic universality of sigmoidal neural networks
references.venue: Information and computation,
references.authors: Alex Graves Greg Wayne Ivo Danihelka
references.title: Neural turing machines
references.venue: arXiv preprint arXiv:1410.5401,
references.authors: Alex Graves Greg Wayne Malcolm Reynolds Tim Harley Ivo Danihelka Agnieszka Grabska- Barwińska Sergio Gómez Colmenarejo Edward Grefenstette Tiago Ramalho John Agapiou
references.title: Hybrid computing using a neural network with dynamic external memory
references.authors: Turlough Neary Damien Woods
references.title: Four small universal turing machines
references.venue: Fundamenta Informaticae,
references.authors: J Nicholas Hobbs Hava Siegelmann
references.title: Implementation of universal computation via small recurrent finite precision neural networks
references.venue: In 2015 International Joint Conference on Neural Networks (IJCNN),
references.authors: Fred C Hennie Richard Edwin Stearns
references.title: Two-tape simulation of multitape turing machines
references.venue: Journal of the ACM (JACM),
references.authors: Ronald J Williams
references.title: Simple statistical gradient-following algorithms for connectionist reinforcement learning
references.venue: Machine learning,
sections.heading: 1 Introduction
sections.text: Symbolic (such as 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 to combine symbolic and sub-symbolic capabilities is by enabling the running of algorithms on a neural substrate, which means a neural network that can simulate a Universal Turing Machine (UTM). Previous works [1, 2, 3] have shown that this is possible – there exists a recurrent neural network (RNN) that can simulate a UTM. These proofs assumed a couple of neurons with unbounded precision that equals the number of symbols used in the Turing tape. Here we provide an alternative simulation of a UTM by RNNs with bounded-precision neurons only.
  The general idea works as 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, a 54-neuron bounded-precision RNN is constructed that can simulate any Turing Machine.
  Our proposed growing memory modules are 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 are 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 (NeurIPS 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 is 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, a process by which short-term memory is transformed into long-term memory [9, 10]. Compared to short-term memory, long-term memory is more long-lasting and robust to 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 a mechanism to store information stably.
  Growing memory modules share similarities with other stack-augmented RNNs [11, 12, 13, 14, 15]. In neural stacks [11], the RNN outputs two continuous scalars that control the strength of pushing and popping operations, and the stack is made differentiable by adding a strength vector. In stack RNNs [12] and DiffStk-RNN [15], the RNN outputs the probability vector corresponding to pushing, popping, and no 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 to pushing. NSPDA [14] uses a discrete-valued action neurons to control pushing and popping operations. In contrast to these models, growing memory modules have a 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 a 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.
  A Turing-complete RNN that is fully differentiable was introduced in 1996 [16]; this feature is a prerequisite to have the network trainable by gradient descent. It was followed by the Neural Turing Machine (NTM) [17] 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-precision NTMs and differentiable neural computers are not Turing-complete due to the fixed-sized memory bank, but they can simulate space-bounded Turing Machines (see Section 5).
  Simulation of a Turing Machine by an RNN with growing memory modules represents a 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 time and independent of the memory size. By showing how to simulate a Turing Machine with a bounded-precision RNN and thereby constructing a bounded-precision RNN that can run any algorithms, our paper proposes a 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 to simulating a Turing Machine with unbounded-precision RNNs and shows the existence of a 40-neuron unbounded-precision RNN that is Turing-complete. Section 4 presents the growing memory modules and proves the existence of a 54-neuron bounded-precision RNN with two growing memory modules that is Turing-complete. Section 5 relates the number of neurons and the precision of RNNs when simulating Turing Machines. Section 6 concludes the paper.
sections.heading: 2 Background and Notation
sections.text: A Turing Machine is a 7-tuple M = (Q,Σ,Γ, δ, q0, ♯, F ), where Q is a finite set of states, Σ is a finite set of input symbols, Γ is a finite set of tape symbols (note that Σ ⊂ Γ), δ : Q×Γ → Q×Γ×{L,R}
  is the machine’s transition rule, q0 ∈ Q is the initial starting state, ♯ is the blank symbol (note that ♯ ∈ Γ but ♯ /∈ Σ), and F ⊂ Q is the set of final state. We only consider deterministic Turing Machines in this paper.
  The instantaneous description (or the configuration) of a Turing Machine is typically defined as a tuple of state, tape, and the location of the read/write head. However, we use a slightly different definition in the paper. We define the left-tape symbols (or the left tape in short), denoted as sL, to 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 sR, 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 sR (that is, the left tape is reversed in the representation) and the blank symbols at the two ends are omitted. Therefore, the length of sL and sR combined equals to the number of symbols used in the Turing tape in each step (that is, unbounded but not infinite). Since sL and sR encode both the tape and the location of the read/write head, we define the instantaneous description of a Turing Machine as a 3-tuple (q, sL, sR) ∈ (Q,Γ∗,Γ∗), where q denotes the state, sL denotes the left-tape symbols, and sR 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 := (Q,Γ∗,Γ∗). 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 = (q, sL, sR) be the input configuration, sL,(1) denote the first symbol in sL and sR,(1) denote the first symbol in sR. The transition is defined by the 3-tuple (q′, y, d) = δ(q, sL,(1)); 2. Replace the state of the machine q with q′ and the first symbol in sL by y; 3. Move the symbol in sL,(1) to become the new sR,(1) if d = L, and move sR,(1) to become the new sL,(1) if d = R (if there are no symbols left in sL or sR for moving, append a blank symbol ♯ to it before moving). Denote the left-tape symbols and the right-tape symbols after 2. and 3. by s′L and s ′ R respectively. Then PM(x) = (q′, s′L, s′R) represents one transition of the Turing Machine M from one configuration to the next. The partial input-output function of M, denoted as P∗M : X → X , is defined by applying PM repeatedly until q ∈ F , and is undefined if it is not possible to have q ∈ F by applying PM repeatedly. A recurrent neural network (RNN) is a neural network consisting of n neurons. The value of neuron i at time t ∈ {1, 2, ...}, denoted as xi(t) ∈ 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 σ, i.e. xi(t) = σ( ∑n j=1 wijxj(t− 1) + bi), where wij are the weights and bi is the bias; or in vector form:
  x(t) = σ(Wx(t− 1) + b), (1)
  where x(t) ∈ Qn, W ∈ Rn×n and b ∈ Rn. This defines a mapping TW,b : Qn → Qn which characterizes an RNN. For simplicity, we consider the saturated-linear function in this paper; that is:
  σ(x) :=  0 if x < 0, x if 0 ≤ x ≤ 1, 1 if x > 1.
  (2)
  Thus, x(t) ∈ (Q ∩ [0, 1])n for all t > 0. We say that a neuron xi(t) has precision p in base b if for all t > 0, xi(t) can be expressed as∑p
  l=1 a(l)(t)∏l
  j=1 c(j)(t) for some strings a(t) ∈ {0, 1, ..., b}p and c(t) ∈ {1, ..., b}p.
  For a string a, we use a(i) to denote the ith symbol in a and a(i:j) to denote the string a(i)a(i+1)...a(j). For a function f that maps from a set Y to a subset of Y, we use fn to denote the nth iterate of f where 1 ≤ n < ∞. For any two vectors x ∈ Rm,y ∈ Rn, we use x ⊕ y ∈ Rm+n 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.
sections.heading: 3 Turing Completeness of Unbounded-Precision RNNs
sections.text: To simulate a Turing Machine M by an RNN, we first consider how to encode the instantaneous description (q, sL, sR) ∈ X by a vector of rational numbers. For the state q ∈ Q, we encode it with ⌈log2 |Q|⌉ binary values, denoted as ρ(q) : Q → {0, 1}⌈log2 |Q|⌉, with each possible combination of binary values representing a specific state.
  Example. Let Q = {1, 2, 3, 4, 5, 6}. We can encode it by ⌈log2 |Q|⌉ = 3 binary values, with ρ(q)(1) = [0, 0, 0], ρ(q)(2) = [0, 0, 1], ρ(q)(3) = [0, 1, 0], ρ(q)(4) = [0, 1, 1], ρ(q)(5) = [1, 0, 0], and ρ(q)(6) = [1, 0, 1].
  For the left tape sL ∈ Γ∗ and the right tape sR ∈ Γ∗, we use fractal encoding in two rational numbers, as recommended in [1, 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 Γ are encoded into numbers {1, 3, 5, ..., 2|Γ|− 1} and that the blank symbol ♯ is encoded by 1. Then, define the fractal encoding ρ(s) : Γ∗ → Q by:
  ρ(s)(y) :=  |y|∑ i=1 y(i) (2|Γ|)i + 1 (2|Γ|)|y| · (2|Γ| − 1) . (3)
  Example. Let Γ = {1, 3, 5, 7}, sL = (3, 5, 7, 3, 5), and ♯ = 1. Then ρ(s)(sL) = 38 + 5 82 + 7 83 + 3 84 +
  5 85 + 1 86 + 1 87 + 1 88 + ... = 3 8 + 5 82 + 7 83 + 3 84 + 5 85 + 1 85·7 . The last term in (3) represents the infinite 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 a Turing Machine has an 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 to remove this unbounded-precision assumption in Section 4.
  Finally, we encode the value of the top symbol in each tape neuron, sL,(1) and sR,(1), by a binary tuple ρ(r) : Γ → {0, 1}|Γ|−1:
  ρ (r) i (y) := 1{y > 2i} (1 ≤ i ≤ |Γ| − 1). (4)
  That is, the i coordinate of ρ(r)(y) is 1 if and only if the symbol y has a value larger than 2i, and is 0 otherwise.
  Example. Let Γ = {1, 3, 5, 7}. Then ρ(r)(1) = [0, 0, 0], ρ(r)(3) = [1, 0, 0], ρ(r)(5) = [1, 1, 0], and ρ(r)(7) = [1, 1, 1].
  Combining the above discussion, we define the encoding function of configurations ρ : X → Q2|Γ|+⌈log2 |Q|⌉+|Q||Γ|+5 by:
  ρ(q, sL, sR) = ρ (q)(q)⊕ ρ(s)(sL)⊕ ρ(s)(sR)⊕ ρ(r)(sL,(1))⊕ ρ(r)(sR,(1))⊕ 0, (5)
  where 0 is a zero vector of size |Q||Γ|+ 5. Let ρ−1 : ρ(X ) → X be the inverse function such that ρ−1(ρ(x)) = x for all x ∈ X (note that ρ is injective, i.e. ρ(x) = ρ(x′) implies x = x′); we call ρ−1 the decoder function.
  It should be noted that ρ(q)(q) ⊕ ρ(s)(sL) ⊕ ρ(s)(sR) is sufficient to decode the instantaneous description. We include ρ(r)(sL,(1))⊕ ρ(r)(sR,(1))⊕ 0 only because it facilitates the full simulation on the RNN. This completes the construction of the encoding function.
  Given an instantaneous description x ∈ X , we initialize the neurons in an RNN with values ρ(x). 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: Theorem 1. Given a Turing Machine M, there exists an injective function ρ : X → QN and an n-neuron unbounded-precision RNN TW,b : Qn → Qn, where n = 2|Γ|+ ⌈log2 |Q|⌉+ |Q||Γ|+ 5, such that for all instantaneous descriptions x ∈ X ,
  ρ−1(T 3W,b(ρ(x))) = PM(x). (6)
  Proof. A sketch of the proof is as follows. Neurons in the RNNs are grouped by their function. Tape neurons, initialized with ρ(s)(sL) and ρ(s)(sR), encode the tape in fractal encoding. Readout neurons, initialized with ρ(r)(sL,(1)) and ρ(r)(sR,(1)), encode the first symbol in the left and the right tape. State neurons, initialized with ρ(q)(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 0, compute the combination of the state and the symbol under the head. Since this combination fully determines the next transition, we use it to 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 instantaneous description x by the encoder function ρ, apply the RNN three times T 3W,b, and decode the values back by ρ−1 to obtain PM(x), 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 1 repeatedly, we simulate a Turing Machine with an RNN in a linear time. To be specific, the partial input-output function of an RNN, denoted as T ∗W,b : QN → QN , is defined by applying T 3W,b repeatedly until q ∈ F (where q is the state that the RNN simulates), and is undefined if it is not possible to have q ∈ F by applying T 3W,b repeatedly. Based on this definition and Theorem 1, it follows that:
  Corollary 1.1. Given a Turing Machine M, there exists an injective function ρ : X → Qn and an n-neuron unbounded-precision RNN TW,b : Qn → Qn, where n = 2|Γ|+ ⌈log2 |Q|⌉+ |Q||Γ|+ 5, such that for all instantaneous descriptions x ∈ X , the following holds: If P∗M(x) is defined, then
  ρ−1(T ∗W,b(ρ(x))) = P∗M(x), (7)
  and if P∗M(x) is not defined, then T ∗W,b(ρ(x)) is also not defined. If P∗M(x) is defined and computed in T steps by M, then T ∗W,b(ρ(x)) is computed in 3T steps by the RNN.
  Corollary 1.1 shares similarities with Theorem 1 in [1]. However, our theorem states that 3T , instead of 4T , 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 Γ in the Turing Machine.
  A small UTM with 6 states and 4 symbols, denoted by U6,4, was proposed [19] and can simulate any Turing Machine in time O(T 6), where T is the number of steps required by the Turing Machine (the one to be simulated) to compute the result. As U6,4 is also a Turing Machine, we apply Corollary 1.1 to simulate U6,4, leading to a Turing-complete RNN. Plugging in |Q| = 6 and |Γ| = 4, we obtain the following result:
  Corollary 1.2. There exists a 40-neuron unbounded-precision RNN that can simulate any Turing Machine in O(T 6), where T is the number of steps required for the Turing Machine to compute the result.
  It should be noted that [1] 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.
sections.heading: 4 Turing Completeness of Bounded-Precision RNNs with Growing Memory
sections.text: 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 ⌈|sj |/p⌉ neurons using fractal encoding, where j ∈ {L,R}. We do this by encoding every p symbols of the tape into a single neuron. Since most of these neurons do not require updates, just like symbols far from the read/write head in a Turing tape, we propose to store them in a separate growing memory module organized in a stack-like manner:
  Definition 1. A growing memory module is a stack of non-zero neurons with push and pop operations controlled by two neurons in an RNN, denoted as push neuron 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) > 0, then a new neuron with the value u(t) is pushed to the stack and u(t) is set to 0; (ii) if o(t) = 0 and the stack is 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(t) = 0 and the stack is empty, then o(t) is set to a default value c.
  An RNN with a growing memory module is a mapping TW,b : (QN ,Q∗) → (QN ,Q∗) where the first element of 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 an 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 a mapping TW,b : (QN ,Q∗,Q∗) → (QN ,Q∗,Q∗). We can view the growing memory module as a way of dynamically pointing to a sequence of non-zero neurons appended by one zero neuron. o(t) can be viewed as the pointer for the last non-zero neuron in the sequence, and u(t) can be viewed as the pointer for the zero neuron at the beginning of the sequence; see Figure 1.
  With two growing memory modules (one for the left tape and one for the right tape), we can construct an RNN with bounded-precision neurons that can simulate any Turing Machine. We first describe how to encode the instantaneous description (q, sL, sR) ∈ X by a vector of rational numbers and two stacks, with which an RNN and its growing memory modules can be initialized. In the following discussion, we assume that all neurons have precision bounded by p ≥ 2 in base 2|Γ|; that is, each neuron can encode p symbols at most.
  Both the state q and the top symbols sL,(1), sR,(1) are encoded with binary values as in Section 3. For the tape sj (j ∈ {L,R}), we define the fractal encoding ρ(s) : Γ∗ → Q by:
  ρ(s)(y) := |y|∑ i=1 y(i) (2|Γ|)i , (8)
  which is similar to (3) except for the encoding of infinite blank symbols. Then, we encode the tape sj into a stack of neurons as follows: First, encode the rightmost p symbols (the ones farthest from the read/write head) with ρt and push it to an empty stack, denoted as Mj . Then, encode the next
  rightmost p symbols and push it to Mj again, and repeat until at least one and at most p symbols remain in the tape. Denote this encoding function for the tape as ρ(M) : Γ∗ → Q∗. The remaining symbols in the tape, denoted as sj,(1:h(|sj |)), where h(y) := ((y − 1) mod p) + 1, will be encoded with fractal encoding ρ(s) 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 (sj,(1:h(|sj |))) reside in the RNN. If the number of symbols residing in the RNN reaches 0 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. It is interesting to note that the kth neuron in the stack (from the top) requires at least kp steps of the Turing Machine before it may be updated, so 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 Γ = {1, 3, 5, 7}, sL = (3, 5, 7, 3, 5, 5, 3, 7) and p = 3. Then the number of symbols to remain in the RNN is 2 and they are encoded by ρ(s)(sL,(1:h(|sL|))) = 3 8 + 5 82 . The remaining six symbols are stored in the stack: ρ(M)(sL) = [ 78 + 3 82 + 5 83 , 5 8 + 3 82 + 7 83 ].
  We encode in neuron h(|sj |), the number of symbols in sj (j ∈ {L,R}). In the above example, h(|sL|) = 2. These neurons help the RNN to know when pushing or popping operations are required. We use the encoding ρ(h) : {1, 2, ..., p} → Q, defined by:
  ρ(h)(y) = y
  p+ 1 . (9)
  Together, define the encoding function ρ : X → (Q2|Γ|+⌈log2 |Q|⌉+|Q||Γ|+19,Q∗,Q∗) by:
  ρ(q, sL, sR) =(ρ (q)(q)⊕ ρ(s)(sL,(1:h(|sL|)))⊕ ρ (s)(sR,(1:h(|sR|)))⊕ ρ (s)(sL,(h(|sL|)+1:h(|sL|)+p))⊕
  ρ(s)(sR,(h(|sR|)+1:h(|sR|)+p))⊕ ρ (r)(sL,(1))⊕ ρ(r)(sR,(1))⊕ ρ(h)(h(|sL|))⊕
  ρ(h)(h(|sR|))⊕ 0, ρ(M)(sL), ρ(M)(sR)), (10) where 0 is a zero vector of size |Q||Γ| + 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, ρ is injective and so we can define the decoder function ρ−1 : ρ(X ) → X . With the new encoding function ρ and growing memory modules, we can prove an alternative version to Theorem 1 that only requires bounded precision neurons: Theorem 2. Given a Turing Machine M, there exists an injective function ρ : X → (Qn,Q∗,Q∗) and an n-neuron p-precision (in base 2|Γ|) RNN with two growing memory modules TW,b : (Qn,Q∗,Q∗) → (Qn,Q∗,Q∗), where n = 2|Γ| + ⌈log2 |Q|⌉ + |Q||Γ| + 19 and p ≥ 2, such that for all instantaneous descriptions x ∈ X ,
  ρ−1(T 3W,b(ρ(x))) = PM(x). (11)
  Proof. The detailed proof is in Appendix B. To illustrate the construction of the RNN, the parameters for the neuron initialized with ρ(h)(h(|sL|)), called the left guard neuron and denoted as gL(t), will be described here.
  We assume all neurons in the RNN are initialized with values from the encoder function ρ(x) at time t = 1. The guard neuron gL(t) encodes the number of left-tape symbols residing in the RNN. In three stages of an RNN, we need to update its value from gL(1) = h(|sL|)/(p + 1) to gL(4) = h(|s′L|)/(p+1), where s′L is the left tape after one step of the Turing Machine. First, notice that h(|s′L|) can be expressed as:
  h(|s′L|) =  h(|sL|)− 1 if d = L and h(|sL|) ≥ 2, p if d = L and h(|sL|) = 1, h(|sL|) + 1 if d = R and h(|sL|) ≤ p− 1, 1 if d = R and h(|sL|) = p,
  (12)
  where d is the direction that the Turing Machine’s head is moved.
  Example. Assume d = L and the size of the active symbols is h(|sL|) = 1, which means that the Turing Machine is moving left and there is only one symbol residing in the RNN. Since after the move, sL will have one symbol less and so the corresponding neuron sL(t) will encode no symbols. As a result, the top neuron of the left growing memory module would be popped out, and sL(t) would assume its value. This way the neuron sL(t) again encodes the active symbols (1 to p) of the left tape series, and h(|sL|) is set to p. (Alternatively, one may prove it directly by the definition of h and the fact that |s′L| = |sL| − 1.) An analogous process holds when the Turing Machine is moving right. We implement (12) with an RNN as follows. Define stage neurons as:
  c1(t+ 1) = σ(1− c1(t)− c2(t)), (13) c2(t+ 1) = σ(c1(t)), (14)
  with both neurons initialized to be zero. Define c(t) := [c1(t), c2(t), c3(t)] where c3(t) := 1 − c1(t) − c2(t), then c(1) = [0, 0, 1]; c(2) = [1, 0, 0]; c(3) = [0, 1, 0]. 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) = [dL(t), dR(t)], such that if the Turing Machine is moving left, d(1) = [0, 0]; d(2) = [1, 0]; d(3) = [0, 0]; and if the Turing Machine is moving right, d(1) = [0, 0]; d(2) = [0, 1]; d(3) = [0, 0]; this signals which direction the Turing Machine is moving to (formulas of d(t) appear in Appendix B).
  Then consider the following update rule for the left guard neurons:
  gL(t+ 1) = σ(gL(t) + (dR(t)− dL(t)− pg′L(t) + pg′′L(t))/(p+ 1)), (15) g′L(t+ 1) = σ((p+ 1)gL(t) + dR(t)− p− 2c2(t)− 2c3(t)), (16) g′′L(t+ 1) = σ(2− (p+ 1)gL(t)− dR(t)− 2c2(t)− 2c3(t)), (17)
  where gL(1) = h(|sL|)/(p+1), g′L(1) = g′′L(1) = 0. It can be verified that gL(4) = h(|t′L|)/(p+1) as defined by (12), completing the proof for gL(t).
  Example. Assume d = L and h(|sL|) = 1. Then gL(1) = gL(2) = 1/(p+ 1) and g′L(1) = g′′L(1) = g′L(2) = g ′′ L(2) = 0. On the second stage, gL(3) = σ(1/(p + 1) − 1/(p + 1)) = 0, g′L(3) = σ(1−p) = 0, and g′′L(3) = σ(2−1) = 1. On the third stage, gL(4) = σ(0+p/(p+1)) = p/(p+1) as required.
  The full proof appears in Appendix B.
  Similar to Corollary 1.1, it follows that: Corollary 2.1. Given a Turing Machine M, there exists an injective function ρ : X → (Qn,Q∗,Q∗) and an n-neuron p-precision (in base |2Γ|) RNN with two growing memory modules TW,b : (Qn,Q∗,Q∗) → (Qn,Q∗,Q∗), where n = 2|Γ| + ⌈log2 |Q|⌉ + |Q||Γ| + 19 and p ≥ 2, such that for all instantaneous descriptions x ∈ X , the following holds: If P∗M(x) is defined, then
  ρ−1(T ∗W,b(ρ(x))) = P∗M(x), (18)
  and if P∗M(x) is not defined, then T ∗W,b(ρ(x)) is also not defined. If P∗M(x) is defined and computed in T steps by M, then T ∗W,b(ρ(x)) is computed in 3T steps by the RNN.
  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 Turing Machine in O(T 6), where T is the number of steps required for the Turing Machine to compute the result and p ≥ 2.
  The architecture of the Turing-complete 54-neuron RNN (fully described in the proof of Theorem 2) is depicted in Figure 2.
sections.heading: 4.1 Relationship of the Growing Memory Modules with Stack-augmented RNNs
sections.text: The proposed growing memory module belongs to the generic class of stack-augmented RNNs, which refers to any RNNs augmented with a stack-like mechanism. Many different forms of stackaugmented RNNs have been proposed [11, 12, 13, 14, 15]. Given the simplicity of the design,
  the growing memory module represents the foundation form of these stack-augmented RNNs. It is easy to show that these stack-augmented RNNs can simulate the growing memory module in linear time. For example, the growing memory modules can be simulated by the neural stack [11] as follows. For pushing operation, set vt in the neural stack to u(t) in the growing memory module, and dt in the neural stack to 1{u(t) > 0} in the growing memory module. For popping operation, set ut in the neural stack to 1{o(t) = 1} in the growing memory module. Therefore, the proof for the Turing completeness of bounded-precision RNNs with growing memory modules can extend to other stack-augmented RNNs. That is, bounded-precision stack-augmented RNNs are also Turing-complete.
  Different from other stack-augmented RNNs, the proposed growing memory modules use a simple mechanism to control pushing and popping, as only the top neurons in the stack are included in the RNNs. This allows theories relating to growing memory modules to be easily extended to other forms of RNNs.
sections.heading: 5 Bounded-Precision RNNs and Space-Bounded Turing Machines
sections.text: As discussed above, it is inefficient to update all neurons that encode tape information, but if one still wants to remove the growing memory modules and focuses purely on a bounded-precision RNN only, then the resulting network can simulate space-bounded Turing Machines (that is, Turing Machines with a bounded-size tape) only.
  Theorem 3. Given a Turing Machine M with a bounded tape of size F , there exists an injective function ρ : X → Qn and an n-neuron p-precision (in base |2Γ|) RNN TW,b : Qn → Qn, where n = O(⌈F/p⌉) and p ≥ 2, such that for all instantaneous descriptions x ∈ X ,
  ρ−1(T 3W,b(ρ(x))) = PM(x). (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 an RNN as 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, we say an RNN has an
  unbounded number of neurons if the RNN either has an infinite number of neurons to start with or can increase the number of neurons after each update step depending on the neurons’ values. The UTM that simulates any Turing Machine in a fast way was described in [21], which does so with only O(T log T ) slowdown. While this UTM has multiple tapes, Theorem 3 can be generalized to multiple-tape Turing Machines easily. We now obtain:
  Corollary 3.1. There exists an unbounded-neuron bounded-precision RNN that can simulate any Turing Machine in O(T log T ), where T is the number of steps required for the Turing Machine to compute the result.
sections.heading: 6 Discussion and Conclusion
sections.text: To construct a Turing-complete RNN, we have to incorporate some encoding for the unbounded number of symbols on the Turing tape. This encoding can be done by: (a) unbounded precision of some neurons (Theorem 1), (b) an unbounded number of neurons (Theorem 3), or (c) a separate growing memory module (Theorem 2). The main contribution of this paper is spelling out the details of (c), which provides a practical way to construct an RNN that runs any given algorithms. We prove the Turing completeness of a 40-neuron unbounded-precision RNN, which is the smallest Turing-complete RNN to date. We analyze the relationship between the number of neurons and the precision of an RNN when simulating a Turing Machine. Most importantly, we propose a 54-neuron bounded-precision RNN with growing memory modules that is Turing-complete, and this proof of Turing completeness can be extended to stack-augmented RNNs in general.
  This paper focuses on the computational capabilities and representability of symbolic and subsymbolic processing via stack-augmented RNNs; it 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 a 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.
title: Turing Completeness of Bounded-Precision Recurrent Neural Networks