Problems in Algorithmic Information
This list of questions will be regularly updated.
- Is every c.e. set equivalent to a c.e. set of even numbers, with respect to initial segment Kolmogorov complexity?
This can be formalized with respect to plain, prefix-free or conditional Kolmogorov complexity.
Given a c.e. set $A$ is there a c.e. set $B$ of even numbers such that
- $K(A\upharpoonright_n) = K(B\upharpoonright_n)$ where $K$ is the prefix-free Kolmogorov complexity
- $C(A\upharpoonright_n) = C(B\upharpoonright_n)$ where $C$ is the plain Kolmogorov complexity
- $C(A\upharpoonright_n \mid B\upharpoonright_n)= C(B\upharpoonright_n \mid A\upharpoonright_n) = O(1)$
where equalities hold for all $n$ up to a constant.