On the Computational Power of Neural Nets
Abstract
This paper deals with finite networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a "sigmoidal" scalar nonlinearity to a linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by rational nets. In particular, one can do this in linear time, and there is a net made up of about 1,000 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Furthermore, we assert a similar theorem about non-deterministic Turing Machines. Consequences for undecidability and complexity issues about nets are discussed too.
Cite
Text
Siegelmann and Sontag. "On the Computational Power of Neural Nets." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130432Markdown
[Siegelmann and Sontag. "On the Computational Power of Neural Nets." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/siegelmann1992colt-computational/) doi:10.1145/130385.130432BibTeX
@inproceedings{siegelmann1992colt-computational,
title = {{On the Computational Power of Neural Nets}},
author = {Siegelmann, Hava T. and Sontag, Eduardo D.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {440-449},
doi = {10.1145/130385.130432},
url = {https://mlanthology.org/colt/1992/siegelmann1992colt-computational/}
}