The Kolmogorov complexity of random reals (Q1887661): Difference between revisions

Crudely speaking, a real number is random iff it does not belong to any constructive set of measure 0. Randomness can be reformulated in terms of a (prefix-free) Kolmogorov complexity \(K(\alpha_{| n})\) of the initial segments of the real number \(\alpha\) (described as an infinite sequence of 0s and 1s): \(\alpha\) is random iff there exists a constant \(c\) such that for all \(n\), \(K(\alpha_{| n})\geq n-c\). Are all random numbers equally random in some sense? It is reasonable to say that a random number \(\alpha\) is ``less random'' than \(\beta\) (denoted \(\alpha\leq_K \beta\)) if \(K(\alpha_{| n})\leq K(\beta_{| n})+O(1)\). If \(\alpha\leq_K\beta\) and \(\beta\leq_K\alpha\), then \(\alpha\) and \(\beta\) are equally random; an equivalence class of equally random numbers is called a \(K\)-degree. The authors prove that there is no ``most random'' real number (in the sense of this definition), and that there are uncountably many \(K\)-degrees. They also show that there exists a random real number \(\alpha\) for which \(\limsup (K(\alpha_{| n})-K(\Omega_{| n}))=\infty\), where \(\Omega\) is Chaitin's random number -- the probability that a randomly selected Turing machine halts. They also formulate several interesting open problems: e.g., it is not even clear if it is possible for one random real number \(\alpha\) to be strictly less random than the other \(\beta\), i.e., \(\alpha\leq_K \beta\) and \(\beta\not\leq_K\alpha\).