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 paper aims to outline an analysis and interpretation of the process that led to First-Order Logic and its consolidation as a core system of modern logic. We begin with an historical overview of landmarks along the road to modern logic, and proceed to a philosophical discussion casting doubt on the possibility of a purely rational justification of the actual delimitation of First-Order-Logic. On this basis, we advance the thesis that a certain historical tradition was essential to the emergence of (...) modern logic; this traditional context is analyzed as consisting in some guiding principles and, particularly, a set of exemplares (i.e., paradigmatic instances). Then, we proceed to interpret the historical course of development reviewed in section 1, which can broadly be described as a two-phased movement of expansion and then restriction of the scope of logical theory. We shall try to pinpoint ambivalencies in the process, and the main motives for subsequent changes. Among the latter, one may emphasize the spirit of modern axiomatics, the situation of foundational insecurity in the 1920s, the resulting desire to find systems well-behaved from a proof-theoretical point of view, and the metatheoretical results of the 1930s. Not surprisingly, the mathematical and, more specifically, the foundational context in which Firs-Order-Logic matured will be seen to have played a primary role in its shaping. (shrink)

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.

This paper is an amalgam of physics and mathematical logic. It contains an elementary axiomatization of spacetime in terms of the primitive concepts of particle, signal, and transmission and reception. In the elementary language formed with these predicates we state AxiomsE, C, andU, which are naturally interpretable as basic physical properties of particles and signals. We then determine all mathematical models of this axiom system; these represent certain generalizations of the standard model. Also, the automorphism groups of the models are (...) determined. Finally we give another physical model and discuss the philosophical implications. (shrink)

We discuss the possibility to build and operate a time machine, a device that produces closed timelike curves. We specify the spacetime structure needed to implement a time machine and assess attempted no-go results against time machines in classical general relativity, semi-classical quantum gravity, quantum field theory on curved spacetime, and in Euclidean quantum gravity. Such no-go theorems for time machines would show that, under physically reasonable conditions, CTCs cannot develop in spacetimes initially free of these pathologies. Our review indicates (...) that an investigation of the prospects of achieving no-go results has not been entirely successful in establishing such generality. At the same time, the pursuit of chronology protection results has proved to be a fruitful way to probe the foundations of classical GTR and the interface between general relativity and quantum field theory. (shrink)