rK degree

Definitions Let $A\subset\omega$. $A$ is $n$-r.e. if there is a computable function $f(a,s)$ such that for all $a\in\omega$, $f(a,0)=0$, $|\{s:f(a,s)\neq f(a,s+1)\}|\leq n$, $\lim_{s\to\infty}f(a,s)=\chi_A(a)$. Note that $1$-r.e. sets are just r.e. sets; $2$-r.

The game Given parameters $(l,c,q)$. For convenience you can assume that $l$ is very large, $c=4$ and $q=1/2$. Consider the following game between a coder and a destroyer. The coder has spaces $f(\tau)$ indexed by $\tau\in 2^{\leq l}$ (all binary strings of length $\leq l$ which are called codes).

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.

Abstract We study the compressibility of enumerations, and its role in the relative Kolmogorov complexity of computably enumerable sets, with respect to density. With repspect to a strong and a weak form of compression, we examine the gain: the amount of auxiliary information embedded in the compressed enumeration.

The game Given $k$, consider the following game of $2$ players. In each round, player 1 chooses a set $R$ of $k$ natural numbers that he has not yet chosen earlier player 2 chooses an even number $n\in[\min R,\max R]$, that he has not yet chosen earlier If player 2 is unable to make a move at some round, he loses the game; otherwise he wins.