Neural Networks and Analog Computation

1. Front Matter

   Pages i-xiv

   PDF

2. Computational Complexity

   • Hava T. Siegelmann

   Pages 1-17

3. The Model

   • Hava T. Siegelmann

   Pages 19-27

4. Networks with Rational Weights

   • Hava T. Siegelmann

   Pages 29-58

5. Networks with Real Weights

   • Hava T. Siegelmann

   Pages 59-76

6. Kolmogorov Weights: Between P and P/poly

   • Hava T. Siegelmann

   Pages 77-89

7. Space and Precision

   • Hava T. Siegelmann

   Pages 91-96

8. Universality of Sigmoidal Networks

   • Hava T. Siegelmann

   Pages 97-113

9. Different-limits Networks

   • Hava T. Siegelmann

   Pages 115-120

10. Stochastic Dynamics

    • Hava T. Siegelmann

    Pages 121-139

11. Generalized Processor Networks

    • Hava T. Siegelmann

    Pages 141-146

12. Analog Computation

    • Hava T. Siegelmann

    Pages 147-152

13. Computation Beyond the Turing Limit

    • Hava T. Siegelmann

    Pages 153-164

14. Back Matter

    Pages 165-184

    PDF

Humanity's most basic intellectual quest to decipher nature and master it has led to numerous efforts to build machines that simulate the world or communi­ cate with it [Bus70, Tur36, MP43, Sha48, vN56, Sha41, Rub89, NK91, Nyc92]. The computational power and dynamic behavior of such machines is a central question for mathematicians, computer scientists, and occasionally, physicists. Our interest is in computers called artificial neural networks. In their most general framework, neural networks consist of assemblies of simple processors, or "neurons," each of which computes a scalar activation function of its input. This activation function is nonlinear, and is typically a monotonic function with bounded range, much like neural responses to input stimuli. The scalar value produced by a neuron affects other neurons, which then calculate a new scalar value of their own. This describes the dynamical behavior of parallel updates. Some of the signals originate from outside the network and act as inputs to the system, while other signals are communicated back to the environment and are thus used to encode the end result of the computation.

• Natur
• Theorie
• complexity
• computer science
• development
• model
• robot
• robotics
• science
• simulation

"All of the three primary questions are considered: What computational models can the net simulate (within polynomial bounds)? What are the computational complexity classes that are relevant to the net? How does the net (which, after all, is an analog device) relate to Church’s thesis? Moreover the power of the basic model is also analyzed when the domain of reals is replaced by the rationals and the integers."

—Mathematical Reviews

"Siegelmann's book focuses on the computational complexities of neural networks and making this research accessible...the book accomplishes the said task nicely."

---SIAM Review, Vol. 42, No 3.

• Department of Information Systems Engineering, Faculty of Industrial Engineering and Management Technion, Haifa, Israel

  Hava T. Siegelmann

Policies and ethics