Title: The interplay between randomness and genericity
by Laurent Bienvenu (Université de Bordeaux) as part of Computability theory and applications
In computability theory, one often think of (Cohen)-genericity and algorithmic randomness as orthogonal notions: a truly random real will look very non-generic, and a truly generic real will look very non-random. This orthogonality is best incarnated by the result of Nies, Stephan and Terwijn that any 2-random real and 2-generic real form a minimal pair for Turing reducibility. On the other hand, we know from the Kucera-Gacs theorem that for any n there is a 1-random real which computes an n-generic one, but also (and more surprisingly), by a result of Kautz that every 2-random real computes a 1-generic real. These last two results tell us that the interplay between randomness and genericity is rather complex when “randomness” is between 1-random and 2-random or “genericity” between 1-generic and 2-generic. It is this gray area that we will discuss in this talk (based on the paper of the same title, joint work with Chris Porter).