# Understanding the computational power of neural networks

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?