×

On the computability of fractal dimensions and Hausdorff measure. (English) Zbl 0926.03049

Summary: It is shown that there exist subsets \(A\) and \(B\) of the real line which are recursively constructible such that \(A\) has a nonrecursive Hausdorff dimension and \(B\) has a recursive Hausdorff dimension (between 0 and 1) but has a finite, nonrecursive Hausdorff measure. It is also shown that there exists a polynomial-time computable curve on the two-dimensional plane that has a nonrecursive Hausdorff dimension between 1 and 2. Computability of Julia sets of computable functions on the real line is investigated. It is shown that there exists a polynomial-time computable function \(f\) on the real line whose Julia set is not recursively approximable.

MSC:

03D80 Applications of computability and recursion theory
28A80 Fractals
03D15 Complexity of computation (including implicit computational complexity)
03F60 Constructive and recursive analysis
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberth, O., Computable Analysis (1980), McGraw-Hill: McGraw-Hill New York · Zbl 0461.03015
[2] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers; NP completeness, recursive functions and universal machines, Bull. Amer. Math. Soc., 21, 1-46 (1989) · Zbl 0681.03020
[3] Cai, J.-Y.; Hartmanis, J., On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, J. Comput. System Sci., 49, 605-619 (1994) · Zbl 0824.68054
[4] Cenzer, D., Effective real dynamics, (Crossley, J. N.; Remmel, J. B.; Shore, R. A.; Sweedler, M. E., Logical Methods (1993), Birkhäuser: Birkhäuser Boston), 162-177 · Zbl 0823.03034
[5] Chou, A.; Ko, K., Computational complexity of two-dimensional regions, SIAM J. Comput., 24, 923-947 (1995) · Zbl 0836.68037
[6] Falconer, K., Fractal Geometry, Mathematical Foundations and Applications (1991), Wiley: Wiley New York
[7] Goodstein, R., Recursive Analysis (1961), North-Holland: North-Holland Amsterdam · Zbl 0217.30202
[8] Ko, K., Complexity Theory of Real Functions (1991), Birkhäuser: Birkhäuser Boston
[9] Ko, K., A polynomial-time computable curve whose interior has a nonrecursive measure, Theoret. Comput. Sci., 145, 241-270 (1995) · Zbl 0874.68287
[10] Ko, K.; Weihrauch, K., On the measure of two-dimensional regions with polynomial-time computable boundaries, (Proc. 11th IEEE Conf. on Computational Complexity (1996)), 150-159
[11] Lacombe, D., Les ensembles récursivement ouverts on fermès et leurs applications à l’analyse récursive, Comptes Rendus, 244, 838-840 (1957)
[12] Mandelbrot, B., The Fractal Geometry of Nature (1983), W.H. Freeman: W.H. Freeman New York
[13] Merzenich, W.; Staiger, L., Fractals, dimension, and formal languages, RAIRO Inform. Théor., 28, 361-386 (1994) · Zbl 0883.68078
[14] Pour-El, M.; Richards, I., Computability in Analysis and Physics (1989), Springer: Springer Berlin · Zbl 0678.03027
[15] Šanin, N., Constructive Real Numbers and Function Spaces, (Translations of Mathematical Monographs, vol. 21 (1968), American Mathematical Society: American Mathematical Society Providence, RI), (transl. by E. Mendelson)
[16] Weihrauch, K., Computability (1987), Springer: Springer Berlin · Zbl 0611.03002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.