Первой публикацией по алгоритмической теории информации является всемирно известная статья А.Н. Колмогорова «Три подхода к определению понятия “количество информации”», вышедшая в первом выпуске первого тома журнала «Проблемы передачи информации», который издается ИППИ РАН с 1965 г. В этой статье А.Н. Колмогоров указал способ измерения сложности конечного объекта (слова), для чего он ввел понятие, называемое сейчас колмогоровской сложностью. Своё новое понятие он применил для построения алгоритмического варианта теории информации, позволяющего измерять информацию в конечной строке знаков. Алгоритмическая теория информации, является естественным обобщением шенноновской вероятностной теории информации на конечные (дискретные) объекты. В рамках этой теории было получено точное определение индивидуального объекта, для которого выполняются все законы теории вероятностей, а именно, было дано точное определение индивидуальной случайной последовательности на основе понятия алгоритма.

Теория универсального кодирования дискретных вероятностных источников без искажений рассматривает задачу наилучшего описания (сжатия) данных в условиях, когда про источник известно только то, что он принадлежит некоторому множеству (источников). При этом используются различные постановки задачи и критерии эффективности. В ряде случаев они близки к задачам алгоритмической теории информации. Д.т.н. Ю.М. Штарьков, рассмотрел задачу универсального кодирования источников без памяти по критерию относительной избыточности и исследовал возможности применения известных результатов в некоторых практических задачах.

Предложенный А.Н. Колмогоровым не вероятностный способ рассмотрения статистических проблем привел к развитию прямых универсальных методов прогнозирования и классификации, не использующих гипотезы о вероятностных моделях, генерирующих исходные данные. В отличие от традиционного статистического подхода, при котором сначала восстанавливаются параметры предполагаемого вероятностного источника — модели, а затем эта модель используется для прогнозирования будущих данных, строятся адаптивные алгоритмы, которые в режиме он-лайн изучают закономерности временного ряда и производят прогнозы, удовлетворяющие заданным критериям качества. В настоящее время эти методы оформлены в виде алгоритмической теории самообучающихся алгоритмов (Algorithmic Learning Theory), которая тесно связана с разработкой и анализом работы практических компьютерных алгоритмов прогнозирования и классификации. В рамках этой теории специалистами ИППИ РАН разрабатываются универсальные алгоритмы прогнозирования временных рядов, возникающих в различных областях техники, финансов и статистики.

Результаты группы теоретических компьютерных исследований, в составе д.ф.-м.н. В.В. Вьюгина, к.ф.-м.н А. Шеня, к.ф.-м.н. А.Г. Ромащенко, к.ф.-м.н. Е.А. Асарина представлены в обзоре В.А.Успенский, В.В.Вьюгин «Становление алгоритмической теории информации в России». В частности, на алгоритмическом языке проводится анализ многих проблем теории кодирования, статистического анализа данных, алгоритмического и вероятностного прогнозирования и теории самообучающихся алгоритмов.