## Neural Networks and Analog Computation: Beyond the Turing LimitHumanity'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 |

179 | |

### Other editions - View all

Neural Networks and Analog Computation: Beyond the Turing Limit Hava Siegelmann Limited preview - 2012 |

Neural Networks and Analog Computation: Beyond the Turing Limit Hava Siegelmann No preview available - 2012 |

### Common terms and phrases

activation function activation values adder machine advice Turing machine alarm clock machine algorithm analog computation analog processor networks analog shift map assume automaton binary sequences bits Boolean circuits bounded Chapter circuit family class of languages complexity classes computational classes computational models computational power consider constant construction Corollary defined definition denote described deterministic digital computation dynamical systems encoding exponential finite automata finite control finite number fixed points formal network gate halting implemented infinite sequence input lines input string Kolmogorov complexity Lemma NETfl non-empty nondeterministic nondeterministic Turing machine nonuniform number of neurons operation oracle Turing machines p-stack machine P/poly polynomial prefix probabilistic automaton probabilistic Turing machine prove random rational numbers rational weights real numbers real weights recurrent neural networks recursive restless counter result Section shift map simulation stack h step stochastic networks symbol tally set tape theory threshold circuits Turing model update equation vector