Publication year

On the Computational Power of Neural Nets

Resource type
Authors/contributors
Title
On the Computational Power of Neural Nets
Abstract
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.
Publication
Journal of Computer and System Sciences
Volume
50
Issue
1
Pages
132-150
Date
February 1, 1995
Journal Abbr
Journal of Computer and System Sciences
Language
en
DOI
10/dvwtc3
ISSN
0022-0000
Accessed
2019-11-28T17:50:06Z
Library Catalog
ScienceDirect
Extra
ZSCC: 0000002
Citation
Siegelmann, H. T., & Sontag, E. D. (1995). On the Computational Power of Neural Nets. Journal of Computer and System Sciences, 50(1), 132–150. https://doi.org/10/dvwtc3
Processing time: 0.03 seconds

Graph of references

(from Zotero to Gephi via Zotnet with this script)
Graph of references