On the computational power of neural nets

Hava T. Siegelmann, Eduardo D. Sontag

Research output: Chapter in Book/Report/Conference proceedingConference contribution

81 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
PublisherPubl by ACM
Pages440-449
Number of pages10
ISBN (Print)089791497X, 9780897914970
DOIs
StatePublished - 1992
EventProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory - Pittsburgh, PA, USA
Duration: Jul 27 1992Jul 29 1992

Publication series

NameProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

Other

OtherProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
CityPittsburgh, PA, USA
Period7/27/927/29/92

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'On the computational power of neural nets'. Together they form a unique fingerprint.

Cite this