| Editorial Future Trends in Hypercomputation Mike Stannett How powerful a tool is unconventional computing? Are we developing more of the same, or are our devices and theories fundamentally different from those that can be modelled by the Turing machine? This question lies at the heart of hypercomputation theory (the investigation whether logical and physical systems can be more powerful than Turing machines), and offers insights into both the nature of computation, and the nature of physics itself. By developing a better understanding of the limits that physics places on buildable systems, we gain at the same time a better understanding of the systems that Nature itself can produce. Answering this question is, inevitably, fraught with difficulty; but the papers in this collection are part of the ongoing attempt. Computational power (identifying the class of problems that can be solved using any given class of machines) is inherently concerned with the infinite; for if we limit ourselves to machines using finite discrete resources in finite discrete time, we can go no further than the finite state machine. Turing machines and quantum computers overcome this restriction by assuming that, while resources may be finite, they are nonetheless unbounded. Analog models takes advantage of continuity, a mathematical assumption that allows infinitely many operations to be carried out in finite time. Are either of these assumptions justified? It is currently impossible to say, because the answers depend on a firmer understanding of Nature itself. Is the Universe infinite? Can time be infinitely divided, or is a fundamental limit imposed by quantum theory? It is more than a century since work began on relativity and quantum physics, but our understanding of physics remains incomplete, and without a comprehensive model of reality, we cannot deduce the limiting properties of physical devices from first principles. But this is no reason to abandon the quest. On the contrary, it encourages us to redouble our efforts, to investigate the models that each version of physics can support. Only in this way can we meaningfully design devices and experiments capable of establishing, and exploiting, the underlying structures of physics. ABOUT THE PAPERS Taking us into the realms of advanced theory,Wells addresses a puzzle first raised during a conversation with Tarski, in which the latter suggested that an avowedly nonrecursive system might nonetheless be decidable. Ord and Kieu turn the spotlight on a much simpler system, the throw of a biassed coin, and consider the extent to which it can be used as an oracle. Much research has been done on systems that extend Turing computation; in contrast, MacLennan investigates the role of Natural Computation, while Stepney asks about systems that extend non-classical paradigms. Hogarth discusses one such paradigm: computations that exploit relativistic cosmological singularities. Kieu discusses a non-standard approach to quantum computing that appears to support hypercomputation (various early criticisms of this approach are discussed and addressed). Finally, Love takes us back to the origins of modern computation, by considering forgotten issues in early metamathematics, and their consequences. ACKNOWLEDGMENTS |
|||