Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: 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. 


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. 

Another 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.

To conclude:
1. 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).
2. 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).

If 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.



references:
[1] On the computational power of neural nets (Siegelmann and Sonntag)

[2] Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets (Joulin and Mikolov)

[3] The Neural Network Pushdown Automaton: Model, Stack and Learning Simulations (Sun, Giles, Chen, Lee)

[4] Learning to Transduce with Unbounded Memory (Grefenstette, Hermann, Suleyman, Blunsom)

limitations_and_societal_impact: none relevant
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.
main_review: The paper has a limited practical significance.

About unbounded-precision neurons: 
- Unbounded-precision is not practical.

About the RNN with bounded-precision neurons and two stacks:
- It is well known that a finite-state machine with two stacks is Turing-complete.
And an RNN with bounded-precision is a finite-state machine.
- The proposed stacks are not differentiable.
- The original Neural Turing Machine was already Turing-complete, if using an unbounded tape.
The 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.


limitations_and_societal_impact: See the main review for limitations.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: 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.   

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).

The 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.

Significance: 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?

This 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. 

It was very pleasant to read this paper and the nice results. Thank you! 


Minor:
* Line 112: "without loss of generosity" --> "without loss of generality"

References

[1] Mali et al. "Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack", 2020.

[2] Mali et al. "The Neural State Pushdown Automata", IEEE Transactions on Artificial Intelligence, 2020.

[3] Suzgin et al. "Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages", 2019.
limitations_and_societal_impact: Limitations and societal impact have been addressed to the best of my understanding.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
main_review: # Strengths
- Most of the results seems novel and paper is very well-written.

# Questions/Possible-Limitations
- 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? 
- I wonder whether copying experiments (like in NTM paper) is appropriate here. It would be nice to have a working implementation of proposed RNN. 

## Minor
- Without loss of generosity, -> generality. 
- "Implementing Neural Turing Machines" https://arxiv.org/abs/1807.08518 Might be a relevant work.
- "https://www.nature.com/articles/nature20101" Same with this. 
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_title: null

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)