Ph.D. Dissertation Defense - Satyadev Nandakumar

Date: 03 Nov, 2009
Time: 10:00 AM
Location: 223 Atanasoff Hall
Topic: Dynamics, Measure and Dimension in the Theory of Computing
Major Professor(s): Jack Lutz


Abstract:

This thesis establishes some results in algorithmic information theory. Martin-Lof in 1966 formalized the notion of what it means for a given sequence to be random, using the theory of computation. Equivalent, alternate definitions justify that this definition is robust. A finite string is called random if there is no short program which outputs the string - that is, the Kolmogorov complexity of the string is within an additive constant of the length of the string itself. With the introduction of a suitable notion termed self-delimiting Kolmogorov complexity, an infinite sequence is called random if almost all its finite prefixes are incompressible in the above sense. Algorithmic information theory studies the properties of such random sequences.

It is natural to enquire whether a sequence random according to this definition satisfies the well-known probabilistic laws. Early results by van Lambalgen and Vovk established that all random sequences obey Borel-Cantelli Lemmas, the Strong Law of Large Numbers and the Law of the Iterated Logarithm. van Lambalgen conjectured that Birkhoff's ergodic theorem resists such effectivization. Nevertheless, V'yugin in a tour-de-force established an effective version of the Ergodic Theorem. V'yugin's version has a technical limitation, however, that restricts its applicability. Random variables are assumed to be computable, and hence continuous. In the first part of the thesis, we extend V'yugin's theorem to handle a restricted class of discontinuous functions, and prove that we can apply it to effectivize some results on continued fractions.

The concept of dimension gives a quantitative refinement of how non-random sequences or sets are. In the subsequent parts, we deal with the concept of dimension in various resource-bounded settings. We give an alternate characterization of constructive Hausdorff and constructive packing dimension using generalizations of tools used in establishing the effective ergodic theorem.

The final two parts deal with finite-state dimension, which can be seen as density of information as measured by finite-state machines. This has ties to the classical notion of normality of numbers. We prove that multiplication with a non-zero rational number does not alter the finite-state dimension of the base-k expansion of a real number. This generalizes and gives a new proof of Wall's classical theorem that multiplication by a non-zero rational does not alter the normality of a number.

In the last part of the talk, we give constructions of normal and non-normal Liouville numbers, a well-known class of transcendental numbers.