EssayAI
Блог
Блог
Естественные науки

Колмогоровская сложность: длина кратчайшего описания

8 ноября 2026Время чтения: 8 минут
#колмогоровская сложность#теория информации#алгоритмы#сжатие данных#вычислимость
Колмогоровская сложность: длина кратчайшего описания

Колмогоровская сложность измеряет, насколько кратко можно точно описать отдельный объект с помощью программы. Для длинной строки из нулей достаточно указать правило повторения и длину; для другой строки столь короткого правила может не существовать. Мера определяется длиной кратчайшей программы, которая выдаёт строку и останавливается. Она помогает рассуждать о сжатии и алгоритмической случайности, хотя общего способа вычислить её точное значение нет. Калькулятор ниже иллюстрирует доказательство подсчётом: меняйте длину строк и порог описания, чтобы увидеть гарантированное число строк без слишком коротких программ.

Определение: программа как описание

Зафиксируем универсальную вычислительную машину UU, принимающую двоичную программу pp. Простая колмогоровская сложность конечной двоичной строки xx определяется так:

CU(x)=min⁡{∣p∣:U(p)=x}.C_U(x) = \min\{\lvert p\rvert : U(p)=x\}.

Здесь ∣p∣\lvert p\rvert - длина программы в битах, а равенство означает, что машина выводит в точности xx и останавливается. В литературе для разных вариантов сложности встречаются обозначения CC и KK; ниже для краткости используем KK для определённой выше простой сложности. Вводимая отдельно префиксная сложность использует самоделимитирующиеся программы и имеет другие технические оценки.

Слово «программа» не обязательно означает код на привычном языке. Важно зафиксировать способ записи битов и исполнитель, а также учитывать всю информацию, необходимую для восстановления строки. Если программа получает xx на вход бесплатно, она уже описывает другую величину - условную сложность. Нельзя спрятать часть исходных данных в невидимой библиотеке и назвать описание коротким без указания этого условия.

Подход к информации через алгоритмическое описание изложен в работе А. Н. Колмогорова 1965 года. Он относится к конкретному объекту, а не требует заранее задавать вероятностное распределение источника. Кодирование символов в реальном сообщении обсуждается отдельно в статье о равномерном и неравномерном кодировании.

Повторы, описания и размер программы

Представим две строки длиной миллион бит. Первая состоит только из нулей. Её можно задать инструкцией «вывести ноль миллион раз», добавив к инструкции двоичную запись числа повторений. Длина такого описания растёт примерно как число бит для записи длины, плюс постоянные затраты на саму программу. Это лишь верхняя оценка: мы нашли описание, но не доказали, что более короткого нет.

Вторая строка может выглядеть беспорядочной. Для некоторых строк действительно не найдётся программы существенно короче них самих. Но по виду конкретной последовательности это не доказать: даже длинный фрагмент с неочевидным узором может порождаться коротким правилом. Например, первые миллион двоичных знаков числа, заданного коротким алгоритмом, могут выглядеть случайно и всё же иметь компактное описание при условии, что в программе указана нужная длина.

Обратная тривиальная стратегия - включить саму строку в программу и вывести её. Для фиксированной универсальной машины простая сложность не превосходит длину строки более чем на некоторую константу: K(x)≤∣x∣+cK(x)\leq |x|+c. Константа зависит от выбранного исполнителя и способа записи, поэтому для коротких строк накладные расходы особенно важны.

Почему коротких программ не хватает

При длине nn существует ровно 2n2^n двоичных строк. Программ длины строго меньше kk не больше, чем всех битовых слов такой длины, включая пустое слово:

1+2+4+…+2k−1=2k−1.1+2+4+\ldots+2^{k-1}=2^k-1.

Каждая остановившаяся программа выдаёт только один результат. Значит, не более 2k−12^k-1 разных строк могут иметь описание короче kk. Некоторые программы не остановятся, а несколько программ могут дать одну строку, поэтому равенство здесь не гарантируется. При k≤nk\leq n отсюда следует нижняя граница:

#{x:∣x∣=n, K(x)≥k}≥2n−(2k−1).\#\{x: |x|=n,\ K(x)\geq k\}\geq 2^n-(2^k-1).

Подсветка постепенно отмечает максимум строк, которые могли бы покрыть 15 коротких программ; среди 256 строк остаётся не менее 241 без такого описания.

Движение показывает предельный случай: каждой короткой программе условно сопоставлена отдельная строка длиной восемь бит. Это не поиск конкретных сложных строк и не утверждение, что отмеченные программы останавливаются. Реальных разных результатов может быть меньше, а число оставшихся строк - больше.

Пример: восемь бит и порог четыре

Пусть n=8n=8, а k=4k=4. Всего есть 28=2562^8=256 строк. Возможных программ длины от нуля до трёх бит - 1+2+4+8=151+2+4+8=15. Поэтому не менее 256−15=241256-15=241 строки имеют сложность не меньше четырёх бит. Это примерно 94,14%94{,}14\% всех восьмибитовых строк.

Среди 256 восьмибитовых строк не более 15 могут иметь программу короче четырёх бит, поэтому не менее 241 такой программы не имеют
Среди 256 восьмибитовых строк не более 15 могут иметь программу короче четырёх бит, поэтому не менее 241 такой программы не имеют

Более общий вывод получают, положив k=n−dk=n-d для целого dd от нуля до n−1n-1. Доля строк, описываемых программой короче n−dn-d, меньше 2−d2^{-d}. При увеличении требуемого выигрыша на один бит эта верхняя граница доли уменьшается вдвое. Это утверждение о множестве строк; оно не говорит, какие именно строки в нём находятся.

Зачем фиксировать универсальную машину

На разных языках одна и та же строка может иметь программы разной длины. Однако универсальная машина способна имитировать другую машину: достаточно добавить фиксированный переводчик к её программе. Теорема инвариантности утверждает, что для двух фиксированных универсальных машин значения простой сложности отличаются не более чем на постоянную, зависящую от пары машин, но не от строки.

Эта постоянная может быть большой. Теорема не обещает одинаковых значений в битах для короткого примера и не позволяет сравнивать числа без указания модели. Её смысл асимптотический: при рассмотрении всё более длинных объектов выбор универсальной машины добавляет ограниченную поправку, а не произвольную функцию длины.

Условная сложность K(x∣y)K(x\mid y), в свою очередь, измеряет длину кратчайшей программы для xx, если yy уже доступно исполнителю. Так можно отдельно спросить, сколько нового нужно сообщить о строке при известной длине или при наличии другой строки. Условие должно быть явно названо: иначе сравнение с безусловной сложностью вводит в заблуждение.

Почему точное значение не вычислить

Можно запускать программы и сохранять длины тех, что уже выдали нужную строку. Если нашлась программа длины 100 бит, это доказывает верхнюю оценку K(x)≤100K(x)\leq100. Позднее может найтись ещё более короткая. Но для точного ответа нужно исключить все короткие программы, которые пока не завершились. Общий алгоритм не умеет определить для каждой из них, остановится она когда-нибудь или работает бесконечно.

Невычислимость можно увидеть и через противоречие. Предположим, что существует алгоритм точного вычисления KK. Тогда для любого достаточно большого mm можно перебрать строки и выбрать первую со сложностью больше mm: такая строка существует по приведённому подсчёту. Но сама процедура выбора вместе с записью mm задаёт эту строку программой длины порядка log⁡m\log m плюс постоянная. При больших mm это меньше mm, что противоречит условию выбора. Следовательно, предполагаемого алгоритма нет.

Это не запрет на любые оценки. Конкретная программа даёт проверяемую верхнюю границу, а математическое доказательство иногда даёт нижнюю. Просто универсальный метод, который всегда выдаёт точный минимум для произвольной строки, невозможен.

Сжатие, энтропия и сложность алгоритма

Архиватор строит практически полезное описание данных для определённого декодера. Если он действительно восстанавливает исходную строку без потерь, размер архива вместе с нужным фиксированным декодером даёт верхнюю оценку сложности. Плохое сжатие конкретным архиватором не доказывает высокую сложность: другой алгоритм может обнаружить структуру, которую первый пропустил. Кроме того, в практических форматах существенны заголовки и служебные данные.

Количество информации по Шеннону связано с вероятностями исходов, а энтропия - со средним по распределению. Колмогоровская сложность характеризует отдельную строку относительно машины. Теории связаны результатами о средних длинах описаний, но подставлять энтропию вместо сложности одной конкретной строки нельзя.

Слово «сложность» также не означает время исполнения кратчайшей программы. Короткое описание может потребовать очень долгого вычисления. Напротив, временная и пространственная сложность изучает ресурсы алгоритма при росте входа, а цикломатическая сложность описывает структуру ветвлений программы. Эти меры отвечают на разные вопросы и не выражаются друг через друга простым равенством.

Частые ошибки

  • Считать сжатый архив точным значением KK. Он даёт описание и тем самым верхнюю оценку, но не доказывает оптимальности.
  • Объявлять строку случайной по внешнему виду. Неочевидный шаблон всё равно может задаваться короткой программой.
  • Забывать длину и декодер. Их стоимость либо включают в описание, либо явно оговаривают как условие и фиксированную машину.
  • Принимать оценку подсчётом за точное число. Не все программы останавливаются и не все дают разные результаты нужной длины.
  • Путать сложность описания со скоростью. Кратчайшая программа может работать очень долго.

FAQ

Можно ли вычислить сложность для конкретной строки?

Иногда точное значение удаётся доказать относительно заданной машины. В общем случае алгоритма, который точно отвечает для любой строки, не существует. Найденная программа всегда даёт верхнюю оценку.

Является ли строка из случайных битов несжимаемой?

Среди всех строк одной длины доля существенно сжимаемых мала, поэтому равномерный случайный выбор с высокой вероятностью даст строку без сильно короткого описания. Для отдельного результата это вероятностное рассуждение не указывает его точную сложность.

Зависит ли сложность от языка программирования?

Да. Для двух фиксированных универсальных машин разница ограничена константой, но на коротких строках она может существенно влиять на результат. Поэтому конкретные значения имеют смысл только с указанной машиной и правилами записи.

Коротко

Колмогоровская сложность - длина кратчайшей останавливающейся программы, выводящей объект. Подсчёт показывает существование большого числа строк без короткого описания, но не даёт общего алгоритма для нахождения точной сложности конкретной строки. Практическое сжатие предоставляет полезные верхние оценки; его результат зависит от выбранного метода и не удостоверяет минимальность.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

8 ноября 20268 минут
Алгоритм LZW: сжатие данных с помощью словаря

Алгоритм LZW: сжатие данных с помощью словаря

Алгоритм LZW по шагам: как строится словарь фраз, выдаются коды и восстанавливается исходная строка. Разберём пример, особый случай декодирования и оценку размера.

8 ноября 20268 минут
Числа Белла: разбиения множества и формула

Числа Белла: разбиения множества и формула

Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

8 ноября 20269 минут
Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

8 ноября 20269 минут
Чётность подстановки: инверсии и знак

Чётность подстановки: инверсии и знак

Чётность подстановки через инверсии, транспозиции и циклы: пошаговый подсчёт, доказательство независимости разложения и применение в алгоритмах и определителях.

8 ноября 20268 минут
Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.

8 ноября 20268 минут