* The first exposition on super-recursive algorithms, systematizing all main classes and providing an accessible, focused examination of the theory and its ramifications * Demonstrates how these algorithms are more appropriate as mathematical models for modern computers and how they present a better framework for computing methods * Develops a new practically-oriented perspective on the theory of algorithms, computation, and automata, as a whole
Author(s): Mark Burgin
Series: Monographs in Computer Science
Publisher: Springer
Year: 2004
Language: English
Pages: 314
Contents......Page 8
Preface......Page 10
1 Introduction......Page 14
1.1 Information processing systems (IPS)......Page 15
1.2 What theory tells us about new directions in information technology......Page 21
1.3 The structure of this book......Page 25
1.4 Notation and basic definitions......Page 30
2.1 What algorithms are and why we need them......Page 34
2.2 Mathematical models of algorithms and why we need them: History and methodology......Page 45
2.3 Centralized computation: Turing machines......Page 59
2.4 Distributed computation: Neural networks and cellular automata......Page 69
2.5 Applications......Page 85
3.1 What subrecursive algorithms are and why we need them......Page 91
3.2 Mathematical models of subrecursive algorithms and why we need them......Page 93
3.3 Procedural programming as know-how: Finite automata and finite-state machines......Page 97
3.4 Functional programming as know-what: Recursive functions......Page 109
4 Superrecursive Algorithms: Problems of Computability......Page 118
4.1 What superrecursive algorithms are and why we need them......Page 119
4.2 Mathematical models of superrecursive algorithms and why we need them......Page 125
4.3 Emerging computation, inductive Turing machines, and their computational power......Page 163
4.4 Grid automata: Interaction and computation......Page 195
5 Superrecursive Algorithms: Problems of Efficiency......Page 214
5.1 Measures of computer efficiency, program complexity, and their mathematical models......Page 215
5.2 Computational complexity: Axiomatic approach and specific measures......Page 223
5.3 Dual complexity measures: Axiomatic approach and Kolmogorov complexity......Page 238
6 Conclusion: Problems of Information Technology and Computer Science Development......Page 256
6.1 A systemology for models of algorithms and information processing systems......Page 258
6.2 Development of information processing systems (IPS)......Page 262
6.3 From algorithms to programs to technology......Page 269
References and Sources for Additional Reading......Page 273
A......Page 305
C......Page 306
F......Page 308
L......Page 309
M......Page 310
O......Page 311
S......Page 312
U......Page 313
W......Page 314
