Колмогоровская сложность как энергия: две статфизические модели в информатике

Колмогоровская (логарифмическая) сложность объекта (числа/текста/кода/вычислимой функции) определяется как длина кратчайшего описания этого объекта. Ни существование и единственность (с определенной точностью), ни невычислимость этой замечательной функции, введенной в 1950–60 годы, не являются интуитивно очевидными.
В докладе будет рассказано о двух независимых контекстах, в которых сложность появляется в вероятностных распределениях, связанных с информатикой, подобно тому, как энергия фигурирует в физических статсуммах. Эти контексты — закон Ципфа и асимптотическая граница для кодов, исправляющих ошибки.