The extent of computation in malament–hogarth spacetimes

British Journal for the Philosophy of Science 59 (4):659-674 (2008)
  Copy   BIBTEX

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?

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
77 (#159,035)

6 months
1 (#448,551)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
Epistemic Holes and Determinism in Classical General Relativity.Juliusz Doboszewski - 2020 - British Journal for the Philosophy of Science 71 (3):1093-1111.
SAD computers and two versions of the Church–Turing thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Supertasks.Jon Pérez Laraudogoitia - 2008 - Stanford Encyclopedia of Philosophy.

View all 9 citations / Add more citations

References found in this work

Limiting recursion.E. Mark Gold - 1965 - Journal of Symbolic Logic 30 (1):28-48.
Non-Turing Computers and Non-Turing Computability.Mark Hogarth - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:126-138.

View all 11 references / Add more references