Speaker: Rutger Kuyper
Joint work with Joseph S. Miller
Title: Preservation of randomness and genericity under symmetric differences
Abstract:
Given a class $\mathcal U$ of subsets of the natural numbers, let us say that a subset $A$ of the natural numbers is $\mathcal U$-stabilising if the symmetric difference (or bitwise addition) $A+X$ of $A$ and $X$ is an element of $\mathcal U$ for every element $X$ of $\mathcal U$.
Several people have asked, using varying terminology, to characterise the Martin-Löf-stabilising sets, i.e. the sets $A$ such that $X+A$ is Martin-Löf random for every Martin-Löf random set $X$. We show that the Martin-Löf-stabilising sets are exactly the $K$-trivial sets.
We also show that the 1-generic-stabilising sets are exactly the computable sets, using an argument which (surprisingly) makes use of Kolmogorov complexity and facts about the $K$-trivial sets.