Dynamics, measure and dimension in the theory of computing
Satyadev Nandakumar · 2009
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, however, will resist 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 measurement of how non-random sequences or sets are. In subsequent chapters 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 chapters deal with finite-state dimension, which can be seen as density of information as measured by finite-state machines. This ties to a classical notion of normality of numbers. We prove that multiplication by a rational number does not alter the finite-state dimension of the base-$k$ expansion of a real number, generalizing and giving 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 chapter, we give constructions of normal and non-normal Liouville numbers, a well-known class of transcendental numbers.