Let K be a fixed prefix-free Kolmogorov complexity and define, for reals x,y∈R, x≤_K y if and only if there exists a constant c∈N such that for every n∈N, K(x upharpoonright n)≤ K(y upharpoonright n)+c. Does there exist a real x whose K-degree is maximal; equivalently, does there exist x∈R such that for every y∈R, y≤_K x?

Existence of a maximal K-degree

Let $K$ be a fixed prefix-free Kolmogorov complexity and define, for reals $x,y\in\mathbb{R}$ , $x\leq_K y$ if and only if there exists a constant $c\in\mathbb{N}$ such that for every $n\in\mathbb{N}$ , $K(x\upharpoonright n)\leq K(y\upharpoonright n)+c$ . Does there exist a real $x$ whose $K$ -degree is maximal; equivalently, does there exist $x\in\mathbb{R}$ such that for every $y\in\mathbb{R}$ , $y\leq_K x$ ?

References

Primary source

arXiv

Additional references

There is no maximal K-degree — arXiv — Lu Liu

algorithmic-randomness computability-theory kolmogorov-complexity

Posted 3 weeks ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Claimed solved

A September 2026 preprint claims that no real has the greatest possible descriptive-complexity degree, but the result is unrefereed and unconfirmed.

The problem asks whether a maximal degree exists under the $K$ -degree ordering. No proposer or earlier date is identified in the retrieved material.

September 2026 preprint

Lu Liu’s new preprint claims to prove that no real is maximal under the $K$ -degree ordering, which would settle the question negatively. The claim is unrefereed and has not been independently confirmed.

Current status (as of September 2026): A preprint claims that no maximal $K$ -degree exists, but this conclusion remains unverified.

Sources

No solutions have been posted yet.