TCS / Research / Publications / Continuous-Time Symmetric Hopfield Nets are Computationally Universal
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Continuous-Time Symmetric Hopfield Nets are Computationally Universal

Reference:

Jiří Šíma and Pekka Orponen. Continuous-time symmetric Hopfield nets are computationally universal. Neural Computation, 15(3):693–733, March 2003.

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, Liapunov-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 discrete-time binary neurons, with in general asymmetric coupling weights, can be simulated by a symmetric continuous-time Hopfield net containing only units employing the saturated-linear activation function. Moreover, if the asymmetric network has maximum integer weight size and converges in discrete time , then the corresponding Hopfield net can be designed to operate in continuous time , for any such that . 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.

Keywords:

dynamical systems, continuous time, neural networks, Hopfield model, computational power

Suggested BibTeX entry:

@article{SiOr03a,
    author = {Ji{\v{r}}{\'{\i}} {\v{S}}{\'{\i}}ma and Pekka Orponen},
    journal = {Neural Computation},
    month = {March},
    number = {3},
    pages = {693--733},
    title = {Continuous-Time Symmetric {H}opfield Nets are Computationally Universal},
    volume = {15},
    year = {2003},
}

See neco.mitpress.org ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.