Hypercomputation Computing Beyond the Church-Turing Barrier
Hypercomputation is a relatively new theory of computation which treats computing methods and devices that transcend the Church-Turing thesis. This book will provide a thorough description of the field of hypercomputation, covering all attempts at devisin
- PDF / 2,407,383 Bytes
- 253 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 213 Views
To my son Demetrios-Georgios and my parents Georgios and Vassiliki
Apostolos Syropoulos
Hypercomputation Computing Beyond the Church–Turing Barrier
ABC
Apostolos Syropoulos 366 28th October Street GR-671 00 Xanthi Greece [email protected]
ISBN 978-0-387-30886-9 e-ISBN 978-0-387-49970-3 DOI 10.1007/978-0-387-49970-3 Library of Congress Control Number: 2008923106 ACM Computing Classification System (1998): F.4.1, F.1.1, F.1.0 Mathematics Subject Classification (2000): 03D10, 03D60, 03D99, 68Q05, 68Q10, 68T99 c 2008 Springer Science+Business Media, LLC ° All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper 9 8 7 6 5 4 3 2 1 springer.com
Preface
Hypercomputation in a Nutshell Computability theory deals with problems and their solutions. In general, problems can be classified into two broad categories: those problems that can be solved algorithmically and those that cannot be solved algorithmically. More specifically, the design of an algorithm that solves a particular problem means that the problem can be solved algorithmically. In addition, the design of an algorithm to solve a particular problems is a task that is equivalent to the construction of a Turing machine (i.e., the archetypal conceptual computing device) that can solve the same problem. Obviously, when a problem cannot be solved algorithmically, there is no Turing machine that can solve it. Consequently, one expects that a noncomputable problem (i.e., a problem that cannot be solved algorithmically) should become computable under a broader view of things. Generally speaking, this is not the case. The established view is that only problems that can be solved algorithmically are actually solvable. All other problems are simply noncomputable. Hypercomputation deals with noncomputable problems and how they can be solved. At first, this sounds like an oxymoron, since noncomputable problems cannot really be solved. Indeed, if we assume that problems can be solved only algorithmically, then this is true. However, if we can find other ways to solve noncomputable problems nonalgorithmically, there is no oxymoron. Thus, hypercomputation is first about finding general nonalgorithmic methods that solve problems not solvable algorithmically and then about the application of these methods to solve particular noncomputable problems. But are there such methods? And if there
Data Loading...
