Degree Type

Dissertation

Date of Award

2009

Degree Name

Doctor of Philosophy

Department

Computer Science

First Advisor

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, 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.

Copyright Owner

Satyadev Nandakumar

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

94 pages

Share

COinS