Laurent Bienvenu (Université de Bordeaux)

November 10, 2020 @ 4:00 am – 5:00 am

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).