Neural Networks and Analog Computation
Beyond the Turing Limit
Published on 1. December 1998
Book
Hardback
XIV, 181 pages
978-0-8176-3949-5 (ISBN)
Description
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.
Reviews / Votes
"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.
More details
Series
Edition
1999 ed.
Language
English
Place of publication
Boston
United States
Target group
Professional and scholarly
Research
Illustrations
XIV, 181 p.
Dimensions
Height: 241 mm
Width: 160 mm
Thickness: 16 mm
Weight
477 gr
ISBN-13
978-0-8176-3949-5 (9780817639495)
DOI
10.1007/978-1-4612-0707-8
Schweitzer Classification
Other editions
Additional editions
Book
10/2012
Springer-Verlag New York Inc.
€160.49
Shipment within 15-20 days
Previous edition
Book
12/1998
Birkhäuser Verlag GmbH
€48.28
Article exhausted; check for reprint
Content
1 Computational Complexity.- 1.1 Neural Networks.- 1.2 Automata: A General Introduction.- 1.3 Finite Automata.- 1.4 The Turing Machine.- 1.5 Probabilistic Turing Machines.- 1.6 Nondeterministic Turing Machines.- 1.7 Oracle Turing Machines.- 1.8 Advice Turing Machines.- 1.9 Notes.- 2 The Model.- 2.1 Variants of the Network.- 2.2 The Network's Computation.- 2.3 Integer Weights.- 3 Networks with Rational Weights.- 3.1 The Turing Equivalence Theorem.- 3.2 Highlights of the Proof.- 3.3 The Simulation.- 3.4 Network with Four Layers.- 3.5 Real-Time Simulation.- 3.6 Inputs and Outputs.- 3.7 Universal Network.- 3.8 Nondeterministic Computation.- 4 Networks with Real Weights.- 4.1 Simulating Circuit Families.- 4.2 Networks Simulation by Circuits.- 4.3 Networks versus Threshold Circuits.- 4.4 Corollaries.- 5 Kolmogorov Weights: Between P and P/poly.- 5.1 Kolmogorov Complexity and Reals.- 5.2 Tally Oracles and Neural Networks.- 5.3 Kolmogorov Weights and Advice Classes.- 5.4 The Hierarchy Theorem.- 6 Space and Precision.- 6.1 Equivalence of Space and Precision.- 6.2 Fixed Precision Variable Sized Nets.- 7 Universality of Sigmoidal Networks.- 7.1 Alarm Clock Machines.- 7.2 Restless Counters.- 7.3 Sigmoidal Networks are Universal.- 7.4 Conclusions.- 8 Different-limits Networks.- 8.1 At Least Finite Automata.- 8.2 Proof of the Interpolation Lemma.- 9 Stochastic Dynamics.- 9.1 Stochastic Networks.- 9.2 The Main Results.- 9.3 Integer Stochastic Networks.- 9.4 Rational Stochastic Networks.- 9.5 Real Stochastic Networks.- 9.6 Unreliable Networks.- 9.7 Nondeterministic Stochastic Networks.- 10 Generalized Processor Networks.- 10.1 Generalized Networks: Definition.- 10.2 Bounded Precision.- 10.3 Equivalence with Neural Networks.- 10.4 Robustness.- 11 Analog Computation.- 11.1 DiscreteTime Models.- 11.2 Continuous Time Models.- 11.3 Hybrid Models.- 11.4 Dissipative Models.- 12 Computation Beyond the Turing Limit.- 12.1 The Analog Shift Map.- 12.2 Analog Shift and Computation.- 12.3 Physical Relevance.- 12.4 Conclusions.