The interplay between randomness and genericity

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

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.