Compression of enumerations and gain
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. Strong compression and weak gainless compression is shown for any computably enumerable set, and a positional game is studied toward understanding strong gainless compression.
Content Overview
Let $C(\cdot|\cdot)$ denote the conditional Komogorov complexity.
Let $A\subset\omega$. The first $n$ bits of $A$, denoted by $A\upharpoonright_n$, is the $n$-bit binary string $\chi_A(0)\chi_A(1)\cdots\chi_A(n-1)$.
Let $A,B\subset\omega$. $A$ is rK-reducible to $B$, written $A\leq_{rK} B$, if $C(A\upharpoonright_n|B\upharpoonright_n)\leq O(1)$. Equivalently, if there is a constant $k$ and a partial computable function $f$, such that $f(B\upharpoonright_n)$ outputs an index $e$ such that $A\upharpoonright_n\in W_e$ and $|W_e|\leq k$, where $W_e$ is the $e^\text{th}$ r.e. set.
Given r.e. set $A$, we call a r.e. set $D$ a compression of $A$ if $A\leq_{rK} D$.
- The compression is gainless if $D\leq_{rK} A$.
- The compression is strong if $D\subset 2\mathbb{N}$.
- The compression is weak if $|D\cap[0,2n)|\leq|A\cap[0,2n)|/2$.
A set $A$ is well-compressible if it has a gainless strong compression.
Theorem. Each rK-complete set (that is, an r.e. set $K$ such that $A\leq_{rK}K$ for any r.e. set $A$) has a strong gainless compression.
Theorem. Each r.e. set has a strong compression.
Theorem. Each r.e. set has a weak gainless compression.
Theorem. Let $r$ represents any of $rK$ reduction, $K$ reduction or $C$ reduction. If r.e. sets $A,B$ both have strong gainless compression and $B<_r A$, then there is an r.e. set $C$ such that $B<_r C<_r A$.
Open problem
Does each r.e. set have a strong gainless compression?
Links and resources
Relevant contents
- talk - Compression of enumerations and gain
- open problem - Even Number Game
- open problem - $n$-r.e. plus left-r.e.
