Open Problems in Mathematical Logic — Problem 28 (Downey--Hirschfeldt--Miller--Nies [DHMN])

Definitions and mathematical statement

The source leaves the domain of $x$ and the properties of $U$ unspecified. Under the conventional interpretation of relativized prefix-free Kolmogorov complexity, let $2^{<\omega}$ be the set of finite binary strings, let $2^\omega$ be the set of infinite binary sequences, and regard $x\in 2^\omega$ as an oracle subset of ${\mathbb{N}}$. Fix an optimal universal oracle machine $U$ whose domain is prefix-free for each oracle. For $\sigma\in 2^{<\omega}$, define \[ K^x(\sigma)=\min\{\lvert\tau\rvert:\tau\in 2^{<\omega},\ U^x(\tau)=\sigma\}, \qquad \Omega^x=\sum_{\sigma\in 2^{<\omega}}2^{-K^x(\sigma)}. \] Here $\lvert\tau\rvert$ denotes the length of the program $\tau$. The prefix-free convention makes this a convergent real-valued sum. The displayed definition sums one term for each output string, using its shortest program length; it is to be retained exactly as supplied.

For sets $A,B\subseteq{\mathbb{N}}$, write $A\leq_T B$ when membership in $A$ is computable using oracle $B$. When a real serves as an oracle, use its binary expansion, choosing the terminating expansion at dyadic reals. Let $0''$ denote the second Turing jump of the empty set.

With these conventions, the question attributed in the supplied record to Downey--Hirschfeldt--Miller--Nies [DHMN] is: \[ \exists x\in 2^\omega\quad 0''\leq_T\Omega^x\,? \] The oracle domain and machine conventions above require confirmation against the underlying source. The supplied record does not specify whether the intended assertion concerns a particular fixed machine or every optimal universal prefix-free oracle machine; no machine-independence assertion is made here.

Short English statement

Under the stated conventional interpretation, does some binary-sequence oracle $x$ make the real $\Omega^x$, defined by summing $2^{-K^x(\sigma)}$ over all finite binary strings, compute the second Turing jump $0''$? The source labels this problem open, but that status and the unresolved machine conventions require review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $801016$, source code catalogue entry, in the AMR Open Problem Lists collection. The supplied status is open; this is a registry label, not an independently verified literature assessment.
• Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 28. 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 details, not a claim of independent source access.
• Attribution/context supplied in the title and background: Downey--Hirschfeldt--Miller--Nies [DHMN]. No full bibliographic entry for [DHMN] is included in the supplied record. The registry's proposer field lists Barmpalias, Gao et al.