Effective prediction and its computational complexity

摘要

A model for the problem of predicting the outputs of a process, based only on knowledge of previous outputs, is proposed in terms of a decision problem. The strength of this particular formulation of the decision problem follows from the accuracy of its outputs in predicting the outputs of any particular deterministic process, and this predictability is quantified in terms of the number of bits the process may generate, and its length/time complexity. Both upper and lower bounds on the computational complexity of this decision problem are provided