Compression of enumerations and gain

Abstract

I will talk about how information in a recursive enumeration can be compressed, in the sense of relative Kolmogorov complexity (rK). We introduce a strong and a weak form of compression, and we also care about the gain of compressions. It turns out that the existence of strong gainless compression is a key to provide a join operator on r.e. rK degrees, making the degree structure dense. I’ll show that strong compression and weak gainless compression exist for any recursive enumeration. I’ll also talk about a positional game that is crucial toward obtaining a strong gainless compression.

Links and resources

• talk video
• slide pdf

Relevant contents

• article - Compression of enumerations and gain
• open problem - Even Number Game
• open problem - $n$-r.e. plus left-r.e.