Computing with continuous-time Liapunov systems
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 <italic>n</italic> threshold gates can also be computed by a continuous-time symmetrically-coupled Hopfield system of dimension 18<italic>n</italic>+7. Moreover, if the threshold logic network has maximum weight <italic>w</italic>_{\max} and converges in discrete time <italic>t</italic>^*, then the corresponding Hopfield system can be designed to operate in continuous time &THgr;(<italic>t</italic>^*/ε), for any value 0<ε<0.0025 such that <italic>w</italic>_{\max}2^{3<italic>n</italic>}\leq\ε 2^{1/ε}.
The result appears at first sight counterintuitive, because the dynamics of any symmetric Hopfield system is constrained by a <italic>Liapunov</italic>, or <italic>energy function</italic> 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 <italic>terminating</italic> 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.