# Can every subsequence of a non-computable sequence be itself non-computable?

So I was playing around with a small conjecture (not in computability theory), trying to find a counterexample, and I realized that if a function $$f$$ with very specific properties exists, then I could easily find many said counterexamples. Jury is still out on whether, if there are no such function $$f$$, I can prove the conjecture.

So, formally, is there a function with the following properties:

• $$f$$ is a function from $$\mathbb{N}$$ to $$\mathbb{N}$$ (if you have one example $$f:\mathbb{N}\rightarrow X$$ for $$X\neq \mathbb{N}$$ that would still be a nice answer for the question, but I prefer $$f:\mathbb{N}\rightarrow\mathbb{N}$$)
• $$f$$ is increasing (this is optional as well);
• and, for every increasing function $$i:\mathbb{N}\rightarrow\mathbb{N}$$, $$f\circ i$$ is non computable (and so, by taking $$i$$ to be the identity, $$f$$ is non computable as well)?

This question and this one are similar, but they ask specifically about functions $$f:\mathbb{N}\rightarrow\{0,1\}$$, when the answer is obviously negative: one can always find, by the pigeon-hole principle, a function $$i:\mathbb{N}\rightarrow\mathbb{N}$$ (possibly non computable) such that $$f\circ i$$ is not only computable, but even constant.

I tried using a counting argument to show that there are no such functions, writing them as countable "unions" of computable functions, of which there is only a countable set, but I ran into the problem that the $$i$$ need not be computable. As I do not know a lot about computability theory, I could not progress any further in trying to find such an $$f$$, or disprove that one exists.

The $$n$$th Busy Beaver is a $$n$$-state Turing machine on the alphabet $$\{0,1\}$$ that produces the maximum number $$\Sigma(n)$$ of $$1$$s after starting with a tape of only $$0$$s, compared to all other $$n$$-state Turing machines on the same alphabet (see Wikipedia).
• $$\Sigma$$ is clearly a function from $$\mathbb{N}$$ to $$\mathbb{N}$$.
• It is increasing, since a $$n$$-state Turing machine is a particular case of a $$n+1$$-state Turing machine.
• Radó proved in 1962 that, for every computable function $$f:\mathbb{N}\rightarrow\mathbb{N}$$ there exists a $$N\in\mathbb{N}$$ such that, for all $$n\geq N$$, $$\Sigma(n)>f(n)$$: so, for each increasing $$i:\mathbb{N}\rightarrow\mathbb{N}$$, $$\Sigma\circ i$$ grows at least as fast as $$\Sigma$$, and is therefore non computable.
So $$\Sigma$$ is one example of the functions I am looking for (sorry for self-answering).