The Complexity and Effectiveness of Prediction Algorithms

The problem of predicting an arbitrary sequence x₁x₂x₃ · · · is considered with x_{t + 1} being predicted from an analysis of the word x₁x₂ · · · x_t. There are no presumptions concerning the probability structure on this process. The relation between prediction effectiveness and Kolmogorov complexity is established. Then the Hausdorff dimension of sets of sequences for which effective methods of prediction exist is estimated. The prediction method which is asymptotically superior to other arbitrary ones realized by finite automata is constructed.