Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов

В 1964 г. А. Н. Колмогоров ввел понятие сложности конечного объекта (например, слова в некотором алфавите). Сложность он определял как минимальное число двоичных знаков, содержащих всю информацию о задаваемом объекте, достаточную для его восстановления (декодирования). Это определение существенно зависит от метода декодирования, однако с помощью общей теории алгоритмов А. Н. Колмогорову удалось дать инвариантное (универсальное) определение сложности. Близкие понятия рассматривались Р. Дж. Соломоновым (США) и А. А. Марковым. На базе понятия сложности А. Н. Колмогоров дал определение количества информации в конечных объектах и понятия случайной последовательности (уточненное потом в работах П. Мартин-Лёфа). Впоследствии этот круг вопросов быстро развивался. В частности, интересное развитие получили идеи А. А. Маркова о применении понятия сложности для изучения количественных вопросов теории алгоритмов. Настоящая статья представляет собой обзор основных результатов, связанных со всем изложенным.