The standard theory of computation excludes computations whose completion requires an infinite number of steps. Malament-Hogarth spacetimes admit observers whose pasts contain entire future-directed, timelike half-curves of infinite proper length. We investigate the physical properties of these spacetimes and ask whether they and other spacetimes allow the observer to know the outcome of a computation with infinitely many steps.

Here we briefly review the concept of "prediction" within the context of classical relativity theory. We prove a theorem asserting that one may predict one's own future only in a closed universe. We then question whether prediction is possible at all (even in closed universes). We note that interest in prediction has stemmed from considering the epistemological predicament of the observer. We argue that the definitions of prediction found thus far in the literature do not fully appreciate this predicament. We (...) propose a more adequate alternative and show that, under this definition, prediction is essentially impossible in general relativity. (shrink)

A true Turing machine (TM) requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime (the spacetime of common sense), but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar ("close") to (...) our world. But curiously enough-and this is the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation (e.g. intuitive, finitely programmed, limited in computational capability), a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

Here, we examine hole-freeness - a condition sometimes imposed to rule out seemingly artificial spacetimes. We show that under existing definitions (and contrary to claims made in the literature) there exist inextendible, globally hyperbolic spacetimes which fail to be hole-free. We then propose an updated formulation of the condition which enables us to show the intended result. We conclude with a few general remarks on the strength of the definition and then formulate a precise question which may be interpreted as: (...) Are all physically reasonable spacetimes hole-free? (shrink)