On the Computational Power of Neural Nets

• DOI: 10.1006/jcss.1995.1013
• Publication Date: 2002-10-07T11:33:37Z
• Authors: H.T. Siegelmann; E.D. Sontag
• Keywords: Time hierarchy theorem; Turing; Pushdown automaton

AbstractThis 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.