Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

March 1, 2003, Vol. 15, No. 3, Pages 693-733
(doi: 10.1162/089976603321192130)
© 2003 Massachusetts Institute of Technology
Continuous-Time Symmetric Hopfield Nets Are Computationally Universal
Article PDF (339.99 KB)
Abstract

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 wmax and converges in discrete time t*, then the corresponding Hopfield net can be designed to operate in continuous time Θ(t*/ϵ) for any ϵ > 0 such that wmax212n ≤ ϵ21/ϵ. 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.