Колмогоровская сложность: строгое определение «понимания»
Длина самой короткой программы, печатающей объект, — это не абстракция. Это точная мера того, насколько хорошо вы что-то поняли.
📐 В предыдущей статье мы говорили, что понимание — это сжатие. Но что такое «сжатие» строго? Интуиция подсказывает: если вы можете описать объект короче, чем он сам, вы что-то поняли. Колмогоровская сложность превращает эту интуицию в математическое определение.
Формально: колмогоровская сложность объекта (например, строки символов) — это длина самой короткой компьютерной программы, которая выдаёт этот объект в качестве результата[citation:1]. Программа написана на некотором фиксированном языке программирования, и сложность измеряется в битах (или символах) этой программы.
«Сложность строки — это длина наименьшей программы, которая печатает эту строку».
Что такое колмогоровская сложность
Представьте, что у вас есть чёрный ящик, который печатает строки. Вы подаёте на вход программу — он выдаёт строку. Колмогоровская сложность строки s — это длина самой короткой такой программы, которая напечатает именно s и остановится.
📖 Определение (упрощённо)
Пусть U — универсальная машина (например, интерпретатор Python). Тогда:
где |p| — длина программы p в битах, а U(p) — результат выполнения p на U.
Ключевой момент: выбор языка программирования почти не важен. Если перейти с Python на Java, сложность изменится не более чем на фиксированную константу (длину интерпретатора Python, написанного на Java). Эта константа не зависит от строки s. Поэтому колмогоровскую сложность называют языково-инвариантной с точностью до аддитивной константы[citation:2].
Пример: abababab против случайной строки
Рассмотрим две строки одинаковой длины (32 символа)[citation:1]:
Обе строки имеют длину 32. Но описать первую можно фразой «напиши ab 16 раз» — это около 17 символов. Вторую строку нечем описать, кроме как выписать её целиком (или почти целиком). Значит, колмогоровская сложность первой строки намного меньше, чем второй.
Чем короче минимальное описание, тем ниже колмогоровская сложность.
Это и есть строгая версия того, что мы называем «пониманием»: когда вы находите короткое описание, вы снижаете колмогоровскую сложность объекта в своём представлении.
Случайный шум несжимаем
Из определения следует фундаментальный факт: большинство строк несжимаемы. Почему? Программ длины меньше n бит существует меньше, чем строк длины n бит. Значит, на каждую короткую программу приходится не более одной строки, которую она печатает, а строк гораздо больше.
Следовательно, случайная строка почти наверняка имеет сложность, близкую к своей длине: K(s) ≈ |s|. Её нельзя сжать сколько-нибудь значительно. Это не недостаток алгоритмов сжатия — это математический закон.
🧮 Калькулятор: оцените сжимаемость строки
Введите строку, и калькулятор оценит её «эмпирическую сжимаемость» через простой алгоритм RLE (run-length encoding) — грубую верхнюю оценку.
Невычислимость: почему нельзя просто «посчитать» понимание
Кажется, что можно написать программу, которая вычисляет колмогоровскую сложность любой строки. Но это невозможно. Теорема, доказанная Колмогоровым и позже уточнённая, утверждает: не существует алгоритма, который для любой строки s возвращает K(s).
Доказательство использует парадокс, похожий на парадокс Берри («наименьшее число, которое нельзя описать менее чем двадцатью словами»). Если бы такой алгоритм существовал, можно было бы построить программу, которая находит строку со сложностью больше, чем длина самой этой программы, — что невозможно, потому что программа сама является описанием этой строки.
«Нет эффективного способа вычислить K(s). Мы можем только приближаться к ней сверху с помощью реальных архиваторов».
Это не мешает использовать колмогоровскую сложность как теоретический инструмент. Мы можем доказывать утверждения вида «существует строка со сложностью больше n» или «сложность этой конкретной строки не превосходит такой-то величины», даже если не умеем вычислять её точно.
Связь с пониманием: длина описания как критерий
Вернёмся к исходной теме. Если понимание — это сжатие, то колмогоровская сложность даёт нам строгий идеал: понять объект — значит найти программу, которая его порождает, и эта программа должна быть как можно короче.
- Ньютон не запоминал траектории всех падающих тел. Он написал закон, из которого они выводятся. Колмогоровская сложность этого закона (вместе с начальными условиями) намного меньше, чем сложность таблицы всех траекторий.
- Кеплер заменил тысячи строк наблюдений Марса тремя законами. Сложность законов ниже — и именно это мы называем пониманием.
- Теория Максвелла сжала гору фактов о магнетизме, электричестве и свете в четыре уравнения. Это акт сжатия в чистом виде.
📐 Практический критерий
Если ваше объяснение явления по длине сравнимо с самим явлением (или с таблицей его наблюдений), вы не поняли явление — вы его пересказали. Понимание начинается там, где длина описания падает.
Ограничения и критика
Колмогоровская сложность — мощный инструмент, но у него есть границы, которые важно признавать.
🔍 Три ограничения
- Зависимость от языка. Строго говоря, K(s) определена с точностью до аддитивной константы, зависящей от выбора универсальной машины. На практике это значит, что «самая короткая программа» — понятие относительное.
- Невычислимость. Мы не можем точно измерить K(s) для произвольной строки. Мы можем только оценивать её сверху реальными компрессорами.
- Сжатие ≠ истина. Краткая, но ложная теория (например, конспирологическая) тоже «сжимает» данные. Колмогоровская сложность не отличает науку от блестящей лжи — нужен эксперимент.
Тем не менее, как идеализация, колмогоровская сложность даёт нам язык для разговора о понимании. Она превращает расплывчатое «я это чувствую» в измеримую величину: насколько короче стало описание?
🎧 Подкаст: «Колмогоровская сложность за 2 минуты»
Слушайте краткое объяснение ключевых идей: что такое K(s), почему случайное несжимаемо и при чём здесь понимание.
💡 Главный вывод
Колмогоровская сложность — это длина самой короткой программы, печатающей объект. Понимание — это процесс снижения этой длины. Наука, красота и смех работают как архиваторы именно потому, что наш мозг вознаграждает за сокращение описания. Но помните: сжатие — необходимое, но не достаточное условие истины.
?>