Rutger Kuyper

When:
January 7, 2016 @ 10:30 am – 11:00 am
2016-01-07T10:30:00-10:00
2016-01-07T11:00:00-10:00
Where:
Physical Science Bldg
Honolulu, HI 96822
USA
Rutger Kuyper

Title: Preservation of randomness and genericity under symmetric differences

Abstract:

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.

Joint work with Joseph S. Miller