Continuous-time symmetric Hopfield nets are computationally universal.

We establish a fundamental result in the theory of computation by continuous-time dynamical systems by showing that systems corresponding to so-called continuous-time symmetric Hopfield nets are capable of general computation. As is well known, such networks have very constrained Lyapunov-function controlled dynamics. Nevertheless, we show that they are universal and efficient computational devices, in the sense that any convergent synchronous fully parallel computation by a recurrent network of n discrete-time binary neurons, with in general asymmetric coupling weights, can be simulated by a symmetric continuous-time Hopfield net containing only 18n + 7 units employing the saturated-linear activation function. Moreover, if the asymmetric network has maximum integer weight size w(max) and converges in discrete time t*, then the corresponding Hopfield net can be designed to operate in continuous time Theta(t*/epsilon) for any epsilon > 0 such that w(max)2(12n) </= epsilon2(1/epsilon). In terms of standard discrete computation models, our result implies that any polynomially space-bounded Turing machine can be simulated by a family of polynomial-size continuous-time symmetric Hopfield nets.