Future Trends in Hypercomputation
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
Just as there are researchers committed to the possibility of hypercomputers, so others consider the topic a non-subject. Loff and Costa’s paper puts things into perspective, reviewing a number of interpretations and misunderstandings. Kugel’s reminds us that even a Turing machine can compute non-recursive functions if we simply change our view as to what constitutes a ‘computation’, while Cottrell, Cockshott and Michaelson consider the hypercomputational status of real-world economic systems.
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 biased 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.
Much is owed, both to the UK Engineering and Physical Science Research Council, and the White Rose Universities Consortium, who supported a hypercomputation workshop at Sheffield University in 2006, attended by researchers from many different disciplines. The EPSRC have since agreed to fund a new Hypercomputation Research Network from 2007 to 2010; we are keen to reach out to all researchers with interests in the field. The Sheffield workshop itself would have been impossible without the support of Gillian Callaghan, Andrew Hughes and Simon Foster. Finally, a special thank you goes to Susan Stepney, for her invaluable support.