Hypercomputation (eBook)

Computing Beyond the Church-Turing Barrier

Apostolos Syropoulos (Autor)

eBook Download: PDF

2008 | 2008
X, 260 Seiten
Springer US (Verlag)
978-0-387-49970-3 (ISBN)

Infos

This book provides a thorough description of hypercomputation. It covers all attempts at devising conceptual hypermachines and all new promising computational paradigms that may eventually lead to the construction of a hypermachine. Readers will gain a deeper understanding of what computability is, and why the Church-Turing thesis poses an arbitrary limit to what can be actually computed. Hypercomputing is a relatively novel idea. However, the book's most important features are its description of the various attempts of hypercomputation, from trial-and-error machines to the exploration of the human mind, if we treat it as a computing device.

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).

---

Hypercomputation is a relatively new theory of computation that is about computing methods and devices that transcend the so-called Church-Turing thesis. This book will provide a thorough description of the field of hypercomputation covering all attempts at devising conceptual hypermachines and all new promising computational paradigms that may eventually lead to the construction of a hypermachine.Readers of this book will get a deeper understanding of what computability is and why the Church-Turing thesis poses an arbitrary limit to what can be actually computed. Hypercomputing is in and of itself quite a novel idea and as such the book will be interesting in its own right. The most important features of the book, however, will be the thorough description of the various attempts of hypercomputation: from trial-and-error machines to the exploration of the human mind, if we treat it as a computing device.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 10.12.2008
• Zusatzinfo: X, 260 p. 19 illus.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Informatik ► Theorie / Studium ► Kryptologie
• Themenwelt: Naturwissenschaften
• Schlagworte: Algorithm analysis and problem complexity • Church-turing thesis • Computability • Computer • Geometry • hyperminds • infinite-time • pseudorecursiveness • Theory of Computation • Turing Machine
• ISBN-10: 0-387-49970-9 / 0387499709
• ISBN-13: 978-0-387-49970-3 / 9780387499703