ON THE COMPUTATIONAL POWER OF NEURAL NETS

This paper deals with finite size networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a ''sigmoidal'' function to a linear combination of the previous states of all units. We prove that one may simulate all Turing machines by such nets. In particular, one can simulate any multi-stack Turing machine in real time, and there is a net made up of 886 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Non-deterministic Turing machines can be simulated by non-deterministic rational nets, also in real time. The simulation result has many consequences regarding the decidability, or more generally the complexity, of questions about recursive nets. (C) 1995 Academic Press, Inc.