Syropoulos Hypercomputation

Computing Beyond the Church-Turing Barrier
1. Auflage 2008
ISBN: 978-0-387-49970-3
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 260 Seiten

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

Autoren/Hrsg.

Syropoulos, Apostolos

Inhaltsverzeichnis

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