On The Computational Power Of Neural Nets

On The Computational Power Of Neural Nets

1992 | Hava T. Siegelmann, Eduardo D. Sontag
This paper explores the computational capabilities of recurrent first-order neural networks, or "processor nets," which consist of interconnections of synchronously evolving processors. Each processor updates its state using a "sigmoidal" function applied to a linear combination of the previous states of all units. The authors prove that these nets can simulate all Turing Machines in linear time, and demonstrate a net with about 1,000 processors that computes a universal partial-recursive function. They also discuss the simulation of non-deterministic Turing Machines and its implications for undecidability and complexity issues. The paper provides a detailed mathematical construction and proof, including a description of the network's architecture and a generalization to multi-tape Turing Machines. The results highlight the computational power of processor nets, which can achieve universality without high-order connections.This paper explores the computational capabilities of recurrent first-order neural networks, or "processor nets," which consist of interconnections of synchronously evolving processors. Each processor updates its state using a "sigmoidal" function applied to a linear combination of the previous states of all units. The authors prove that these nets can simulate all Turing Machines in linear time, and demonstrate a net with about 1,000 processors that computes a universal partial-recursive function. They also discuss the simulation of non-deterministic Turing Machines and its implications for undecidability and complexity issues. The paper provides a detailed mathematical construction and proof, including a description of the network's architecture and a generalization to multi-tape Turing Machines. The results highlight the computational power of processor nets, which can achieve universality without high-order connections.
Reach us at info@study.space
[slides and audio] On the computational power of neural nets