Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.

The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation which claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed—a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such a situation (...) does not occur for the methods of hypercomputation under attack, and why it is unlikely to occur for any other serious methods. Introduction Issues with specific hypermachines Conclusions for hypercomputation. (shrink)

It is shown that a number of questions, usually considered philosophical rather than scientific, can be reformulated to apply to a world of automata or "well-informed heat engines." In some cases they admit of physical answers, but in many cases obtaining answers entails violation of the second law of thermodynamics. This is demonstrated explicitly for the problem of determinism and free will, for the discovery of the origin or ultimate fate of the universe, or for the discovery of causes or (...) purposes in nature. (shrink)

Gödel's Theorem is often used in arguments against machine intelligence, suggesting humans are not bound by the rules of any formal system. However, Gödelian arguments can be used to support AI, provided we extend our notion of computation to include devices incorporating random number generators. A complete description scheme can be given for integer functions, by which nonalgorithmic functions are shown to be partly random. Not being restricted to algorithms can be accounted for by the availability of an arbitrary random (...) function. Humans, then, might not be rule-bound, but Gödelian arguments also suggest how the relevant sort of nonalgorithmicity may be trivially made available to machines. (shrink)

This open access book addresses the physical phenomenon of events that seem to occur spontaneously and without any known cause. These are to be contrasted with events that happen in a determined, predictable, lawful, and causal way. All our knowledge is based on self-reflexive theorizing, as well as on operational means of empirical perception. Some of the questions that arise are the following: are these limitations reflected by our models? Under what circumstances does chance kick in? Is chance in physics (...) merely epistemic? In other words, do we simply not know enough, or use too crude levels of description for our predictions? Or are certain events "truly", that is, irreducibly, random? The book tries to answer some of these questions by introducing intrinsic, embedded observers and provable unknowns; that is, observables and procedures which are certified to be unknowable or undoable. A review of quantum mechanics is presented which is inspired by quantum logic. Postulated quantum knowables are reviewed. More exotic unknowns originate in the assumption of classical continua, and in finite automata and generalized urn models, which mimic complementarity and yet maintain value definiteness. Traditional conceptions of free will, miracles and dualistic interfaces are based on gaps in an otherwise deterministic universe. (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)

We establish a connection between measurement-based quantum computation and the field of mathematical logic. We show that the computational power of an important class of quantum states called graph states, representing resources for measurement-based quantum computation, is reflected in the expressive power of (classical) formal logic languages defined on the underlying mathematical graphs. In particular, we show that for all graph state resources which can yield a computational speed-up with respect to classical computation, the underlying graphs—describing the quantum correlations of (...) the states—are associated with undecidable logic theories. Here undecidability is to be interpreted in a sense similar to Gödel’s incompleteness results, meaning that there exist propositions, expressible in the above classical formal logic, which cannot be proven or disproven. (shrink)

It is shown that it is impossible for an observer to distinguish all present states of a system in which he or she is contained, irrespective of whether this system is a classical or a quantum mechanical one and irrespective of whether the time evolution is deterministic or stochastic. As a corollary, this implies that it is impossible for an observer to measure the EPR-correlations between himself or herself and an outside system. Implications of the main result are discussed for (...) how we have to conceive of universally valid theories. (shrink)

Virtual physics is the study of the intrinsic perception of computer-generated universes. Algorithmic physics is the study of physical systems by methods developed in formal logic and the computer sciences. Both fields of research may be conceived as two sides of the same constructivistic attempt to re-interpret physical indeterminism and undecidability. In that way, virtual reality is a powerful “intuition pump” for algorithmic physics, and vice versa.

We present a toy theory that is based on a simple principle: the number of questions about the physical state of a system that are answered must always be equal to the number that are unanswered in a state of maximal knowledge. Many quantum phenomena are found to have analogues within this toy theory. These include the noncommutativity of measurements, interference, the multiplicity of convex decompositions of a mixed state, the impossibility of discriminating nonorthogonal states, the impossibility of a universal (...) state inverter, the distinction between bipartite and tripartite entanglement, the monogamy of pure entanglement, no cloning, no broadcasting, remote steering, teleportation, entanglement swapping, dense coding, mutually unbiased bases, and many others. The diversity and quality of these analogies is taken as evidence for the view that quantum states are states of incomplete knowledge rather than states of reality. A consideration of the phenomena that the toy theory fails to reproduce, notably, violations of Bell inequalities and the existence of a Kochen-Specker theorem, provides clues for how to proceed with this research program. (shrink)