Skip to main content
MathOverflow

Return to Question

Question marks; `<>` -> `\langle\rangle`
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

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

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 $<y, s>$$\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?

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

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 $<y, s>$ 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?

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

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?

Source Link
Peter Gerdes
Peter Gerdes
  • 3k
  • 16
  • 18

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

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 $<y, s>$ 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?