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



Self-similarity in the theory of computability
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$.


