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.

For much of this century, philosophers hoped that Einstein’s general theory of relativity would play the role of physician to philosophy. Its development would positively influence the philosophy of methodology and confirmation, and its ontology would answer many traditional philosophical debates—for example, the issue of spacetime substantivalism. In physics, by contrast, the attitude is increasingly that GTR itself needs a physician. The more we learn about GTR the more we discover how odd are the spacetimes that it allows. Not only (...) does GTR permit singularities, naked and clothed, but it allows time travel, topology change, and event and particle horizons, to name but a few of these oddities. Rather than revel in the riches of the theory, however, many physicists seek to rule out one or more of the above “pathologies” on the grounds that they are “physically unreasonable.” Thus contemporary researchers hawk various “cures” for the “illnesses” of GTR: among them, Chronology Protection to ensure against time travel, Cosmic Censorship for naked singularities, Inflation for horizons, and so on. The physics of these illnesses and cures, and the problems they engender, are the source of much controversy in the physics literature. Philosophers have largely neglected it. But clearly the subject needs philosophers of physics to determine whether the patient is genuinely ailing, and if so, to sift the real antidotes from the snake oil. (shrink)

Indeed, this is the first serious book-length study of the subject by a philosopher of science.

A true Turing machine requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime, 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 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, 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)

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)