2000px-Venn0110.svg

Preservation of randomness under symmetric differences

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.