Abstract:
This Focused Research Group is a collaborative effort by researchers at many sites who bring ideas from recursion theory, complexity theory, and other specialties to bear on questions about algorithmic randomness. Important background notions include the ideas of Kolmogorov complexity and Martin-Lof randomness, which have separately and jointly received large amounts of attention, and which come together in many of the examples and problems described in this proposal. Issues to be studied during the project include relationships between Martin-Lof random sets and Hausdorff dimension or other measures of dimension, methods for extracting randomness from a semi-random source of data, dimensions and other properties of complexity classes of strings, distinctive properties of sets with low Kolmogorov complexity, and relationships between algorithmic randomness and reverse mathematics, which seeks to understand the axiomatic strength required by particular theories.
The forms of randomness studied by this group of researchers are based on some appealing ideas regarding infinite strings, such as the record of an infinitely repeated series of coin tosses. Intuitively, the Kolmogorov complexity of a binary string like the record of heads and tails from coin tosses is the length of the shortest definitive description of the string. Digitization methods for voice and picture transmission take advantage of the regularity and repetition in typical voice signals or digitized images, using much less space or time to record the sound or image data than might seem necessary.
From the point of view of Kolmogorov complexity, a genuinely random binary string is probably its own shortest description, or nearly so.
Some of the problems studied by this research group seek to establish properties of subsets of strings that have the same complexity, such as their dimension. Activities of the group will include workshops, summer schools for graduate students, and travel for collaboration.