๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by Jin-yi Cai; Juris Hartmanis

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
767 KB
Volume
49
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 fractal in the sense of Mandelbrot. We also solve an open problem of Razborov using our exact bound on the topological dimension.

๐Ÿ“œ SIMILAR VOLUMES

The Kolmogorov complexity of random real
The Kolmogorov complexity of random reals
โœ Liang Yu; Decheng Ding; Rodney Downey ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 296 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