Existence: non-recursive sequence without a recursive subsequence

Question

As the title suggests, the question is whether or not there exists a non-recursive sequence of natural numbers which has no recursive subsequence?

Answer 1

Any sufficiently fast-growing function (such as the Busy Beaver function) provides an example. However, there's also a cute general trick we can use here:

Given an arbitrary sequence of natural numbers $\alpha=(a_i)_{i\in\mathbb{N}}$, consider the new sequence $$\hat{\alpha}=(\prod_{k<i}p_k^{a_k+1})_{i\in\mathbb{N}},$$ where $p_k$ is the $k$th prime. Each term in the sequence $\hat{\alpha}$ codes an entire initial segment of $\alpha$; if I know infinitely many terms of $\hat{\alpha}$ I can reconstruct the entire sequence $\alpha$. This means that if $\alpha$ is any noncomputable sequence, then $\hat{\alpha}$ is a noncomputable sequence with no computable subsequence. Moreover, $\alpha$ and $\hat{\alpha}$ are "essentially equally complicated" (precisely: $\alpha\equiv_T\hat{\alpha}$), so this shows that sequences without computable subsequences are quite common.