We investigate two constants cT and rT, introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that cT does not represent the complexity of T and found that for two theories S and T, one can always find a universal Turing machine such that equation image. We prove the following are equivalent: equation image for some universal Turing machine, equation image for some universal Turing (...) machine, and T proves some Π1-sentence which S cannnot prove. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the (...) developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book constitutes the 4th volume of the FoLLI LNAI subline; containing the refereed proceedings of the 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008, held in Edinburgh, UK, in July 2008. The 21 revised full papers presented together with the abstracts of 7 tutorials and invited lectures were carefully reviewed and selected from numerous submissions. The papers cover all pertinent subjects in computer science with (...) particular interest in cross-disciplinary topics. Typical areas of interest are: foundations of computing and programming; novel computation models and paradigms; broad notions of proof and belief; formal methods in software and hardware development; logical approach to natural language and reasoning; logics of programs, actions and resources; foundational aspects of information organization, search, flow, sharing, and protection. (shrink)

This is a review of the issue of randomness in quantum mechanics, with special emphasis on its ambiguity; for example, randomness has different antipodal relationships to determinism, computability, and compressibility. Following a philosophical discussion of randomness in general, I argue that deterministic interpretations of quantum mechanics are strictly speaking incompatible with the Born rule. I also stress the role of outliers, i.e. measurement outcomes that are not 1-random. Although these occur with low probability, their very existence implies that the no-signaling (...) principle used in proofs of randomness of outcomes of quantum-mechanical measurements should be reinterpreted statistically, like the second law of thermodynamics. In three appendices I discuss the Born rule and its status in both single and repeated experiments, review the notion of 1-randomness that in various guises was investigated by Kolmogorov and others and treat Bell’s Theorem and the Free Will Theorem with their implications for randomness. (shrink)

Wie ist es wohl, eine Fledermaus zu sein? Wäre ein rein physikalisches Duplikat von mir nur ein empfindungsloser Zombie? Muss man sich seinem Schicksal ergeben, wenn man sich unfreiwillig als lebensnotwendige Blutwaschanlage eines weltberühmten Violinisten wieder findet? Kann man sich wünschen, der König von China zu sein? Bin ich vielleicht nur ein Gehirn in einem Tank mit Nährflüssigkeit, das die Welt von einer Computersimulation vorgegaukelt bekommt? Worauf beziehen sich die Menschen auf der Zwillingserde mit ihrem Wort 'Wasser', wenn es bei (...) ihnen gar kein H2O gibt? -/- Diese und weitere seltsame Fragen sind das tägliche Brot vieler professioneller Philosophen. Die abstrusen Umstände, die dabei geschildert werden, nennt man "Gedankenexperimente". -/- Was soll die Erörterung dieser Szenarien, die sich so weit von unserem alltäglichen Leben, z.T. außerhalb der Grenzen unserer Wirklichkeit abspielen? Welche Rolle spielen diese "Gedankenexperimente" in der philosophischen Methodologie? Ist diese Rolle überhaupt berechtigt? -/- Das vorliegende Buch gibt Antworten auf diese Fragen. Es stellt sich heraus, dass diese seltsamen Gedankenexperimente nicht nur berechtigte, sondern überaus wichtige Instrumente philosophischen Forschens darstellen. (shrink)

In this paper I discuss possible ways of measuring the power of arithmetical theories, and the possiblity of making an explication in Carnap's sense of this concept. Chaitin formulates several suggestions how to construct measures, and these suggestions are reviewed together with some new and old critical arguments. I also briefly review a measure I have designed together with some shortcomings of this measure. The conclusion of the paper is that it is not possible to formulate an explication of the (...) concept. (shrink)

Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations.

Review of "Exploring Randomness" (200) and "The Unknowable" (1999) by Gregory Chaitin.

Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a (...) PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree. (shrink)