Будет рассмотрена комбинаторная переформулировка следующего утверждения про колмогоровскую сложность: для любого a < 1 существует такая бесконечная последовательность, что для всех пар слов, для которых vu является началом последовательности, выполнено неравенство K(u|v) > a|u| + O(1).

Данное утверждение является простым обобщением леммы Левина и было ранее доказано средствами Колмогоровской Сложности.

На докладе будет рассказано чисто комбинаторное доказательство данного утверждения.