New report available

[Jiri Sima]

Dear Colleagues,

the following report 

Sima, J., Orponen, P. A Continuous-Time Hopfield Net Simulation 
of Discrete Neural Networks. Technical report V-773, ICS CAS, 
Prague, January, 1999.

is now available on-line at

http://www.uivt.cas.cz/ics/reports.html


Abstract:

We investigate the computational power of continuous-time
symmetric Hopfield nets. Since the dynamics of such networks
are governed by Liapunov (energy) functions, they cannot
generate infinite nondamping oscillations, and hence cannot
simulate arbitrary (potentially divergent) discrete computations.
Nevertheless, we prove that any convergent fully parallel 
computation by a network of $n$ discrete-time binary neurons, 
with in general asymmetric interconnections, can be simulated 
by a symmetric continuous-time Hopfield net containing $14n+6$
units using the saturated-linear sigmoid activation function.
In terms of standard discrete computation models this result 
implies that any polynomially space-bounded Turing machine can 
be simulated by a polynomially size-increasing sequence of 
continuous-time Hopfield nets. Similar techniques as here yield 
corresponding results on the convergence time and computational 
power of discrete-time Hopfield nets.


Comments are welcome,

  Best regards,
                   
-- Jirka Sima

******************************************************************
Mgr. Jiri Sima, CSc.
Department of Theoretical Informatics
Institute of Computer Science, Czech Academy of Sciences
Pod vodarenskou vezi 2, 182 07 Prague 8, Czech Republic
phone: (+4202) 66 05 30 30      e-mail: sima at uivt.cas.cz
fax: (+4202) 85 85 789          www: http://www.uivt.cas.cz/~sima
******************************************************************