Reference:
Jiří Šíma and Pekka Orponen. Computing with continuoustime Liapunov systems. In J. S. Vitter, P. Spirakis, and M. Yannakakis, editors, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC'01, Crete, July 2001), pages 722–731, New York NY, 2001. Association for Computing Machinery.
Abstract:
We establish a fundamental result in the theory of computation by continuoustime dynamical systems, by showing that systems corresponding to so called continuoustime symmetric Hopfield nets are capable of general computation. More precisely, we prove that any function computed by a discretetime asymmetric recurrent network of threshold gates can also be computed by a continuoustime symmetricallycoupled Hopfield system of dimension . Moreover, if the threshold logic network has maximum weight and converges in discrete time , then the corresponding Hopfield system can be designed to operate in continuous time , for any value such that .
The result appears at first sight counterintuitive, because the dynamics of any symmetric Hopfield system is constrained by a em Liapunov, or em energy function defined on its state space. In particular, such a system always converges from any initial state towards some stable equilibrium state, and hence cannot exhibit nondamping oscillations, i.e. strictly speaking cannot simulate even a single alternating bit. However, we show that if one only considers em terminating computations, then the Liapunov constraint can be overcome, and one can in fact embed arbitrarily complicated computations in the dynamics of Liapunov systems with only a modest cost in the system's dimensionality.
In terms of standard discrete computation models, our result implies that any polynomially spacebounded Turing machine can be simulated by a family of polynomialsize continuoustime symmetric Hopfield nets.
Keywords:
dynamical systems, continuous time, neural networks, Hopfield model, computational power
Suggested BibTeX entry:
@inproceedings{SiOr01a,
address = {New York NY},
author = {Ji{\v{r}}{\'{\i}} {\v{S}}{\'{\i}}ma and Pekka Orponen},
booktitle = {Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC'01, Crete, July 2001)},
editor = {J. S. Vitter and P. Spirakis and M. Yannakakis},
organization = {Association for Computing Machinery},
pages = {722731},
title = {Computing with ContinuousTime {L}iapunov Systems},
year = {2001},
}
