ON THE COMPUTABILITY OF FRACTAL DIMENSIONS AND HAUSDORFF MEASURE

It is shown that there exist subsets A and B of the real line which ar e recursively constructible such that A has a nonrecursive Hausdorff d imension and B has a recursive Hausdorff dimension (between 0 and 1) b ut has a finite, nonrecursive Hausdorff measure. It is also shown that there exists a polynomial-time computable curve on the two-dimensiona l plane that has a nonrecursive Hausdorff dimension between 1 and 2. C omputability of Julia sets of computable functions on the real line is investigated. It is shown that there exists a polynomial-time computa ble functions on the real line whose Julia set is not recurisvely appr oximable. (C) 1998 Elsevier Science B.V. All rights reserved.