The Kolmogorov complexity of random reals
type: Item
instance of: scholarly article
title: The Kolmogorov complexity of random reals
zbMATH Open document ID: 1065.03025
author: Liang Yu
author: Decheng Ding
author: Rodney G. Downey
published in: Annals of Pure and Applied Logic
publication date: 2004-11-22T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 03D80
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 2117330
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: random reals
reviewed by: Vladik Kreinovich
MaRDI profile type: Publication
full work available at URL: j.apal.2004.01.006
OpenAlex ID: W2135826414
cites work: Q4381402
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Incompleteness theorems for random reals
cites work: Information, randomness and incompleteness. Papers on algorithmic information theory
cites work: Q5316387
cites work: Algorithmic Randomness and Complexity
cites work: Q4460833
cites work: Randomness and recursive enumerability
cites work: Q4070738
cites work: The definition of random sequences
cites work: Q4023358
cites work: Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
cites work: Q4040892
cites work: A formal theory of inductive inference. Part II
cites work: Von Mises' definition of random sequences reconsidered
cites work: There are 2^{ℵ₀} many 𝐻-degrees in the random reals
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
DOI: 10.1016/J.APAL.2004.01.006
Recommended article: Q4934359
Recommended article: Kolmogorov Complexity Theory over the Reals
Recommended article: On the Kolmogorov Complexity of Continuous Real Functions
Recommended article: On the Kolmogorov complexity of continuous real functions
Recommended article: The Kolmogorov complexity of real numbers.
Recommended article: Q3974885
Recommended article: Randomness and Intractability in Kolmogorov Complexity
Recommended article: Kolmogorov complexity and Hausdorff dimension
Recommended article: Incompleteness theorems for random reals
description: scientific article; zbMATH DE number 2117330