Neural Networks and Analog Computation: Beyond the Turing Limit

Front Cover
Springer Science & Business Media, Dec 1, 1998 - Computers - 181 pages
4 Reviews
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.
 

What people are saying - Write a review

User Review - Flag as inappropriate

Excellent and clearly written, "Beyond the Turing Limit" is a classic introducing a completely new way to look at computation. The text is clear, concise and the math can only be termed elegant. Read carefully, this book provides new insight not only into the technical area of computation, but into the biological world. 

Contents

Computational Complexity
1
11 Neural Networks
2
A General Introduction
4
121 Input Sets in Computability Theory
5
13 Finite Automata
6
14 The Turing Machine
8
141 Neural Networks and Turing Machines
10
15 Probabilistic Turing Machines
11
51 Kolmogorov Complexity and Reals
78
52 Tally Oracles and Neural Networks
81
53 Kolmogorov Weights and Advice Classes
85
54 The Hierarchy Theorem
87
Space and Precision
91
62 Fixed Precision Variable Sized Nets
94
Universality of Sigmoidal Networks
97
71 Alarm Clock Machines
100

151 Neural Networks and Probabilistic Machines
12
161 Nondeterministic Neural Networks
13
18 Advice Turing Machines
14
181 Circuit Families
15
182 Neural Networks and Advice Machines
16
19 Notes
17
The Model
19
21 Variants of the Network
20
211 A System Diagram Interpretation
22
22 The Networks Computation
23
23 Integer Weights
25
Networks with Rational Weights
29
31 The Turing Equivalence Theorem
30
32 Highlights of the Proof
33
322 Stack Operations
35
323 General Construction of the Network
36
331 PStack Machines
37
34 Network with Four Layers
38
341 A Layout Of The Construction
43
35 RealTime Simulation
44
351 Computing in Two Layers
45
352 Removing the Sigmoid From the Main Layer
48
353 One Layer Network Simulates TM
54
37 Universal Network
56
38 Nondeterministic Computation
57
Networks with Real Weights
59
41 Simulating Circuit Families
61
412 A Circuit Retrieval
63
413 Circuit Simulation By a Network
66
414 The Combined Network
67
42 Networks Simulation by Circuits
68
422 The Network Simulation by a Circuit
70
43 Networks versus Threshold Circuits
72
44 Corollaries
75
Kolmogorov Weights Between P and Ppoly
77
712 Alarm Clock and Adder Machines
102
72 Restless Counters
103
73 Sigmoidal Networks are Universal
106
731 Correctness of the Simulation
110
74 Conclusions
112
Differentlimits Networks
115
82 Proof of the Interpolation Lemma
118
Stochastic Dynamics
121
91 Stochastic Networks
122
911 The Model
124
92 The Main Results
125
922 Rational Networks
126
93 Integer Stochastic Networks
127
94 Rational Stochastic Networks
128
941 Rational Set of Choices
129
95 Real Stochastic Networks
134
96 Unreliable Networks
136
97 Nondeterministic Stochastic Networks
138
Generalized Processor Networks
141
Definition
142
102 Bounded Precision
143
103 Equivalence with Neural Networks
145
104 Robustness
146
Analog Computation
147
111 Discrete Time Models
148
112 Continuous Time Models
149
113 Hybrid Models
150
Computation Beyond the Turing Limit
153
121 The Analog Shift Map
156
122 Analog Shift and Computation
158
123 Physical Relevance
163
124 Conclusions
164
Bibliography
165
Index
179
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

Bibliographic information