Введение: Загадка трёх строк длиной в миллион бит — Слепое пятно теории информации Шеннона
Представьте, что перед вами лежат три двоичные строки, каждая длиной ровно $1\,000\,000$ бит:
- Первая строка $S_1$ — это пятьсот тысяч раз повторённая комбинация
01:01010101...01. - Вторая строка $S_2$ — первые $1\,000\,000$ двоичных знаков после запятой числа $\pi$:
1100100100001111110110.... - Третья строка $S_3$ получена в результате миллиона реальных подбрасываний симметричной монеты (орёл =
1, решка =0).
Какая из этих трёх строк содержит больше «информации»? Какая из них «сложнее», и какая является по-настоящему «случайной»? Если мы обратимся к классической теории информации Клода Шеннона (1948), мы столкнёмся с неожиданным парадоксом: шенноновская энтропия $H(X) = -\sum P(x)\log_2 P(x)$ измеряет среднюю неопределённость распределения вероятностей (ансамбля источника), но совершенно ничего не говорит о внутренней сложности отдельного конкретного объекта $x$! В модели честной монеты вероятность выпадения идеально регулярной строки $S_1$ и хаотичной строки $S_3$ абсолютно одинакова и равна $2^{-1\,000\,000}$; а для детерминированной константы $\pi$ ($S_2$) распределение вообще вырождено в одну точку с нулевой энтропией ($H=0$), хотя частота нулей и единиц в ней проходит любые статистические тесты на псевдослучайность!
Чтобы дать строгое математическое определение сложности и случайности индивидуального объекта, Рэй Соломонофф (1960), Андрей Николаевич Колмогоров (1965) и Грегори Хайтин (1966) независимо друг от друга создали алгоритмическую теорию информации (Algorithmic Information Theory, AIT). Их ключевая идея проста и гениальна: истинная сложность объекта определяется не количеством символов в нём, а длиной самой короткой компьютерной программы, способной этот объект породить!
flowchart TD
S1["String S1: 010101...01 (1M bits)"] -->|"Short Loop Program"| K1["K(S1) = O(log n) bits (Highly Compressible)"]
S2["String S2: Binary Digits of Pi (1M bits)"] -->|"Spigot Algorithm"| K2["K(S2) = O(log n) bits (Deterministic Law)"]
S3["String S3: Fair Coin Flips (1M bits)"] -->|"No Pattern / Hardcoded"| K3["K(S3) >= n - O(1) bits (Algorithmically Random)"]
1. Колмогоровская сложность $K(x)$ и теорема об инвариантности
Зафиксируем универсальную машину Тьюринга $U$ (или любой Тьюринг-полный язык программирования, такой как C или Python). Колмогоровской сложностью $K_U(x)$ двоичной строки $x \in \{0,1\}^*$ называется битовая длина $|p|$ кратчайшей программы $p$, которая при запуске на машине $U$ выводит строку $x$ и останавливается. Чтобы выполнялось неравенство Крафта $\sum 2^{-|p|} \le 1$, в современной теории обычно используется беспрефиксная сложность (сложность Левина — Хайтина) $K(x)$, при которой ни одна допустимая программа не является началом другой.
Взглянем на наши три строки длиной в миллион бит сквозь призму $K(x)$:
- Для $S_1$ достаточно крошечной программы
print("01" * 500000). Поскольку в программе нужно закодировать лишь двоичную запись счётчика цикла $n/2$, получаем $K(S_1) = O(\log_2 n) pprox 20$ бит — эта строка алгоритмически тривиальна. - Для $S_2$ (первые $n$ бит числа $\pi$), несмотря на кажущийся хаос битов, программа длиной в несколько сотен байт, реализующая формулу Мэчина или капельный алгоритм BBP, вычисляет $S_2$ абсолютно точно. Следовательно, и здесь $K(S_2) = O(\log_2 n)$! Это открывает глубокую философскую истину: закон природы — это не что иное, как предельное алгоритмическое сжатие эмпирических наблюдений.
- Напротив, для строки $S_3$, полученной бросками монеты, не существует никакой скрытой закономерности. Кратчайшая программа для вывода $S_3$ вынуждена буквально хранить все миллион бит в явном виде (
print("1011001...")), поэтому $K(S_3) pprox n + O(1) pprox 1\,000\,000$ бит!
Возникает естественный вопрос: не зависит ли $K_U(x)$ от произвольного выбора языка программирования $U$? Теорема Колмогорова об инвариантности (Invariance Theorem) доказывает, что нет: для любых двух универсальных машин Тьюринга $U_1$ и $U_2$ существует константа $c_{12}$, зависящая только от $U_1$ и $U_2$ (и не зависящая от строки $x$), такая что $|K_{U_1}(x) - K_{U_2}(x)| \le c_{12}$. Доказательство прозрачно: $c_{12}$ — это просто фиксированный размер интерпретатора (симулятора) машины $U_2$, написанного на языке $U_1$! При стремлении длины данных $n o \infty$ эта константа становится пренебрежимо малой.
$$ H(X) = -\sum_{x \in \mathcal{X}} P(X = x) \log_2 P(X = x) $$$$ K_U(x) = \min_{p \in \{0,1\}^*} \Big\{ |p| \;\Big|\; U(p) = x \Big\}, \qquad \Big| K_{U_1}(x) - K_{U_2}(x) \Big| \le c_{12} $$2. Природа случайности: принцип Дирихле, несжимаемость и случайность по Мартин-Лёфу
До Колмогорова теория вероятностей не могла объяснить, почему индивидуальная строка 0000000000 не случайна, а 0110100110 кажется случайной. Алгоритмическая теория информации дала первое строгое определение: случайность есть несжимаемость — полное отсутствие алгоритмических закономерностей!
Более того, с помощью элементарного принципа Дирихле (Pigeonhole Principle) в две строчки доказывается, что подавляющее большинство двоичных строк алгоритмически случайны (несжимаемы): Всего существует ровно $2^n$ двоичных строк длины $n$. А сколько существует двоичных программ длины строго меньше $n - c$ бит? Суммируя количество программ длины $0, 1, \dots, n-c-1$, получаем $\sum_{i=0}^{n-c-1} 2^i = 2^{n-c} - 1$ возможных программ. Поскольку каждая программа выдаёт не более одного результата, из $2^n$ строк длины $n$ не более чем $2^{n-c} - 1$ строк могут быть сжаты хотя бы на $c$ бит ($K(x) < n - c$)! Иными словами, доля строк длины $n$, поддающихся сжатию на $c$ бит и более, строго меньше $2^{-c}$. При $c = 20$ свыше $99,9999\,\%$ всех строк невозможно сжать даже на $20$ бит никаким мыслимым алгоритмом! Пер Мартин-Лёф в 1966 году доказал, что бесконечная двоичная последовательность проходит все вычислимые статистические тесты на случайность (случайность по Мартин-Лёфу) тогда и только тогда, когда все её префиксы $x_{1:n}$ несжимаемы ($K(x_{1:n}) \ge n - O(1)$).
$$ \sum_{i=0}^{n-c-1} 2^i = 2^{n-c} - 1 \implies \mathbb{P}_{x \sim \text{Unif}(\{0,1\}^n)}\big( K(x) < n - c \big) < \frac{2^{n-c}}{2^n} = 2^{-c} $$$$ \Omega = \sum_{p:\, U(p)\text{ halts}} 2^{-|p|} \in (0, 1), \qquad K(\Omega_{1:n}) \ge n - O(1) $$
flowchart TD
A["Assume Program P_K Computes K(x)"] --> B["Construct Program Q of Length L = |Q|"]
B --> C["Q Searches Lexicographically for First String s with K(s) > L + 1000"]
C --> D["Q Outputs s, so by Definition K(s) <= |Q| = L"]
D --> E["Contradiction: L + 1000 < K(s) <= L (Berry Paradox / Uncomputability)"]
3. Парадокс Берри, невычислимость $K(x)$, константа Хайтина $\Omega$ и современный ИИ
Можно ли написать идеальный архиватор, который для любой входной строки $x$ вычисляет её точную сложность $K(x)$? Ответ категоричен: нет, функция $K(x)$ алгоритмически невычислима!
Это ограничение восходит к классическому парадоксу Берри («наименьшее натуральное число, которое нельзя описать менее чем двадцатью словами» — фраза из двенадцати слов, описывающая это число!). Грегори Хайтин формализовал его так: допустим, существует подпрограмма ComputeK(x) фиксированной длины $L$ бит, вычисляющая $K(x)$. Построим главную программу $Q$, которая перебирает все строки $s$ в лексикографическом порядке, вызывает ComputeK(s) и выводит первую же строку $s^*$, для которой $K(s^*) > L + 10000$. Полная длина программы $Q$ составляет всего $L + O(1)$ бит, но она выдаёт $s^*$! По определению $K(s^*)$ как длины кратчайшей программы должно выполняться $K(s^*) \le |Q| < L + 10000$, что прямо противоречит условию $K(s^*) > L + 10000$! Отсюда следует теорема Хайтина о неполноте: никакая формальная аксиоматическая система сложности $C$ бит не способна доказать оценку $K(x) > C + O(1)$ ни для какой конкретной строки $x$.
Хайтин также определил вероятность остановки универсальной беспрефиксной машины Тьюринга — легендарную константу Омега $\Omega = \sum_{U(p) ext{ останавливается}} 2^{-|p|}$. Число $\Omega \in (0,1)$ строго определено, но абсолютно невычислимо и алгоритмически случайно ($K(\Omega_{1:n}) \ge n - O(1)$): знание первых $n$ бит числа $\Omega$ позволяет решить проблему остановки Тьюринга для всех программ длины до $n$!
В современной инженерии и искусственном интеллекте вычислимые оценки сверху для $K(x)$ лежат в основе прорывных технологий:
- Связь с энтропией Шеннона: для стационарных эргодических источников математическое ожидание $ rac{1}{n}\mathbb{E}[K(X_{1:n})]$ сходится к скорости энтропии Шеннона $H(X)$.
- Универсальная индукция Соломоноффа и принцип минимальной длины описания (MDL): бритва Оккама формализуется через универсальное априорное распределение $P_M(x) \propto 2^{-K(x)}$.
- Нормализованное расстояние сжатия (NCD): аппроксимируя $K(x)$ реальными архиваторами (
zstd,lzma,gzip), формула $ ext{NCD}(x,y) = rac{C(xy) - \min(C(x),C(y))}{\max(C(x),C(y))}$ позволяет строить эволюционные деревья геномов и классифицировать вредоносный код без ручного выделения признаков. - Большие языковые модели (LLM): сжатие есть интеллект: как показали Маркус Хаттер (Hutter Prize) и Илья Суцкевер, минимизация кросс-энтропийной функции потерь $-\sum \log_2 P_ heta(x_t \mid x_{
математически эквивалентна поиску кратчайшего сжатия данных без потерь. Чтобы сжать человеческие тексты до предела, нейросеть вынуждена усвоить грамматику, логику и причинно-следственную модель мира.
| Измерение / Концепция | Энтропия Шеннона $H(X)$ | Колмогоровская сложность $K(x)$ | Инженерные аппроксимации (MDL / LLM / NCD) |
|---|---|---|---|
| Объект измерения | Распределение вероятностей (ансамбль) | Индивидуальный объект / строка $x$ | Реальные файлы, геномы, текстовые корпуса |
| Оценка первых $10^6$ бит числа $\pi$ | Детерминированная константа ($H=0$); частоты равномерны | $K(\pi_{1:n}) = O(\log n)$ (проста благодаря короткому алгоритму) | Арифметическое кодирование и нейросети находят структуру |
| Вычислимость | Точно вычислима при известном распределении $P(X)$ | Строго невычислима (эквивалентна проблеме остановки) | Оценки сверху через zstd/LZMA или Transformer $P_ heta$ |
| Ключевые теоремы и философия | Теорема Шеннона о кодировании источника | Теорема об инвариантности, неполнота Хайтина, число $\Omega$ | Бритва Оккама, «Сжатие = Предсказание = Интеллект» |