Hypercomputation (eBook)

Apostolos Syropoulos holds a Diploma in Physics from the University of Ioannina, Greece, a M.Sc. in Computer Science from the University of Göteborg, Göteborg. Sweden, and a Ph.D. in Theoretical Computer Science from the Democritus University of Thrace, Xanthi, Greece. He has published papers in the areas of categorical semantics, natural computing, programming language theory, Web-oriented technologies, and digital typography.In addition, the prospective author has presented his work in the workshop of the European COST Action Group 16 (Multivalued Logics) that was held in Vienna, Austria in 1998. He is also the team leader of the Greek Molecular Computing Group, which is a member of the European Molecular Computing Consortium, whose director is Professor Grzegorz Rezenberg. He was also member of the Democritus University team on Industrial Mathematics of the European Initiative on Mathematics in Industry. Last, but not least, it is worth to mention that recently the prospective author has published a book on the Perl programming language (in Greek).

Preface 6
Hypercomputation in a Nutshell 6
Reading This Book 7
Mathematical Assumptions 8
Acknowledgments 11
Contents 12
I. Introduction 15
1.1 On Computing and Its Limits 15
1.2 From Computation to Hypercomputation 20
1.3 Why Bother with Hypercomputation? 23
II. On the Church–Turing Thesis 25
2.1 Turing Machines 25
2.2 General Recursive Functions 29
2.3 Recursive Relations and Predicates 31
2.4 The Church–Turing Thesis 34
III. Early Hypercomputers 38
3.1 Trial-and-Error Machines 38
3.2 TAE-Computability 43
3.3 Inductive Turing Machines 46
3.4 Extensions to the Standard Model of Computation 50
3.5 Exotic Machines 53
3.6 On Pseudorecursiveness 55
IV. Infinite-Time Turing Machines 58
4.1 On Cardinal and Ordinal Numbers 58
4.2 Infinite-Time Turing Machines 61
4.3 Infinite-Time Automata 73
4.4 Building Infinite Machines 74
4.5 Metaphysical Foundations for Computation 76
V. Interactive Computing 81
5.1 Interactive Computing and Turing Machines 81
5.2 Interaction Machines 84
5.3 Persistent Turing Machines 87
5.4 Site and Internet Machines 89
5.5 Other Approaches 93
VI. Hyperminds 97
6.1 Mathematics and the Mind 98
6.2 Philosophy and the Mind 112
6.3 Neurobiology and the Mind 116
6.4 Cognition and the Mind 121
VII. Computing Real Numbers 125
7.1 Type-2 Theory of Effectivity 125
7.2 Indeterministic Multihead Type-2 Machines 135
7.3 BSS-Machines 137
7.4 Real-Number Random-AccessMachines 143
7.5 Recursion Theory on the Real Numbers 145
VIII. Relativistic and Quantum Hypercomputation 149
8.1 Supertasks in Relativistic Spacetimes 149
8.2 SAD Machines 152
8.3 Supertasks near Black Holes 156
8.4 Quantum Supertasks 160
8.5 Ultimate Computing Machines 164
8.6 Quantum Adiabatic Computation 166
8.7 Infinite Concurrent Turing Machines 174
IX. Natural Computation and Hypercomputation 176
9.1 Principles of Natural Computation 176
9.2 Models of Analog Computation 180
9.3 On Undecidable Problems of Analysis 185
9.4 Noncomputability in Computable Analysis 189
9.5 The Halting Function Revisited 191
9.6 Neural Networks and Hypercomputation 194
9.7 An Optical Model of Computation 195
9.8 Fuzzy Membrane Computing 200
9.9 Analog X-Machines 204
A. The P = NP Hypothesis 210
B. Intractability and Hypercomputation 214
C. Socioeconomic Implications 216
D. A Summary of Topology and Differential Geometry 220
D.1 Frames 220
D.2 Vector Spaces and Lie Algebras 221
D.3 Topological Spaces: Definitions 223
D.4 Banach and Hilbert Spaces 226
D.5 Manifolds and Spacetime 228
References 232
Name Index 246
Subject Index 250