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)

In his recent article On Relativity Theory and Openness of the Future (1991), Howard Stein proves not only that one can define an objective becoming relation in Minkowski spacetime, but that there is only one possible definition available if one accepts certain natural assumptions about what it is for becoming to occur and for it to be objective. Stein uses the definition supplied by his proof to refute an argument due to Rietdijk (1966, 1976), Putnam (1967) and Maxwell (1985, 1988) (...) that Minkowski spacetime leaves no room for objective becoming whatsoever. However, Stein's proof does not seem to go far enough. By considering only what events have become from the standpoint of any given event, Stein's uniqueness proof fails from the outset to allow for a more general kind of becoming whereby it is understood to occur from the standpoint of events on the particular worldlines followed by observers. This suggests that there may, after all, be more than one way to define objective becoming in Minkowski spacetime once each observer's worldline is allowed to figure in the definition. This suspicion is further aroused by two recent proposals for objective, worldline-dependent becoming due to Peacock (1992) and Muller (1992) who advocate ways of defining becoming that are not equivalent to the definition Stein's uniqueness proof delivers. Nevertheless, we show that Stein's uniqueness proofcan be extended in a natural way to cover this more general kind of becoming, provided one does not enrich standard Minkowski spacetime by privileging certain sets of worldlines over others in an unwarranted manner. Thus we aim to reinforce Stein's point that standard Minkowski spacetime does make room for objective becoming, but in essentially only one way, despite arguments and proposals to the contrary. (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)

Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.

This collection of articles on the theme of space and time covers such broad topics as the philosophy of spacetime, spacetime structure, spacetime ontology, the epistemology of geometry, and general relativity.