Аннотация:
Количество информации в слове измеряется его колмогоровской сложностью. Однако не все слова данной сложности "одинаковы": помимо сложности (числа), есть некоторая другая характеристика, которая измеряется некоторой кривой. Эту кривую можно задавать в разных координатах и толковать по-разному: насколько быстро убывает сложность с ограничением на время при увеличении времени, какие есть двухчастные описания, как близко к концу списка слов сложности не выше N находится наше слово, и пр.
Предполагается обзор простых результатов и обсуждение более сложных (по работам Верещагина, Витаньи, Гача, Тромпа, Антунеса и других).
|
