HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Síma, J. Articles by Orponen, P. Search for Related Content PubMed PubMed Citation Articles by Síma, J. Articles by Orponen, P.

Continuous-Time Symmetric Hopfield Nets Are Computationally Universal

Jií íma

sima{at}cs.cas.cz, Institute of Computer Science, Academy of Sciences of the Czech Republic, P.O. Box 5 182 07 Prague 8, Czech Republic

Pekka Orponen

orponen{at}tcs.hut.fi, Laboratory for Theoretical Computer Science, Helsinki University of Technology, P.O. Box 5400, FIN-02015 HUT, Finland

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 (t^*/) for any >0 such that w_max2¹²ⁿ2^1/. 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.

This article has been cited by other articles:

				J. Sima and P. Orponen General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results Neural Comput., December 1, 2003; 15(12): 2727 - 2778. [Abstract] [Full Text] [PDF]