9 problems

Let $B^{\sharp}$ be the domain of finite binary strings under consideration, and let $P^G(x)$ and $K^G(x)$ denote the corresponding generalized probability and complexity functions…

Let $B^{\sharp}$ be the domain of finite binary strings under consideration, and let $P^E(x)$ and $K^E(x)$ denote the corresponding enumerable measure and complexity functions. Wri…

Let $B^{\sharp}$ be the domain of finite binary strings under consideration, and let $P^M(x)$ and $K^M(x)$ denote the corresponding measure and complexity functions. Write…

Let $K$ be prefix Kolmogorov complexity, let $\boldsymbol{\vartheta}_0$ be the true parameter, and let $\Delta(k)$ denote the complexity difference used in the MDL setup. Strengthe…

Let $\theta_0$ be the true Bernoulli parameter, let $\theta^x$ denote the MDL prediction based on the observed sequence, let $K(\theta_0)$ be the prefix Kolmogorov complexity of…

A number is compressed by a non-constructive unique effective description when the validity of the description can be checked effectively given the number, but the number cannot be…

Let $X$ and $Y$ be infinite binary sequences, and let an oracle computation of $X$ by $Y$ have an oracle-use function measuring how many bits of $Y$ are queried to compute the firs…

Entropy-complexity conjecture. For $H=\overline{H}$ or $H=\underline{H}$, one has

Universal semi-density matrix conjecture. There is a lower-semicomputable semi-density matrix $\mu$ dominating every other such matrix: for every lower-semicomputable semi-density…