Neural Networks and Analog Computation Beyond the Turing Limit
The theoretical foundations of Neural Networks and Analog Computation conceptualize neural networks as a particular type of computer consisting of multiple assemblies of basic processors interconnected in an intricate structure. Examining these networks under various resource constraints reveals a c...
Main Author: | |
---|---|
Format: | eBook |
Language: | English |
Published: |
Boston, MA
Birkhäuser
1999, 1999
|
Edition: | 1st ed. 1999 |
Series: | Progress in Theoretical Computer Science
|
Subjects: | |
Online Access: | |
Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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
- 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