×

The extent of computation in Malament-Hogarth spacetimes. (English) Zbl 1154.83301

Summary: We analyse the extent of possible computations following Hogarth (2004) conducted in Malament-Hogarth (MH) spacetimes, and Etesi and Németi (2002) in the special subclass containing rotating Kerr black holes. Hogarth (1994) had shown that any arithmetic statement could be resolved in a suitable MH spacetime. Etesi and Németi (2002) had shown that some \(\forall \exists\) relations on natural numbers that are neither universal nor co-universal, can be decided in Kerr spacetimes, and had asked specifically as to the extent of computational limits there. The purpose of this note is to address this question, and further show that MH spacetimes can compute far beyond the arithmetic: effectively Borel statements (so hyperarithmetic in second-order number theory, or the structure of analysis) can likewise be resolved:
Theorem A. If \(H\) is any hyperarithmetic predicate on integers, then there is an \(MH\) spacetime in which any query ? \(n\in H\) ? can be computed.
In one sense this is best possible, as there is an upper bound to computational ability in any spacetime, which is thus a universal constant of that spacetime.
Theorem C. Assuming the (modest and standard) requirement that spacetime manifolds be paracompact and Hausdorff, for any spacetime \(\mathcal M\) there will be a countable ordinal upper bound, \(w(\mathcal M)\), on the complexity of questions in the Borel hierarchy computable in it.

MSC:

83A05 Special relativity
03D20 Recursive functions and relations, subrecursive hierarchies
03E15 Descriptive set theory
PDFBibTeX XMLCite
Full Text: DOI arXiv