Title :
The complexity of the real line is a fractal
Author :
Cai, Jan-yi ; Hartmanis, Juris
Author_Institution :
Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
Abstract :
The authors investigate the Kolmogorov complexity of real numbers. They determine the Hausdorff dimension and the topological dimension of the graph of K, the Kolmogorov complexity function. They conclude that the complexity graph is a fractal
Keywords :
computational complexity; fractals; topology; Hausdorff dimension; Kolmogorov complexity; complexity graph; fractal; real line; real numbers; topological dimension; Computational complexity; Computational geometry; Computer aided analysis; Computer science; Fractals; Mathematics; Polynomials; Robustness; Turing machines; Visualization;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41820
