David Malament's (1977) well-known result, which is often taken to show the uniqueness of the Poincare-Einstein convention for defining simultaneity, involves an unwarranted physical assumption: that any simultaneity relation must remain invariant under temporal reflections. Once that assumption is removed, his other criteria for defining simultaneity are also satisfied by membership in the same backward (forward) null cone of the family of such cones with vertices on an inertial path. What is then unique about the Poincare-Einstein convention is that it (...) is independent of the choice of inertial path in a given inertial frame, confirming a remark in Einstein 1905. Similarly, what is unique about the backward (forward) null cone definition is that it is independent of the state of motion of an observer at a point on the inertial path. (shrink)

The chronological order of the events along a spacelike path is not invariant under Lorentz transformations, as is well known. This led to an early conviction that tachyons would give rise to causal anomalies. A relativistic version of the Stückelberg-Feynman “switching procedure” (SWP) has been invoked as the suitable tool to eliminate those anomalies. The application of the SWP does eliminate the motions backwards in time, but interchanges the roles ofsource anddetector. This fact triggered the proposal of a host of (...) causal “paradoxes.” Till now, however, it has not been recognized that such paradoxes can be sensibly discussed (and completely solved, at least “in microphysics”)only after the tachyon relativistic mechanics has been properly developed. We start by showing how to apply the SWP, both in the case ofordinary special relativity and in the case with tachyons. Then we carefully exploit the kinematics of the tachyon exchange between to (ordinary) bodies. Being finally able to tackle the tachyon causality problem, we successively solve the paradoxes of : (i) Tolman-Regge, (ii) Pirani, (iii) Edmonds, and (iv) Bell. Finally, we discuss a further, new paradox associated with the transmission of signals by modulated tachyon beams. (shrink)

Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from small (...) time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

Recent findings in the computer sciences, discrete mathematics, formal logics and metamathematics have opened up a royal road for the investigation of undecidability and randomness in physics. A translation of these formal concepts yields a fresh look into diverse features of physical modelling such as quantum complementarity and the measurement problem, but also stipulates questions related to the necessity of the assumption of continua.Conversely, any computer may be perceived as a physical system: not only in the immediate sense of the (...) physical properties of its hardware. Computers are a medium to virtual realities. The foreseeable importance of such virtual realities stimulates the investigation of an?inner description?, a?virtual physics? of these universes of computation. Indeed, one may consider our own universe as just one particular realisation of an enormous number of virtual realities, most of them awaiting discovery.One motive of this book is the recognition that what is often referred to as?randomness? in physics might actually be a signature of undecidability for systems whose evolution is computable on a step-by-step basis. To give a flavour of the type of questions envisaged: Consider an arbitrary algorithmic system which is computable on a step-by-step basis. Then it is in general impossible to specify a second algorithmic procedure, including itself, which, by experimental input-output analysis, is capable of finding the deterministic law of the first system. But even if such a law is specified beforehand, it is in general impossible to predict the system behaviour in the?distant future?. In other words: no?speedup? or?computational shortcut? is available. In this approach, classical paradoxes can be formally translated into no-go theorems concerning intrinsic physical perception.It is suggested that complementarity can be modelled by experiments on finite automata, where measurements of one observable of the automaton destroys the possibility to measure another observable of the same automaton and it vice versa.Besides undecidability, a great part of the book is dedicated to a formal definition of randomness and entropy measures based on algorithmic information theory. (shrink)