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)

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.

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)

Gödel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.

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)

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)