Randomness and Computability

University Of Connecticut, Storrs CT

Investigators

Abstract

The two most fundamental notions in effective randomness are Kolmogorov complexity and Martin-Lof randomness. The first measures the information content of finite binary strings, while the second captures the intuition that a random infinite binary sequence has no "distinguishing features". Both notions are rooted in computability theory, so it is not surprising that the study of randomness draws methods and ideas from computability theory, as well as core mathematical subjects like measure theory and information theory. However, the theory of effective randomness has proved to be a rich field of study in its own right. Miller proposes to study the strength of non-monotonic betting strategies, the computable power of sequences with positive effective Hausdorff dimension, degrees of randomness, and K-triviality. A sequence of zeros and ones is considered random if the shortest (binary) computer program that generates the sequence has essentially the same length as the sequence itself. Intuitively, a random sequence has no patterns that can be exploited to give a compressed description. For example, the sequence consisting of a million zeros can be generated easily by a short program, so it is not random. On the other hand, there is a high probability that a sequence generated by flipping a coin a million times (tails is zero, heads is one) will be random. The length of the shortest program for a sequence is called the Kolmogorov complexity of the sequence; this notion was introduced in the 1960s. An infinite sequence is considered random if all of its finite initial segments are sufficiently random. This is equivalent to saying that no (semi-)computable betting strategy can win money trying to predict the digits of the sequence. The proposed research will address fundamental questions about randomness, including: (1) How powerful are computable betting strategies that are allowed to bet on the digits of a sequence in any order; (2) Is it possible to distill information out of a semi-random source to produce a random sequence or, at least, a sequence that has higher information density; (3) What does it mean to say that one infinite sequence is more random that another (4) How computationally weak are the infinite?