Open Problems in Mathematical Logic — Problem 41

Definitions and mathematical statement

For a set $X\subseteq{\mathbb{N}}$, write $X\leq_T Y$ for Turing reducibility and $X'$ for the Turing jump. The set $X$ is $\Delta^0_2$ if $X\leq_T\varnothing'$, and is low if $X'\equiv_T\varnothing'$. It is $1$-generic if, for every computably enumerable set $W\subseteq 2^{<{\mathbb{N}}}$ of finite binary strings, either some initial segment of $X$ belongs to $W$, or some initial segment of $X$ has no extension belonging to $W$.

The supplied source attributes to [LMNS, Section 3.1] the implication chain \[ \text{$1$-generic $\Delta^0_2$} \Longrightarrow \text{index guessable} \Longrightarrow \text{computes no maximal tower} \Longrightarrow \text{low}. \] It asks whether the first and second implications are reversible.

To display the requested converses without supplying missing hypotheses, let $\mathcal U$ denote the source's intended, unspecified domain, and let $G(x)$, $I(x)$, and $T(x)$ stand respectively for its predicates "$1$-generic $\Delta^0_2$", "index guessable", and "computes no maximal tower". The two questions are whether \[ (\forall x\in\mathcal U)\,[I(x)\Longrightarrow G(x)] \qquad\text{and}\qquad (\forall x\in\mathcal U)\,[T(x)\Longrightarrow I(x)] \] hold, separately.

Unresolved formulation qualifications. The supplied record does not define index guessability or maximal towers, specify the objects and order underlying the towers, or explain how an oracle computes a tower. It also does not specify $\mathcal U$, including whether its assertions concern individual sets or Turing degrees. For individual sets, the first predicate has the definition given above. A degree formulation could instead ask whether a degree contains a $1$-generic $\Delta^0_2$ representative; that is a different formulation and is not selected here. Thus the displayed converse questions are a faithful logical schema, pending the missing definitions and domain from [LMNS, Section 3.1], rather than a fully specified mathematical conjecture.

Short English statement

The source asks whether index guessability implies the preceding $1$-generic $\Delta^0_2$ condition, and whether computing no maximal tower implies index guessability. The intended domain and the specialized definitions are absent, so both converse questions require clarification from the cited source.

Sources

• Local UnsolvedMath registry, permanent ID $801029$, exact source problem code catalogue entry, title Open Problems in Mathematical Logic --- Problem 41. The supplied registry labels the problem open; this label is not an independently verified mathematical or literature assessment.
• Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 41, https://arxiv.org/abs/2608.26628. The registry attributes the problem to Barmpalias, Gao et al. and gives proposed year 2026. Its provenance records access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not a claim of independent access or verification.
• [LMNS, Section 3.1], cited in the supplied statement as establishing the displayed implications. The record supplies no full bibliographic identification or link for [LMNS], so its definitions, hypotheses, and results cannot be checked from the supplied material alone.