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 elaborationDefinition (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 resultsBy 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). CitationShane Legg 2006http://www.vetta.org/documents/IDSIA-12-06-1.pdf(not the author of this post)
Is predicting (in the limit) computable sequences as hard as the halting problem?
computability