Колмогоровская сложность и ее применение в машинном обучении

The materials represented in this article carry, mainly, surveying character. The aim of the paper is complete enough presentation of possibilities of mathematical apparatus of algorithmic complexity and probability for application in machine learning. Nevertheless, some new results are presented: theorems about exact compressors and decompressors, approach to determination of the moment of stopping of learning procedure on the basis of complexity analogue of the Bayes rule et al.