✦ LIBER ✦

The Kolmogorov complexity of random reals

✍ Scribed by Liang Yu; Decheng Ding; Rodney Downey

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 296 KB
Volume: 129
Category: Article
ISSN: 0168-0072
DOI: 10.1016/j.apal.2004.01.006

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Kolmogorov complexity and random graphs

✍ W.W. Kirchherr 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 445 KB

On the Kolmogorov Complexity of Arbitrar

On the Kolmogorov Complexity of Arbitrary Objects

✍ Aaron Shenhar 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 795 KB

The notion of Kolmogorov program-size complexity (or algorithmic information) is defined here for arbitrary objects. Using a special form of recursive topological spaces, called partition spaces, we define a recursive topology which uses a level of partition for approximation of arbitrary objects in

On hausdorff and topological dimensions

On hausdorff and topological dimensions of the kolmogorov complexity of the real line

✍ Jin-yi Cai; Juris Hartmanis 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 767 KB

We investigate the Kolmogorov complexity of real numbers. Let K be the Kolmogorov complexity function; we determine the Hausdorff dimension and the topological dimension of the graph of K. Since these dimensions are different, the graph of the Kolmogorov complexity function of the real line forms a

On the Kolmogorov complexity of function

On the Kolmogorov complexity of functions of finite smoothness

✍ Yuly Makovoz 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 467 KB

Complexity of reals in inner models of s

Complexity of reals in inner models of set theory

✍ Boban Velickovic; W.Hugh Woodin 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 931 KB

We consider the possible complexity of the set of reals belonging to an inner model M of set theory. We show that if this set is analytic then either l-2, M is countable or else all reals are in M. We also show that if an inner model contains a superperfect set of reals as a subset then it contains

An Excursion to the Kolmogorov Random St

An Excursion to the Kolmogorov Random Strings

✍ Harry Buhrman; Elvira Mayordomo 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 809 KB

We study the sets of resource-bounded Kolmogorov random strings: . We show that the class of sets that Turing reduce to R t has measure 0 in EXP with respect to the resource-bounded measure introduced by Lutz. From this we conclude that R t is not Turing-complete for EXP. This contrasts with the re