1
$\begingroup$

If $X \leq_T Y + 0'$ does there always exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$?

Obviously, we can find $Z \leq Y$ where the $y$-th column of $Z$ has a limit equal to $X(y)$. Just let $\langle y, s\rangle$ be given by the computation of $X$ from $0'_s + Y$. However, I realized I wasn't sure if it was possible for it to be the case that any such approximation includes information that $X$ can't compute. Probably, I'm overlooking something obvious.

If not, is there a natural class of $X$ for which this property is guaranteed?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Ohh, I think I'm being dumb. The answer is no.

Given $X \not\leq_T 0'$ we build $Y$ using the finite extension method and modify the usual minimal pair construction by coding in the bits of $X$ into $Y$ between the minimal pair requirements.

Now, since $0'$ can figure out how the minimal pair requirements are met it can decode the bits of $X$ in $Y$. Thus $0' +Y$ computes $X$ but any $Z$ must be computable and as $X \not\leq_T 0'$ the claim fails.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Don't forget to accept your answer if it answers your question. $\endgroup$
    – LSpice
    Commented May 25, 2022 at 3:34
  • 1
    $\begingroup$ I will as soon as it lets me (the site requires I wait 2 days) but thanks! $\endgroup$
    – Peter Gerdes
    Commented May 25, 2022 at 4:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .