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

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set (...) to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}$ sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not ${n \in r}$ with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs. (shrink)

A solution to the measurement problem of quantum mechanics is proposed within the framework of an intepretation according to which only quantum systems with an infinite number of degrees of freedom have determinate properties, i.e., determinate values for (some) observables of the theory. The important feature of the infinite case is the existence of many inequivalent irreducible Hilbert space representations of the algebra of observables, which leads, in effect, to a restriction on the superposition principle, and hence the possibility of (...) defining (macro-) observables which commute with every observable. Such observables have determinate values which are not subject to quantum interference effects. A measurement process is schematized as an interaction between a microsystem and a macrosystem, idealized as an infinite quantum system, and it is shown that there exists a unitary transformation which transforms the initial pure state of the composite system in a finite time (the duration of the interaction) into the required mixture of disjoint states. (shrink)

This article addresses the question whether supertasks are possible within the context of non-relativistic quantum mechanics. The supertask under consideration consists of performing an infinite number of quantum mechanical measurements in a finite amount of time. Recent arguments in the physics literature claim to show that continuous measurements, understood as N discrete measurements in the limit where N goes to infinity, are impossible. I show that there are certain kinds of measurements in quantum mechanics for which these arguments break down. (...) This suggests that there is a new context in which quantum mechanics, in principle, permits the performance of a supertask. (shrink)

Pulier (2000, Theory and Decision 49: 291) and Machina (2000, Theory and Decision 49: 293) seek to dissolve the Barrett–Arntzenius infinite decision puzzle (1999, Theory and Decision 46: 101). The proposed dissolutions, however, are based on misunderstandings concerning how the puzzle works and the nature of supertasks more generally. We will describe the puzzle in a simplified form, address the recent misunderstandings, and describe possible morals for decision theory.

We tell a story where an agent who chooses in such a way as to make the greatest possible profit on each of an infinite series of transactions ends up worse off than an agent who chooses in such a way as to make the least possible profit on each transaction. That is, contrary to what one might suppose, it is not necessarily rational always to choose the option that yields the greatest possible profit on each transaction.

An infinite number of elastically colliding balls is considered in a classical, and then in a relativistic setting. Energy and momentum are not necessarily conserved globally, even though each collision does separately conserve them. This result holds in particular when the total mass of all the balls is finite, and even when the spatial extent and temporal duration of the process are also finite. Further, the process is shown to be indeterministic: there is an arbitrary parameter in the general solution (...) that corresponds to the injection of an arbitrary amount of energy (classically), or energy-momentum (relativistically), into the system at the point of accumulation of the locations of the balls. Specific examples are given that illustrate these counter-intuitive results, including one in which all the balls move with the same velocity after every collision has taken place. (shrink)

An actual infinity of colliding balls can be in a configuration in which the laws of mechanics lead to logical inconsistency. It is argued that one should therefore limit the domain of these laws to a finite, or only a potentially infinite number of elements. With this restriction indeterminism, energy nonconservation and creatio ex nihilo no longer occur. A numerical analysis of finite systems of colliding balls is given, and the asymptotic behaviour that corresponds to the potentially infinite system is (...) inferred. (shrink)

A Zenonian supertask involving an infinite number of colliding balls is considered, under the restriction that the total mass of all the balls is finite. Classical mechanics leads to the conclusion that momentum, but not necessarily energy, must be conserved. Relativistic mechanics, on the other hand, implies that energy and momentum conservation are always violated. Quantum mechanics, however, seems to rule out the Zeno configuration as an inconsistent system.

A Zenonian supertask involving an infinite number of identical colliding balls is generalized to include balls with different masses. Under the restriction that the total mass of all the balls is finite, classical mechanics leads to velocities that have no upper limit. Relativistic mechanics results in velocities bounded by that of light, but energy and momentum are not conserved, implying indeterminism. The notion that both determinism and the conservation laws might be salvaged via photon creation is shown to be flawed.

In the paper below the authors describe three super-tasks. They show that although the abstract notion of a super-task may be, as Benacerraf suggested, a conceptual mismatch, the completion of the three super-tasks involved can be defined rather naturally, without leading to inconsistency, by means of a particular kinematical interpretation combined with a principle of continuity.

In an earlier paper the authors discussed some super-tasks by means of a kinematical interpretation. In the present paper we show a semi-formal way that a more abstract treatment is possible. The core idea of our approach is simple: if a super-task can be considered as a union of (finite) tasks, it is natural to define the effect of the super-task as the union of the effects of the finite tasks it consists of. We show that this approach enables us (...) to handle two of the three super-tasks that we discussed earlier. We also argue that recent objections against our original kinematical interpretation do not hold water. One of our arguments is based on the construction of an elegant correspondence between the first of those three super-tasks and Zeno's Achilles and the Tortois. (shrink)

There are various equivalent formulations of the Church-Turing thesis. A common one is that every effective computation can be carried out by a Turing machine. The Church-Turing thesis is often misunderstood, particularly in recent writing in the philosophy of mind.

Malament-Hogarth spacetimes are the sort of models within general relativity that seem to allow for the possibility of supertasks. There are various ways in which these spacetimes might be considered physically problematic. Here, we examine these criticisms and investigate the prospect of escaping them.

This is a book that no one but Weyl could have written--and, indeed, no one has written anything quite like it since.

We argue that not all cases of before-effect involve causation and ask how to demarcate cases of before-effect in which the events that follow exert causal influence over the before-effect from cases in which they do not.

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? (shrink)

We consider various concepts associated with the revision theory of truth of Gupta and Belnap. We categorize the notions definable using their theory of circular definitions as those notions universally definable over the next stable set. We give a simplified account of varied revision sequences-as a generalised algorithmic theory of truth. This enables something of a unification with the Kripkean theory of truth using supervaluation schemes.

In [7], open questions are raised regarding the computational strengths of so-called ∞-α -Turing machines, a family of models of computation resembling the infinite-time Turing machine model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals α such that Tα≻TωTα≻Tω, the (...) smallest of which is precisely γ , the supremum of ordinals clockable by TωTω. In fact, there is a hierarchy of countable TαTαs of increasing strength corresponding to the transfinite Turing-jump operator ▼. There is a countable ordinal μ such that neither Tμ⪰Tω1Tμ⪰Tω1 nor Tμ⪯Tω1Tμ⪯Tω1—that is, the models TμTμ and Tω1Tω1 are computation-strength incommensurable . A similar fact holds for any larger uncountable device replacing Tω1Tω1. Further observations are made about countable TαTα. (shrink)

That quantum mechanical measurement processes are indeterministic is widely known. The time evolution governed by the differential Schrödinger equation can also be indeterministic under the extreme conditions of a quantum supertask, the quantum analogue of a classical supertask. Determinism can be restored by requiring normalizability of the supertask state vector, but it must be imposed as an additional constraint on the differential Schrödinger equation.

This article shows a clear sense in which general relativity allows for a type of ‘machine’ that can bring about a spacetime structure suitable for the implementation of ‘supertasks’. 1Introduction2Preliminaries3Malament–Hogarth Spacetimes4Machines5Malament–Hogarth Machines6Conclusion.

We describe the solution of the Limit Rule Problem of Revision Theory and discuss the philosophical consequences of the fact that the truth set of Revision Theory is a complete 1/2 set.

We attempt to clarify the main conceptual issues in approaches to ‘objectification’ or ‘measurement’ in quantum mechanics which are based on superselection rules. Such approaches venture to derive the emergence of classical ‘reality’ relative to a class of observers; those believing that the classical world exists intrinsically and absolutely are advised against reading this paper. The prototype approach (K. Hepp, Helv. Phys. Acta45 (1972), 237–248) where superselection sectors are assumed in the state space of the apparatus is shown to be (...) untenable. Instead, one should couple system and apparatus to an environment, and postulate superselection rules for the latter. These are motivated by the locality of any observer or other (actual or virtual) monitoring system. In this way ‘environmental’ solutions to the measurement problem (H.D. Zeh, Found. Phys.1 (1970), 69–76; W. H. Zurek, Phys. Rev.D26 (1982), 1862–1880 and Progr. Theor. Phys.89 (1993), 281–312) become consistent and acceptable, too. Points of contact with the modal interpretation are briefly discussed. We propose a minimal value attribution to observables in theories with superselection rules, in which only central observables have properties. In particular, the eigenvector-eigenvalue link is dropped. This is mainly motivated by Ockham's razor. (shrink)

We define the notion of ordinal computability by generalizing standard Turing computability on tapes of length ω to computations on tapes of arbitrary ordinal length. We show that a set of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of Gödel's constructible universe L. This characterization can be used to prove the generalized continuum hypothesis in L.

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the (...) algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory. (shrink)

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Everyset. for example, is decidable by such machines, and the semi-decidable sets form a portion of thesets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

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.

Determinism fails easily if spacetimes with points removed from the spacetime manifold are taken to be physically reasonable representations of a way the world could be according to classical general relativity. I discuss a recently proposed condition for determining which spacetimes have holes—epistemic hole freeness—and show that epistemic hole freeness gives the correct verdict in some non-globally hyperbolic spacetimes with a closed subset removed, certain spacetimes with genuinely indeterministic features count as having an epistemic hole, which implies that the requirement (...) of epistemic hole freeness enforces a form of determinism, and there is a large class of spacetimes that intuitively are radically indeterministic and unphysical due to containing a hole, but are free from epistemic holes. I show that a few natural ways of remedying are not satisfactory. (shrink)

This paper is an enquiry into the logical, metaphysical, and physical possibility of time travel understood in the sense of the existence of closed worldlines that can be traced out by physical objects. We argue that none of the purported paradoxes rule out time travel either on grounds of logic or metaphysics. More relevantly, modern spacetime theories such as general relativity seem to permit models that feature closed worldlines. We discuss, in the context of Gödel's infamous argument for the ideality (...) of time based on his eponymous spacetime, what this apparent physical possibility of time travel means. Furthermore, we review the recent literature on so-called time machines, i.e., of devices that produce closed worldlines where none would have existed otherwise. Finally, we investigate what the implications of the quantum behaviour of matter for the possibility of time travel might be and explicate in what sense time travel might be possible according to leading contenders for full quantum theories of gravity such as string theory and loop quantum gravity. (shrink)

It is widely held that the paradox of Achilles and the Tortoise, introduced by Zeno of Elea around 460 B.C., was solved by mathematical advances in the nineteenth century. The techniques of Weierstrass, Dedekind and Cantor made it clear, according to this view, that Achilles’ difficulty in traversing an infinite number of intervals while trying to catch up with the tortoise does not involve a contradiction, let alone a logical absurdity. Yet ever since the nineteenth century there have been dissidents (...) claiming that the apparatus of Weierstrass et al. has not resolved the paradox, and that serious problems remain. It seems that these claims have received unexpected support from recent developments in mathematical physics. This support has however remained largely unnoticed by historians of philosophy, presumably because the relevant debates are cast in mathematical-technical terms that are only accessible to people with the relevant training. That is unfortunate, since the debates in question might well profit from input by philosophers in general and historians of philosophy in particular. Below we will first recall the Achilles paradox, and describe the way in which nineteenth century mathematics supposedly solved it. Then we discuss recent work that contests this solution, reiterating the dissident dogma that no mathematical approach whatsoever can even come close to solving the original Achilles. We shall argue that this dissatisfaction with a mathematical solution is inadequate as it stands, but that it can perhaps be reformulated in the light of new developments in mathematical physics. (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)

Recent years have seen a growing consensus in the philosophical community that the grandfather paradox and similar logical puzzles do not preclude the possibility of time travel scenarios that utilize spacetimes containing closed timelike curves. At the same time, physicists, who for half a century acknowledged that the general theory of relativity is compatible with such spacetimes, have intensely studied the question whether the operation of a time machine would be admissible in the context of the same theory and of (...) its quantum cousins. A time machine is a device which brings about closed timelike curves—and thus enables time travel—where none would have existed otherwise. The physics literature contains various no-go theorems for time machines, i.e., theorems which purport to establish that, under physically plausible assumptions, the operation of a time machine is impossible. We conclude that for the time being there exists no conclusive no-go theorem against time machines. The character of the material covered in this article makes it inevitable that its content is of a rather technical nature. We contend, however, that philosophers should nevertheless be interested in this literature for at least two reasons. First, the topic of time machines leads to a number of interesting foundations issues in classical and quantum theories of gravity; and second, philosophers can contribute to the topic by clarifying what it means for a device to count as a time machine, by relating the debate to other concerns such as Penrose's cosmic censorship conjecture and the fate of determinism in general relativity theory, and by eliminating a number of confusions regarding the status of the paradoxes of time travel. The present article addresses these ambitions in as non-technical a manner as possible, and the reader is referred to the relevant physics literature for details. (shrink)

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)