On hausdorff and topological dimensions of the kolmogorov complexity of the real line
Jin‐Yi Cai, Juris Hartmanis · Journal of Computer and System Sciences · 1994
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.