The extent of computation in malament–hogarth spacetimes


Abstract
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 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 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 there will be a countable ordinal upper bound, , on the complexity of questions in the Borel hierarchy computable in it. Introduction 1.1 History and preliminaries Hyperarithmetic Computations in MH Spacetimes 2.1 Generalising SADn regions 2.2 The complexity of questions decidable in Kerr spacetimes An Upper Bound on Computational Complexity for Each Spacetime CiteULike     Connotea     Del.icio.us     What's this?
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1093/bjps/axn031
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 41,650
Through your library

References found in this work BETA

Deciding Arithmetic Using SAD Computers.Mark Hogarth - 2004 - British Journal for the Philosophy of Science 55 (4):681-691.

View all 11 references / Add more references

Citations of this work BETA

The Physical Church-Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
Only Human: A Book Review of The Turing Guide. [REVIEW]Bjørn Kjos-Hanssen - forthcoming - Notices of the American Mathematical Society 66 (4).
SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Human-Effective Computability†.Marianna Antonutti Marfori & Leon Horsten - 2019 - Philosophia Mathematica 27 (1):61-87.

View all 7 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
41 ( #195,906 of 2,250,048 )

Recent downloads (6 months)
1 ( #1,030,887 of 2,250,048 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature