Síma Jirí, Orponen Pekka
Institute of Computer Science, Academy of Sciences of the Czech Republic, P.O. Box 5 182 07 Prague 8, Czech Republic.
Neural Comput. 2003 Mar;15(3):693-733. doi: 10.1162/089976603321192130.
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 Theta(t*/epsilon) for any epsilon > 0 such that w(max)2(12n) </= epsilon2(1/epsilon). 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.
我们通过证明与所谓连续时间对称霍普菲尔德网络相对应的系统能够进行通用计算，在连续时间动态系统的计算理论中建立了一个基本结果。众所周知，此类网络具有非常受限的李雅普诺夫函数控制动力学。然而，我们表明它们是通用且高效的计算设备，即任何由n个离散时间二元神经元的递归网络进行的收敛同步全并行计算，其耦合权重通常是非对称的，都可以由一个仅包含18n + 7个采用饱和线性激活函数的单元的对称连续时间霍普菲尔德网络来模拟。此外，如果非对称网络具有最大整数权重大小w(max)且在离散时间t收敛，那么相应的霍普菲尔德网络可以设计为对于任何ε > 0在连续时间Theta(t/ε)内运行，使得w(max)2(12n) ≤ ε2(1/ε)。就标准离散计算模型而言，我们的结果意味着任何多项式空间有界图灵机都可以由一族多项式大小的连续时间对称霍普菲尔德网络来模拟。
