Syropoulos Hypercomputation

Computing Beyond the Church-Turing Barrier
1. Auflage 2008
ISBN: 978-0-387-49970-3
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 260 Seiten

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.

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