About
Computability, Complexity and Randomness is a series of
conferences devoted generally to the mathematics of
computation and complexity, but tends to primarily focus on
algorithmic randomness/algorithmic information theory and
its impact on mathematics. Algorithmic randomness is the
part of mathematics devoted to ascribing meaning to the
randomness of individual strings and infinite sequences. For
example, we give mathematical meaning to the intuition that
one would more readily believe that the string
01101101001101011 was produced via the flips of a fair coin
than one would of the string 00000000000000000. The core
idea is that a sequence is algorithmically random if it
passes all computational randomness tests, and hence if a
computational observer cannot distinguish its behavior in
some process from the expected behavior.
There are several historical approaches to algorithmic
randomness, such as computable martingales, Kolmogorov
complexity, and Martin-Löf of randomness. Algorithmic
randomness is also related to classical concepts, such as
entropy (in the senses of Shannon and Boltzmann). The
questions that algorithmic randomness addresses include: How
do we calibrate levels of randomness? Can we amplify weak
random sources? Is randomness a provable computational
resource? What kinds of power do random sources give us? And
so on. Tools from this area can be used in many areas of
mathematics and computer science, including the expected
behavior of algorithms, computational biology, ergodic
theory, geometric measure theory, number theory and
normality. The theme of the conference is algorithmic
randomness and related topics in computability, complexity
and logic, such as Kolmogorov complexity, computational
complexity and reverse mathematics.