Computing with Continuous-Time Liapunov Systems

Reference:

Jiří Šíma and Pekka Orponen. Computing with continuous-time 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 continuous-time dynamical systems, by showing that systems corresponding to so called continuous-time symmetric Hopfield nets are capable of general computation. More precisely, we prove that any function computed by a discrete-time asymmetric recurrent network of threshold gates can also be computed by a continuous-time symmetrically-coupled 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 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:

@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 = {722--731},
    title = {Computing with Continuous-Time {L}iapunov Systems},
    year = {2001},
}