Алгоритмическая теория информации и случайность индивидуальных объектов

В середине XX века Шеннон ввёл понятие энтропии, которое можно интуитивно описать как “среднее количестве битов информации в одном значении случайной величины”. Но его нельзя применить к индивидуальным объектам (скажем, к тексту романа или ДНК) — где нет ансамбля многих однородных объектов, нет и случайных величин.
В середине 1960-х годов разным людям (Колмогоров, Соломонов, Левин, Чейтин,…) стало понятно, что можно определять количество информации (сложность) индивидуального объекта как минимальную длину программы, которая этот объект порождает (при естественных ограничениях на язык программирования). Возникла алгоритмическая теория информации, которая оказалась связанной с разными областями: от философских вопросов оснований теории вероятностей (когда мы отвергаем статистические гипотезы?) до комбинаторики (неравенства, связывающие размеры множеств и их проекций) и теории вычислимости.
Я попытаюсь рассказать основные определения и какие-то из базовых результатов, а также (в зависимости от пожеланий аудитории) что-то про более современные работы.