On the computational power of neural nets

Hava T. Siegelmann; Eduardo D. Sontag

doi:10.1145/130385.130432

On the computational power of neural nets

Hava T. Siegelmann, Eduardo D. Sontag

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
Publisher	Publ by ACM
Pages	440-449
Number of pages	10
ISBN (Print)	089791497X, 9780897914970
DOIs	https://doi.org/10.1145/130385.130432
State	Published - 1992
Event	Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory - Pittsburgh, PA, USA Duration: Jul 27 1992 → Jul 29 1992

Publication series

Name	Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

Other

Other	Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
City	Pittsburgh, PA, USA
Period	7/27/92 → 7/29/92

All Science Journal Classification (ASJC) codes

Engineering(all)

Access to Document

10.1145/130385.130432

Cite this

@inproceedings{7e0f09e1920c4f5fab03d0207694e0de,

title = "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.",

author = "Siegelmann, {Hava T.} and Sontag, {Eduardo D.}",

year = "1992",

doi = "10.1145/130385.130432",

language = "English (US)",

isbn = "089791497X",

series = "Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory",

publisher = "Publ by ACM",

pages = "440--449",

booktitle = "Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory",

note = "Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory ; Conference date: 27-07-1992 Through 29-07-1992",

}

Siegelmann, HT & Sontag, ED 1992, On the computational power of neural nets. in Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory. Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, Publ by ACM, pp. 440-449, Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, Pittsburgh, PA, USA, 7/27/92. https://doi.org/10.1145/130385.130432

TY - GEN

T1 - On the computational power of neural nets

AU - Siegelmann, Hava T.

AU - Sontag, Eduardo D.

PY - 1992

Y1 - 1992

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

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

UR - http://www.scopus.com/inward/record.url?scp=0026972451&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026972451&partnerID=8YFLogxK

U2 - 10.1145/130385.130432

DO - 10.1145/130385.130432

M3 - Conference contribution

AN - SCOPUS:0026972451

SN - 089791497X

SN - 9780897914970

T3 - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

SP - 440

EP - 449

BT - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

Y2 - 27 July 1992 through 29 July 1992

ER -

On the computational power of neural nets

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this