Алгоритмический подход к задаче прогнозирования

Решается задача прогнозирования символов произвольной последовательности $x_1,x_2,x_3,\dots,$ причем $x_{t+1}$ надо предсказывать по $x_1, x_2\dots x_t$. Никаких предположений о вероятностной структуре последовательности не делается. Используется теоретико- игровая постановка, предложенная Дж. Келли и позволяющая оценить эффективность прогноза величиной выигрыша в некоторой игре, Устанавливается связь максимальной величины выигрыша с Колмогоровской сложностью и оценивается хаусдорфова размерность множеств последовательностей, для которых возможен эффективный прогноз, Найден метод прогноза, оптимальный для класса конечных автоматов.