Вычислимость
Колмогоровская сложность
В 1965 году советский математик Андрей Колмогоров сформулировал вопрос, который не давал покоя статистикам 50 лет: является ли конкретная строка '10110100...' случайной? До него у вопроса не было ответа - случайность была свойством процесса генерации, а не самой строки. Колмогоров предложил измерять случайность длиной кратчайшего описания. Этот подход объединил теорию информации, теорию вычислимости и основания математики в одну теорию.
- **NCD-классификация:** нормализованное расстояние сжатия используется для кластеризации геномов, обнаружения плагиата и сравнения языков без обучающих данных
- **MDL (Minimum Description Length):** принцип в машинном обучении - выбирать модель, минимизирующую K(данные | модель) + K(модель). Это формализация Occam's razor и основа регуляризации
- **Тестирование генераторов случайных чисел:** NIST SP 800-22 использует статистические тесты, приближающие проверку на несжимаемость
Колмогоровская сложность: определение
В 1965 году Андрей Колмогоров задал неудобный вопрос: что значит "случайная" строка? Его ответ перевернул теорию информации. Колмогоровская сложность K(x) строки x - это длина кратчайшей программы (на универсальной машине Тьюринга), которая выводит x и останавливается. Строка 'aaaaaaaaa...a' (миллион символов 'a') имеет крошечную сложность - программа `print('a' * 1_000_000)` коротка. Строка из миллиона случайных бит имеет сложность около миллиона бит - описание не короче самой строки.
K(x) зависит от выбора универсальной машины Тьюринга U, но лишь до константы: для двух машин U1 и U2 выполняется |K_U1(x) - K_U2(x)| <= c, где c не зависит от x. Это свойство инвариантности делает K(x) объективной мерой сложности.
Чему равна K(x) для строки x длиной n, если x = '000...0' (n нулей)?
Несжимаемые строки и лемма о несжимаемости
Большинство строк несжимаемы - и это не интуиция, а теорема. Из 2^n строк длиной n ровно 2^(n-c) - 1 строк имеют K(x) >= n - c. При c = 1 это больше половины. Принцип Дирихле: программ короче n - 1 бит ровно 2^(n-1) штук - они не могут описать все 2^n строк. Лемма о несжимаемости используется в теоретической CS так же, как метод вероятностных аргументов: предполагается, что строка c-несжимаема (K(x) >= |x| - c), и из этого выводятся нижние оценки.
Лемма о несжимаемости: для любого c >= 0 существует c-несжимаемая строка длины n при каждом n >= c. Доля несжимаемых строк стремится к 1 при n -> inf.
Почему невозможно сжать все строки длиной n хотя бы на 1 бит?
Случайность через сложность
Что делает строку случайной? До Колмогорова ответа не было - случайность определялась через процесс генерации (бросок монеты), а не через саму строку. Мартин-Лоф и Колмогоров дали структурное определение: строка x случайна по Мартин-Лофу тогда и только тогда, когда K(x) >= |x| - c для некоторой константы c. Строка, которую можно сжать, содержит скрытую структуру - закономерность, которую алгоритм сжатия эксплуатирует. Истинно случайная строка - это строка без структуры, кратчайшее её описание - она сама.
Теорема Мартин-Лофа - Чайтина: три подхода к случайности совпадают: (1) несжимаемость по Колмогорову, (2) прохождение всех статистических тестов (Мартин-Лоф), (3) невозможность ставок против (мартингалы по Шнорру). Это один из глубочайших результатов теоретической CS.
Последовательность 0101010101... (n символов). Чему равна приблизительно K этой строки?
Применения колмогоровской сложности
Колмогоровская сложность - не просто теоретический конструкт. Нормализованное расстояние сжатия (NCD) позволяет кластеризовать объекты без какой-либо предметной области: NCD(x,y) = (K(xy) - min(K(x), K(y))) / max(K(x), K(y)). Это расстояние используют для классификации геномов, обнаружения плагиата, кластеризации языков. В ML: минимальная длина описания (MDL - Minimum Description Length) - это байесовский Occam's razor на языке K: выбирай модель, минимизирующую K(data | model) + K(model). Это основа регуляризации.
K невычислима (сводится к проблеме остановки), но аппроксимируется через реальные архиваторы (gzip, zstd). NCD на основе gzip достигает точности профессиональных классификаторов на задачах кластеризации без обучающих данных.
Сжимаемость в реальных архиваторах (gzip, zstd) - это и есть колмогоровская сложность
Реальные архиваторы дают верхнюю оценку K(x), но никогда не достигают минимума
K(x) - это теоретический минимум по всем возможным программам на универсальной машине Тьюринга. Архиваторы реализуют конкретные алгоритмы (LZ77, Huffman) и не перебирают все программы. Разрыв между K(x) и выводом gzip может быть произвольно большим.
Почему колмогоровскую сложность нельзя вычислить точно?
Ключевые идеи
- **K(x) - длина кратчайшей программы:** минимальное количество бит для описания объекта. Регулярные строки имеют K = O(log n), случайные - K = n - O(1).
- **Несжимаемость - норма:** большинство строк несжимаемы. Доля строк с K(x) >= n - c стремится к 1 при росте n.
- **Случайность = несжимаемость:** строка случайна по Мартин-Лофу тогда и только тогда, когда K(x) >= |x| - O(1). Три определения случайности совпадают.
- **K невычислима, но аппроксимируема:** через реальные архиваторы. NCD дает практически полезное расстояние между объектами.
Связанные темы
Колмогоровская сложность связана с теорией невычислимости и теорией информации.
- Проблема остановки — K(x) невычислима по той же причине - вычисление K сводится к HP
- Mapping Reductions — Невычислимость K доказывается через редукцию от проблемы остановки
Вопросы для размышления
- Если K(x) невычислима, как можно использовать её в теоретических доказательствах? Что именно доказывает лемма о несжимаемости, если мы не можем найти несжимаемую строку алгоритмически?
- MDL-принцип говорит: выбирай простейшую модель, объясняющую данные. Чем это отличается от байесовского вывода? Что теряется при переходе от K(x) к реальным архиваторам?
- Строка пи (3.14159...) кажется случайной, но описывается коротко: 'первые n цифр числа пи'. Что это говорит о связи математической структуры и случайности?