Skip Navigation

The British Journal for the Philosophy of Science 2008 59(4):659-674; doi:10.1093/bjps/axn031
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Welch, P. D.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author (2008). Published by Oxford University Press. For Permissions, please email: journals.permissions@oxfordjournals.org

The Extent of Computation in Malament–Hogarth Spacetimes

P. D. Welch

School of Mathematics, University of Bristol, Bristol, England BS8 1TW

p.welch{at}bristol.ac.uk


  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 {forall} exist 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 isin 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 Formula there will be a countable ordinal upper bound, Formula , on the complexity of questions in the Borel hierarchy computable in it.

  1. Introduction
    1.1 History and preliminaries

  2. Hyperarithmetic Computations in MH Spacetimes
    2.1 Generalising SADn regions
    2.2 The complexity of questions decidable in Kerr spacetimes

  3. An Upper Bound on Computational Complexity for Each Spacetime


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Br J Philos SciHome page
T. Button
SAD Computers and Two Versions of the Church-Turing Thesis
Brit J Philos Sci, December 1, 2009; 60(4): 765 - 792.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.