The Computational Power of Continuous Time

Neural Networks (Preliminary Version)

Pekka Orponen
Department of Computer Science
University of Helsinki, Finland?

August 28, 1995

Abstract

We investigate the computational power of continuous-time neural networks with Hopfield-type units. We prove that polynomial-size networks with saturated-linear response functions are at least as powerful as polynomially space-bounded Turing machines.

1 Introduction

In a paper published in 1984 [11], John Hopfield introduced a continuoustime version of the neural network model whose discrete-time variant he had discussed in his seminal 1982 paper [10]. The 1984 paper also contains an electronic implementation scheme for the continuous-time networks, and an argument showing that for sufficiently large-gain nonlinearities, these behave similarly to the discrete-time ones, at least when used as associative memories.

The power of Hopfield's discrete-time networks as general-purpose computational devices was analyzed in [17, 18]. In this paper we conduct a similar analysis for networks consisting of Hopfield's continuous-time units; however we are at this stage able to analyze only the general asymmetric networks, and the very interesting subclass of continuous-time networks

?Address: P. O. Box 26, FIN{00014 University of Helsinki, Finland. E-mail: [email protected]. This work was done during the author's visit to the Institute for Theoretical Computer Science, Technical University of Graz, Austria.