British Journal for the Philosophy of Science 59 (4):659-674 (2008)
|Abstract||We analyse the extent of possible computations following Hogarth () conducted in Malament–Hogarth (MH) spacetimes, and Etesi and Németi () in the special subclass containing rotating Kerr black holes. Hogarth () had shown that any arithmetic statement could be resolved in a suitable MH spacetime. Etesi and Németi () 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)|
|Through your library||Configure|
Similar books and articles
Christian Wüthrich, Hajnal Andréka & István Németi, A Twist in the Geometry of Rotating Black Holes: Seeking the Cause of Acausality.
John Earman & John D. Norton (1993). Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes. Philosophy of Science 60 (1):22-42.
John Byron Manchak (2010). On the Possibility of Supertasks in General Relativity. Foundations of Physics 40 (3):276-288.
Tim Button (2009). Hyperloops Do Not Threaten the Notion of an Effective Procedure. Lecture Notes in Computer Science 5635:68-78.
Gábor Etesi & István Németi (2002). Non-Turing Computations Via Malament-Hogarth Space-Times. International Journal of Theoretical Physics 41:341--70.
John Byron Manchak (forthcoming). Is Spacetime Hole-Free? General Relativity and Gravitation.
Glenn Parsons & Patrick McGivern (2001). Can the Bundle Theory Save Substantivalism From the Hole Argument? Proceedings of the Philosophy of Science Association 2001 (3):S358-.
Added to index2009-01-28
Total downloads24 ( #57,817 of 722,838 )
Recent downloads (6 months)21 ( #6,156 of 722,838 )
How can I increase my downloads?