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

Question

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.

Answer 1

While writing down this question I realized that the Busy Beaver function is one example of what I was looking for, and I don't know how that did not occur to me before: but, because I spent so much time writing the question, I decided to invest a little more time and also write the answer.

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