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 behaviour in some process from the expected behaviour.
There are several historical approaches to algorithmic randomness, such as computable martingales, Kolmogorov complexity
and Martin-Loff of randomness. Algorithmic randomness is also related to classical concepts, such as entropy
(in the senses of Shannon and Boltzmann).
The mathematics of this area is really quite deep. The kinds of questions 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 behaviour 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.
Reverse mathematics and logic
Scientific Programme Committee
Verónica Becher (Buenos Aires, Argentina)
Jack Lutz (Ames, USA)
Alexander G. Melnikov (Wellington, New Zealand)
Wolfgang Merkle, co-chair (Heidelberg, Germany)
Kenshi Miyabe (Kawasaki-city, Japan)
Mariya I. Soskova (Madison, USA)
Linda Brown Westrick, co-chair (State College, USA)