Is predicting (in the limit) computable sequences as hard as the halting problem?

Question

Question: Is predicting (as defined below) computable sequences as hard as the halting problem?

Elaboration: "Predict" means successfully predict, which means make only finitely many errors on the task of trying to predict the n-th bit of the sequence given access to the previous n-1 bits (starting from the first bit and going through the entire infinite computable sequence).

There's a simple diagonalization argument (due to Legg 2006) that for any Turing machine predictor p, there's a computable sequence on which it makes infinitely many errors. (Construct a sequence that has as its nth term the opposite of what p predicts given the previous n-1 terms in the sequence.) So there is no computable predictor that predicts every computable sequence. A halting oracle would allow construction of such a predictor. But can you show that having such a predictor allows you to solve the halting problem?

More elaboration

Definition (Legg)
A predictor p is a Turing machine that tries to predict the n-th bit of a sequence S given access to the previous n-1 bits. If the prediction fails to match the n-th bit of the sequence, we call this a mistake. We will say that p predicts S if p only makes finitely many mistakes on S. In other words, p predicts S if there is some number M in the sequence s.t. for every m>M, p correctly predicts the m-th bit of S given access to the first m-1 bits.

Formally, we could define a predictor machine as having three tapes. The sequence is entered as input bit-by-bit on one tape, the predictions for the next bit are made on a second tape (the machine can only move right across this tape), and then there is a work tape on which the machine can move in both directions.

Simple results
By the above definition, there's a predictor that predicts all the rational numbers. (Use the standard zig-zag enumeration of the rationals. Start by predicting the 1st rational in the list, if there's a mistake, move to the next rational.). By a similar argument, there's a predictor s.t. given access to N, is able to predict all sequences of Kolomogorov complexity less than or equal to N. (Run all the N-bit machines in parallel and take the prediction of the machine that halts first. You can only make finitely many errors).

Citation Shane Legg 2006 http://www.vetta.org/documents/IDSIA-12-06-1.pdf (not the author of this post)

Answer 1

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.