Jarkko KARI


Jonathan MILLS

James M. NYCE


Gabriela QUEIROZ


Philip WELCH

Relativistic Computers and Transfinite Computation

Abstract. Various proposals have been made that seek to exploit special features of general relativistic spacetime solutions (principally by Pitowsky, Hogarth, and Etesi & Németi). Initially the authors sought to decide universal predicates over the natural numbers (such as answering Goldbach's Conjecture, or Fermat's Last Theorem), but it was noticed that by suitable signalling arrangements differences of such predicates could be computed (Etesi-Németi) and even the truth of any arithmetic statement (Hogarth). The latter involved stacking components of spacetime regions with suitable Turing machines acting along worldlines of infinite proper time. It is possible to give a logical analysis of the extent of computations possible in such so-called Malament-Hogarth spacetimes, using these kinds of arrangement (and the outcome is that is far beyond arithmetic). However a simple argument shows that for any universe, indeed our own, there is a universal constant that is an upper bound to the complexity of questions decidable in such spacetimes. However subtler questions arise regarding recognisability of such regions for the job under discussion. It is further possible to view these kinds of stacked regions as a special case of an analysis of stacked Turing machines in general. These can be simulated by allowing Turing machines (or register machines) to run transfinitely. This conceptual model has in recent years been the subject of research activity in a number of locations, and can be regarded as a laboratory for discrete hypercomputations of such a type, just as Turing's original machine became a laboratory for testing various notions of (standard) computation. We review this work further here.