Open Problems in Mathematical Logic — Problem 24

Definitions and mathematical statement

Interpretive qualifications. The supplied record does not explicitly specify the domain of the sequences or define the complexity and reducibility notation. For a conditional standard interpretation, take $x,z\in 2^{{\mathbb{N}}}$, the set of infinite binary sequences, and let $x\upharpoonright n$ denote the initial segment of $x$ of length $n$. Let $K(\sigma)$ denote prefix-free Kolmogorov complexity of a finite binary string $\sigma$, relative to a fixed optimal prefix-free machine, and let $K(n)$ denote the complexity of a fixed effective encoding of the natural number $n$. The usual initial-segment complexity ordering is \[ z\leq_K x \quad\Longleftrightarrow\quad (\exists c\in{\mathbb{N}})(\forall n\geq 1)\; K(z\upharpoonright n)\leq K(x\upharpoonright n)+c, \] with $z\geq_K x$ meaning $x\leq_K z$. These are explanatory conventions, whose agreement with the intended source definitions requires review.

The source uses the distinct notation $\leq_K^+$ in its lower cone. Its superscript $+$ is not explained in the supplied record; no identification with $\leq_K$ is asserted here. Retaining that unresolved notation, set \[ L_x=\{z\in 2^{{\mathbb{N}}}:z\leq_K^+x\}, \qquad U_x=\{z\in 2^{{\mathbb{N}}}:z\geq_Kx\}. \] Here countable includes finite sets.

Questions, subject to the preceding interpretive qualifications. Are both of the following assertions true for every $x\in 2^{{\mathbb{N}}}$?

1. \[ L_x\text{ is countable} \quad\Longleftrightarrow\quad \liminf_{n\to\infty}\left(K(x\upharpoonright n)-K(n)\right)<\infty. \]
2. \[ U_x\text{ is countable} \quad\Longleftrightarrow\quad \liminf_{n\to\infty}\left(K(n)+n-K(x\upharpoonright n)\right)<\infty. \]

Each right-hand condition asks for a uniform finite upper bound along infinitely many lengths. The intended domain and, especially, the meaning of $\leq_K^+$ must be confirmed before this can be treated as a fully specified formulation of the source problem.

Short English statement

The problem asks whether countability of the lower and upper complexity cones of an infinite sequence is characterized by the two displayed bounds holding infinitely often. The binary-sequence and prefix-free-complexity conventions are conditional, and the source's notation $\leq_K^+$ remains undefined. The registry labels the problem open; that label is supplied metadata, not an independently verified assessment.

Sources

• Local UnsolvedMath registry: supplied complete source record, permanent ID $801012$, exact source problem code catalogue entry; title: Open Problems in Mathematical Logic --- Problem 24. The record attributes the problem to Barmpalias, Gao et al., with proposed year $2026$, and supplies the status open.
• Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 24. Supplied source URL: https://arxiv.org/abs/2608.26628. The record reports access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance claims; the source was not independently accessed or verified for this draft.