4
$\begingroup$

Let $M = w_0w_1... \in \{0,1\}^*$. For any computable function $f$ define $M_f = w_{f(0)}w_{f(1)}...$

Let for any computable strictly increasing function $f$ there is continuous computable mapping between $M_f$ and $M$ (we can reestablish $M$ by its any computable subsequence)

Is it possible that $M$ is non-computable?

upd: I mean that $g$ is continuos if for any $x$ and $y$ that $x$ is begin of $y$ $g(x)$ is begin of $g(y)$

$\endgroup$
10
  • $\begingroup$ I'm not quite sure what your second paragraph means: do you mean that for all computable total $f$, we have $M\le_T M_f$? Or that there is a single functional $\Phi_e$ such that, for all total $f$, we have $\Phi_e^{M_f}=M$? Or, going off of your paranthetical, are you asking if $M$ can be computed from any of its computable subsequences (in which case you probably want $f$ to also be increasing)? $\endgroup$ Feb 7, 2014 at 17:34
  • $\begingroup$ Actually, you definitely need some restriction on $f$: otherwise taking $f$ to be constant means $M$ has to be computable. Anyways, interesting question! $\endgroup$ Feb 7, 2014 at 17:35
  • $\begingroup$ @NoahS: thank you! I mean continuous computable mapping $\endgroup$ Feb 7, 2014 at 17:37
  • $\begingroup$ What does "continuous computable mapping" mean? (To me, that sounds like a single $\Phi_e$ which is total on all oracles, but I'm not sure; in particular, if that's what it means, then (a) the quantifiers have the wrong order - you don't mean "for any $f$, there is a cont. comp. map" - and (b) again $M$ has to be computable, because at the "point" $f="n\mapsto 0"$ we must have $\Phi_e^f=M$. $\endgroup$ Feb 7, 2014 at 17:41
  • $\begingroup$ OK, your most recent edit took care of the constant function problem, but I'm still not sure I understand what you mean by cont. comp. map (partly because of quantifier order). $\endgroup$ Feb 7, 2014 at 17:43

1 Answer 1

3
$\begingroup$

Yes, there is such a non-computable set $M$.

Let $M=(M(0),M(1),\ldots)$ be a bi-immune set (i.e., having no infinite computable subset, and whose complement has no infinite computable subset) of minimal Turing degree. (Any nonhyperimmunefree degree contains a biimmune set, so we can use Sacks' minimal degree below $0'$.) Consider any computably selected sequence $$ N = (M(f(0)),M(f(1)),\ldots) $$ Suppose $N$ is computable. Since the range of $f$ is infinite, consider a computable increasing subsequence $f(i_1)<f(i_2)<\ldots$, with $i_1<i_2<\ldots$. Then $\{f(i_j): M(f(i_j))=1\}$ would be an infinite computable subset of $M$ (it's infinite by co-immunity of $M$).

Thus $N$ is noncomputable. Moreover $N\le_T M$. Since $M$ is of minimal degree, it follows that $M\equiv_T N$, i.e., $M$ can be recovered from $N$.

$\endgroup$
2
  • $\begingroup$ I learned from Sasha Shen that perhaps the question really is whether given any $A$ there is $B\ge_T A$ such that any computably selected subsequence of $B$ or $\overline B$ computes $A$. $\endgroup$ Jun 25, 2014 at 5:24
  • $\begingroup$ Ishmukhametov showed any c.e. traceable set has a strong minimal cover. I think the proof uses a kind of forcing that gives degrees that contain bi-immune sets. So there should at least be a continuum of such $A$'s. $\endgroup$ Jun 25, 2014 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.