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)$

Improve this question
$\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$
    – Noah Schweber
    Commented 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$
    – Noah Schweber
    Commented Feb 7, 2014 at 17:35
  • $\begingroup$ @NoahS: thank you! I mean continuous computable mapping $\endgroup$
    – Alexey Milovanov
    Commented 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$
    – Noah Schweber
    Commented 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$
    – Noah Schweber
    Commented Feb 7, 2014 at 17:43

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$
    – Bjørn Kjos-Hanssen
    Commented 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$
    – Bjørn Kjos-Hanssen
    Commented Jun 25, 2014 at 5:48

You must log in to answer this question.

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