@inproceedings{
    SiOr01a,
    editor = "Vitter, J. S. and Spirakis, P. and Yannakakis, M.",
    author = "{\v{S}}{\'{\i}}ma, Ji{\v{r}}{\'{\i}} and Orponen, Pekka",
    title = "Computing with Continuous-Time {L}iapunov Systems",
    url = "http://doi.acm.org/10.1145/380752.380878",
    booktitle = "Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC'01, Crete, July 2001)",
    address = "New York NY",
    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 $n$ threshold gates can also be computed by a continuous-time symmetrically-coupled Hopfield system of dimension $18n+7$. Moreover, if the threshold logic network has maximum weight $w_{\max}$ and converges in discrete time $t^*$, then the corresponding Hopfield system can be designed to operate in continuous time $\Theta(t^*/\varepsilon)$, for any value $0<\varepsilon<0.0025$ such that $w_{\max}2^{3n}\leq\varepsilon 2^{1/\varepsilon}$. \par 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. \par 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.",
    supersedes = "SiOr02",
    flags = "public",
    year = "2001",
    keywords = "dynamical systems, continuous time, neural networks, Hopfield model, computational power",
    organization = "Association for Computing Machinery",
    pages = "722--731"
}