Is predicting (in the limit) computable sequences as hard as the halting problem?
Actually this is easier than solving the halting problem. 

Let $f:\mathbb N\rightarrow\mathbb N$ be a function that dominates all computable functions, i.e., for all total computable functions $g:\mathbb N\rightarrow\mathbb N$, we have that for all but finitely many $n$, $g(n)\le f(n)$. It is a standard fact that there exist such functions that have strictly lower Turing degree than the halting problem, see e.g. Soare's book Recursively Enumerable Sets and Degrees. These are called the high Turing degrees.

Let $\varphi_e$, $e\in\mathbb N$ be a standard list of the partial computable functions from $\mathbb N$ to $\{0,1\}$.

Now, using $f$ we construct a predictor $p$. 

$p(a_0,\ldots,a_{k-1})$ is chosen as some number $a_{k}\in \{0,1\}$ so as to make the sequence $a_0,\ldots,a_k$ agree with $\varphi_t(0),\ldots,\varphi_t(k)$ for the minimal possible $t\le k$. Since we cannot wait for possibly hanging computations to halt, we only monitor the computations until stage $f(k)$ ($f(k)$ many computations steps). If there is no such $t$ we just set $a_{k}$ arbitrarily (say $=0$).

Now suppose $q$ is minimal such that $\varphi_q$ computes the computable sequence that is actually observed. Then we will for all but finitely many $k$ use $t=q$ and hence choose the correct $a_{k}$, because $f$ dominates the running time function for $\varphi_q$, namely $s(n)=$ the least stage where $\varphi_q(n)$ has halted.