Глава 6. Колмогоровская сложность и алгоритмическая информация

Где стоит глава

У информации есть вторая мера. Энтропия Шеннона (Глава 5) измеряет распределение — сколько различений в среднем; колмогоровская сложность $K(x)$ измеряет конкретную строку — длину кратчайшей программы, её порождающей. Шеннон статистичен, Колмогоров алгоритмичен; вместе они — две меры информации на двух сторонах границы финитизации.

Сжатие реализует $K$ сверху — это Element (конечный код); сам $K$ невычислим тем же диагональным двигателем, что халтинг и несчётность — четвёртая грань одной границы (предел-роль).

Глава наводит мост между двумя мерами. Невычислимость $K$ здесь цитируется, а не передоказывается (её диагональный вывод принадлежит вычислительной части, Часть XV); глава ставит её на место как грань общей границы и связывает с Шенноном.

Две меры информации

Колмогоровская сложность $K(x)$ — длина кратчайшей программы (на фиксированной модели вычисления), выводящей строку $x$. Это роль-предел: минимум по всем программам. Несжимаемые строки существуют — чистым счётом: бинарных программ длины $<n$ всего $2^n-1$, а строк длины $n$ ровно $2^n$, поэтому хотя бы одна строка длины $n$ не имеет описания короче $n$¹ (та же голубятня, что в первой главе части).

Различие с Шенноном принципиально. Шеннон приписывает информацию распределению (нужно знать вероятности); Колмогоров — самой строке (вероятности не нужны). Случайность по Колмогорову — это несжимаемость: строка случайна, если её кратчайшее описание — она сама.

Сжатие реализует $K${K} сверху

Хотя $K$ невычислим, его можно приближать сверху: всякий конкретный компрессор даёт длину, не меньшую $K$. И здесь работает Element-сторона: префиксные коды верифицированы — бинарное дерево задаёт беспрефиксный код, сумма Крафта $\sum 2^{-l_i}=1$, и на конкретном диадическом распределении $\{\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{8}\}$ оптимальное дерево достигает средней длины $\frac{7}{4}$ бит — ровно энтропии этого распределения². Сжатие получает и физическое чтение: наблюдатель моделируется как компрессор, а само сжатие укладывается в тот же тип процесса (моды, спектр, энергия), что и физические³.

Конкретное сжатие — Element: конечный код, вычислимая верхняя оценка $K$. Это завершающийся процесс описания.

$K${K} невычислима — четвёртая грань одной границы

Сам $K$, в отличие от его приближений, невычислим: в фиксированной модели нет тотального алгоритма, выдающего $K(x)$ для всех $x$. И невычислимость эта — не отдельный факт, а та же диагональ, что халтинг, канторова булева диагональ ($A\to \mathsf{bool}$; несчётность, Часть IV) и парадокс Рассела: предположение о $K$-решателе разбивается тем же диагональным двигателем⁴.

$K(x)$ — четвёртая грань ОДНОЙ границы: дискриминант / халтинг / Кантор / $K(x)$. Один диагональный двигатель, четыре лица.

Это и есть мост от прикладной части к финитизационной границе всего проекта⁵. Невычислимость $K$ — не дефект и не запрет, а P4-статус: $K$ есть роль-предел, минимум по незавершимому семейству программ, достижимый лишь как процесс приближения сверху.

Мост Шеннон $\leftrightarrow$ Колмогоров

Две меры связаны: для вычислимого распределения ожидаемая колмогоровская сложность совпадает с энтропией Шеннона с точностью до константы (классическая теорема кодирования; здесь — фон, не выводим): статистическая и алгоритмическая информация сходятся. Но граница финитизации проходит между ними по разрешимости.

Шеннон на конечном распределении и конкретное сжатие — Element (разрешимо, вычислимо). Точный $K$ — предел-роль (невычислим). Две меры информации, две стороны одной границы.

Шенноновская мера на конечном пространстве — вычислимый процесс над ℚ (в диадических случаях — точное конечное число битов, в общем — число-процесс, как ${\log }_{2}3$ в Главе 5); компрессия даёт вычислимую верхнюю оценку $K$ (Element); но точное $K$ убегает за границу (предел-роль). Мера информации, как и всё в этой части, разрезана финитизацией: её конечно-вычислимая сторона достижима, её точно-минимальная — процесс, не завершённый объект.

E/R/R-разбор: алгоритмическая информация как система

Разберём по E/R/R в порождающем порядке Rules $\to$ Roles $\to$ Elements.

Rules (L5). Удерживающее правило — минимизация описания: $K(x)$ есть кратчайшая программа, выводящая $x$. К нему примыкает диагональное правило, разбивающее всякий предполагаемый $K$-решатель (то же, что у халтинга).

Roles (L4). $K(x)$ — роль-предел (минимум по семейству программ); сжатие — роль приближения сверху; несжимаемость — роль случайности. Шеннон и Колмогоров — две меры (роли) одной информации (статистическая / алгоритмическая).

Elements (L1 + P4). Носители — конкретные строки и конкретные программы-коды (Хаффман); конечные сжатия. Под P4 актуальны они и любая вычислимая верхняя оценка $K$; тотальный $K$-оракул — предел-роль (диагональ), не завершённый объект.

Проверка сформированности. Минимизация и диагональ — Rules; $K$, сжатие, две меры — Roles; строки и коды — Elements; пересечений нет. В корректной постановке правило минимизации не есть программа своего же языка; коллапс возникает именно при попытке реифицировать его как тотальный решатель внутри той же вычислительной арены — тот самый диагональный коллапс (P1-тень).

Что даёт разбор. Он показывает, что алгоритмическая информация повторяет структуру всей части: конечно-вычислимая сторона (сжатие, верхние оценки) — Element, точно-минимальная ($K$) — предел-роль; и что эта граница есть та же, что несёт весь проект, — $K(x)$ как четвёртая грань диагональной границы.

Две меры информации наведены друг на друга; остаётся последний шаг части — предел самой информации. В следующей главе — принцип неопределённости в информации и мост к фон-Нейману и квантовой информации (Том III).

---

---

Часть: Часть XVII. Дискретная математика, вероятность, информация · Том: «Математика»

Навигация: ← Глава 5. Энтропия Шеннона · Глава 7. Принцип неопределённости в информации →

Footnotes

1. incompressible_exists (в cs/KolmogorovRoleLimit): на любом бюджете $n$ коротких программ конечно, поэтому какой-то объект неописуем в пределах $n$ — голубятня, 0 аксиом. ↩

2. VerifiedHuffman (huffman_synthesis): беспрефиксное дерево, равенство Крафта $\sum 2^{-l_i}=1$, конкретное tree_4_optimal со средней длиной $\frac{7}{4}$ для диадического $\{\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{8}\}$ (совпадает с его энтропией). Это беспрефиксная структура и конкретный пример, а не общая теорема оптимальности Хаффмана среди всех префиксных кодов. Информативность как мера снижения цены поиска — complexity/Informativeness. Машинно проверено, 0 аксиом. ↩

3. ObserverCompressor (observer_compressor_synthesis: измерение/коллапс как максимальное сжатие) и crown/CompressionIsPhysics (compression_is_physics_synthesis: сжатие как процесс того же типа — $N$ мод, спектр, энергия — что звук/свет/КМ). Структурное чтение и мост к Ландауэру (Глава 5) и Тому III, не полная термодинамическая модель сжатия. Машинно проверено, 0 аксиом. ↩

4. kolmogorov_role_limit_drawn и complexity_decidable_no_diagonal (в cs/KolmogorovRoleLimit): критерий сложности роль-предельно нарисован — при наличии самоотрицающей диагонали Берри/Чейтина нет тотального завершающегося решателя (экземпляр diagonal_defeats_decider); роль-предел, не запрет, и без заявки на инвариантность $K$ между машинами. Машинно проверено, 0 аксиом. ↩

5. one_boundary_four_faces (в cs/KolmogorovRoleLimit) расширяет one_boundary_three_faces: к дискриминанту, халтингу и Кантору добавляется $K$. Машинно проверено, 0 аксиом. ↩