ON THE TURING COMPLETENESS OF MODERN NEURAL NETWORK ARCHITECTURES
Alternatives to recurrent neural networks, in particular, architectures based on attention or convolutions, have been gaining momentum for processing input sequences. In spite of their relevance, the computational properties of these alternatives have not yet been fully explored. We study the computational power of two of the most paradigmatic architectures exemplifying these mechanisms: the Transformer (Vaswani et al., 2017) and the Neural GPU (Kaiser & Sutskever, 2016). We show both models to be Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. In particular, neither the Transformer nor the Neural GPU requires access to an external memory to become Turing complete. Our study also reveals some minimal sets of elements needed to obtain these completeness results.
This paper seeks to answer the question of whether models which process sequences, but are not strictly classical RNNs, are Turing complete.
The authors present proofs that both the Transformer and Neural GPU are turing complete, under certain conditions. I do not consider myself qualified to properly verify the proof but it seems to be presented clearly. The authors note that the conditions involved are not how these models are used in the real world. Given the complex construction required for this more theoretically based proof, it seems reasonable that this should be published now, rather than waiting until the further work discussed in the final section is completed.
I have a number of questions where if a brief answer is possible, this would enhance the manuscript. The main question is, of the simplifications and approximations used for the proof, how much does that take the model away from what is used in practice? For example, the assumption of the piecewise linear sigmoid seems like a quite big change, as there are large regions of the space which now have zero gradients. If you run a real implementation of these models, with the normal sigmoid replaced by this one, does training still work? If not, what are the implications for the proof?
The rational numbers assumption is interesting - again I wonder how this would affect the model in reality, obviously all floating points on a computer represent rationals, but it would be interesting to get a better understanding on how the lack of infinite precision rationals on real hardware affects the main results.
Does the proof rely on the input and output dimensionality being the same? Eg in the preliminaries, x_i and y_i are both d-dimensional - could this be changed?
Overall this paper is novel and interesting, I have to give a slightly low confidence score because I'm unfamiliar with a lot of the background here (eg the Siegelamnn & Sontag work). The paper does seem concise and well written.
typos and minor points:
Circular convolution definition only appears to define the values directly adjacent to the border, would it be more appropriate to define S_{h+n, :, :} = S{n, :, :}?
paragraph above equation 5, 'vectores' -> 'vectors'