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)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 9,357
External links
  •   Try with proxy.
  • Through your library Configure
    References found in this work BETA
    E. Mark Gold (1965). Limiting Recursion. Journal of Symbolic Logic 30 (1):28-48.
    Mark Hogarth (2004). Deciding Arithmetic Using SAD Computers. British Journal for the Philosophy of Science 55 (4):681-691.
    István Németi & Gyula Dávid (2006). Relativistic Computers and the Turing Barrier. Journal of Applied Mathematics and Computation 178:118--42.

    View all 6 references

    Citations of this work BETA
    Tim Button (2009). Sad Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
    Gualtiero Piccinini (2011). The Physical Church–Turing Thesis: Modest or Bold? British Journal for the Philosophy of Science 62 (4):733 - 769.
    Similar books and articles
    Analytics

    Monthly downloads

    Added to index

    2009-01-28

    Total downloads

    25 ( #58,686 of 1,088,623 )

    Recent downloads (6 months)

    10 ( #11,009 of 1,088,623 )

    How can I increase my downloads?

    My notes
    Sign in to use this feature


    Discussion
    Start a new thread
    Order:
    There  are no threads in this forum
    Nothing in this forum yet.