Degree Type

Dissertation

Date of Award

2017

Degree Name

Doctor of Philosophy

Department

Computer Science

Major

Computer Science

First Advisor

Jack H. Lutz

Abstract

In this thesis we study the interaction between algorithmic randomness and mathematical analysis. In particular, we focus on the connection between analysis and the fields of effective dimension and resource bounded randomness.

We begin with the effective dimension of Euclidean points. We show that the techniques from algorithmic information can be used successfully to study problems in fractal geometry. Specifically, we investigate the Hausdorff of projections of Euclidean subsets. Using Kolmogorov complexity, we give a new proof of the celebrated Marstrand projection theorem. We also prove, using similar methods, two new lower bounds on projections. The first shows that Marstrand's theorem holds for more general subsets of R^n. The second gives a lower bound on the packing dimension of projections for arbitrary sets.

Our next work is on the algorithmic dimension spectra of lines in the Euclidean plane. Given any line L with slope a and vertical intercept b, the dimension spectrum spec(L) is the set of all effective Hausdorff dimensions of individual points on L. We use Kolmogorov complexity and geometrical arguments to show that, if the effective Hausdorff dimension dim(a, b) is equal to the effective packing dimension Dim(a, b), then spec(L) contains a unit interval. We also show that, if the dimension dim(a, b) is at least one, then spec(L) is infinite. Together with previous work, this implies that the dimension spectrum of any line is infinite.

Our last topic is on the connection between polynomial space randomness and a fundamental result of analysis, the Lebesgue differentiation theorem. We generalize Ko's framework for polynomial space computability in R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation theorem holds for a point x for every pspace L_1-computable function.

DOI

https://doi.org/10.31274/etd-180810-5851

Copyright Owner

Donald M. Stull

Language

en

File Format

application/pdf

File Size

113 pages

Share

COinS