The extent of computation in malament–hogarth spacetimes
British Journal for the Philosophy of Science 59 (4):659-674 (2008)
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?DOI
10.1093/bjps/axn031
My notes
Similar books and articles
A twist in the geometry of rotating Black holes: Seeking the cause of acausality.Christian Wüthrich, Hajnal Andréka & István Németi - manuscript
Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes.John Earman & John D. Norton - 1993 - Philosophy of Science 60 (1):22-42.
On the physical possibility of ordinal computation (draft).Jeffrey A. Barrett & Wayne Aitken - unknown
On the Possibility of Supertasks in General Relativity.John Byron Manchak - 2010 - Foundations of Physics 40 (3):276-288.
Hyperloops do not threaten the notion of an effective procedure.Tim Button - 2009 - Lecture Notes in Computer Science 5635:68-78.
The inductive significance of observationally indistinguishable spacetimes: (Peter Achinstein has the last laugh).John D. Norton - unknown
Non-Turing Computations via Malament-Hogarth space-times.Gábor Etesi & István Németi - 2002 - International Journal of Theoretical Physics 41:341--70.
Analytics
Added to PP
2009-01-28
Downloads
77 (#159,035)
6 months
1 (#448,551)
2009-01-28
Downloads
77 (#159,035)
6 months
1 (#448,551)
Historical graph of 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.
The dependence of computability on numerical notations.Ethan Brauer - 2020 - Synthese 198 (11):10485-10511.
References found in this work
Trial and error predicates and the solution to a problem of Mostowski.Hilary Putnam - 1965 - Journal of Symbolic Logic 30 (1):49-57.
Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes.John Earman & John D. Norton - 1993 - Philosophy of Science 60 (1):22-42.
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.