It is known that a recurrent neural network with rational weights is computationally equivalent to a Turing Machine (a proof can be found in this paper).
I don't understand how is it possible, it particular:
The running time of a neural network depends only on its size, how can a neural network (even a recurrent one) perform superlinear (with respect to the input size) number of operations? how can it iterate over the input? The network cannot "go back" arbitrarily: one has to define (in the architecture) the "unfolding" size (i.e. how many steps can the network go back), so how can a fixed network deal with varying lengths, and how can a fixed size network with size $k$, on input size $n$, can perform $n^2$ operations?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.