Research Catalog

Title

Hypercomputation : computing beyond the Church-Turing barrier / A. Syropoulos.

Author

Syropoulos, Apostolos.

Publication

New York : Springer, [2008], ©2008.

Supplementary Content

DE-576;springer

Items in the Library & Off-site

Details

Description

xiii, 243 pages : illustrations; 24 cm

Summary

"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." "The book features descriptions of the various attempts of hypercomputation: from trial-and-error machines to the exploration of the human mind treated as a device with computational abilities. Hypercomputation: Computing Beyond the Church-Turing Barrier is fairly self-contained but requires a solid background in mathematics (calculus, discrete mathematics, algebra, and topology)."--BOOK JACKET.

Subjects

• Computable functions
• Artificial intelligence
• Computational complexity

Bibliography (note)

• Includes bibliographical references (p. 221-234) and indexes.

Contents

1.1 On Computing and Its Limits 1 -- 1.2 From Computation to Hypercomputation 6 -- 1.3 Why Bother with Hypercomputation? 9 -- Chapter 2 On the Church-Turing Thesis 11 -- 2.1 Turing Machines 11 -- 2.2 General Recursive Functions 15 -- 2.3 Recursive Relations and Predicates 17 -- 2.4 The Church-Turing Thesis 20 -- Chapter 3 Early Hypercomputers 25 -- 3.1 Trial-and-Error Machines 25 -- 3.1.1 Extending Recursion Theory 25 -- 3.1.2 A Model of the Human Mind 27 -- 3.2 TAE-Computability 30 -- 3.3 Inductive Turing Machines 33 -- 3.4 Extensions to the Standard Model of Computation 37 -- 3.5 Exotic Machines 40 -- 3.6 On Pseudorecursiveness 42 -- Chapter 4 Infinite-Time Turing Machines 45 -- 4.1 On Cardinal and Ordinal Numbers 45 -- 4.2 Infinite-Time Turing Machines 48 -- 4.2.1 How the Machines Operate 49 -- 4.2.2 On the Power of Infinite-Time Machines 52 -- 4.2.3 Clockable Ordinals 55 -- 4.2.4 On Infinite-Time Halting Problems 56 -- 4.2.5 Machines with Only One Tape 57 -- 4.2.6 Infinite-Time Machines with Oracles 57 -- 4.2.7 Post's Problem for Supertasks 59 -- 4.3 Infinite-Time Automata 60 -- 4.4 Building Infinite Machines 61 -- 4.5 Metaphysical Foundations for Computation 63 -- Chapter 5 Interactive Computing 69 -- 5.1 Interactive Computing and Turing Machines 69 -- 5.2 Interaction Machines 72 -- 5.3 Persistent Turing Machines 75 -- 5.4 Site and Internet Machines 77 -- 5.5 Other Approaches 81 -- Chapter 6 Hyperminds 85 -- 6.1 Mathematics and the Mind 86 -- 6.1.1 The Pure Godelian Argument 86 -- 6.1.2 The Argument from Infinitary Logic 96 -- 6.1.3 The Modal Argument 97 -- 6.2 Philosophy and the Mind 100 -- 6.2.1 Arguments Against Computationalism 100 -- 6.2.2 The Chinese Room Argument Revisited 102 -- 6.3 Neurobiology and the Mind 104 -- 6.4 Cognition and the Mind 109 -- Chapter 7 Computing Real Numbers 113 -- 7.1 Type-2 Theory of Effectivity 113 -- 7.1.1 Type-2 Machines 114 -- 7.1.2 Computable Topologies 117 -- 7.1.3 Type-2 Computability of Real Numbers 119 -- 7.1.4 The Arithmetic Hierarchy of Real Numbers 120 -- 7.1.5 Computable Real Functions 121 -- 7.2 Indeterministic Multihead Type-2 Machines 123 -- 7.3 BSS-Machines 125 -- 7.3.1 Finite-Dimensional Machines 126 -- 7.3.2 Machines over a Commutative Ring 129 -- 7.3.3 Parallel Machines 130 -- 7.4 Real-Number Random-Access Machines 131 -- 7.5 Recursion Theory on the Real Numbers 133 -- Chapter 8 Relativistic and Quantum Hypercomputation 137 -- 8.1 Supertasks in Relativistic Spacetimes 137 -- 8.2 SAD Machines 140 -- 8.3 Supertasks near Black Holes 144 -- 8.4 Quantum Supertasks 148 -- 8.5 Ultimate Computing Machines 152 -- 8.6 Quantum Adiabatic Computation 154 -- 8.7 Infinite Concurrent Turing Machines 162 -- Chapter 9 Natural Computation and Hypercomputation 165 -- 9.1 Principles of Natural Computation 165 -- 9.2 Models of Analog Computation 169 -- 9.3 On Undecidable Problems of Analysis 174 -- 9.4 Noncomputability in Computable Analysis 178 -- 9.5 The Halting Function Revisited 180 -- 9.6 Neural Networks and Hypercomputation 183 -- 9.7 An Optical Model of Computation 184 -- 9.8 Fuzzy Membrane Computing 189 -- 9.9 Analog X-Machines 193 -- Appendix A The P = NP Hypothesis 199 -- Appendix B Intractability and Hypercomputation 203 -- Appendix C Socioeconomic Implications 205 -- Appendix D A Summary of Topology and Differential Geometry 209 -- D.1 Frames 209 -- D.2 Vector Spaces and Lie Algebras 210 -- D.3 Topological Spaces: Definitions 212 -- D.4 Banach and Hilbert Spaces 215 -- D.5 Manifolds and Spacetime 217.

ISBN

• 0387308865
• 9780387308869

LCCN

2008931304

OCLC

• ocm65764984
• 65764984
• SCSB-5439064

Owning Institutions

Columbia University Libraries