Колмогоров: случайно — значит несжимаемо

В 1933 году Колмогоров дал теории вероятностей аксиомы и закрыл вопрос, стоявший тридцать лет. Одного он при этом не сделал намеренно: не сказал, что такое случайный объект. Через тридцать два года вернулся и сказал.

Чего нельзя спросить у аксиом

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

Между тем в аксиоматике 1933 года у обеих последовательностей ровно одна и та же вероятность $2^{-24}$, и различить их теория не может ничем. И не должна: она говорит о вероятности события, то есть множества исходов, а «эта конкретная строка случайна» — вообще не событие.

Значит, определять надо не через вероятность. А через что?

Определение

Колмогоров предлагает мерить не вероятность, а длину описания.

Пусть выбран какой-то способ описывать двоичные слова программами — скажем, язык $A$. Сложностью слова $x$ называется длина самой короткой программы, которая печатает $x$ и останавливается:

$$K_A(x) \;=\; \min\{\, |p| \;:\; A(p) = x \,\}.$$

Слово из миллиона нулей описывается строчкой «напечатать 0 миллион раз» — сложность его мала. У слова, полученного бросанием монеты, короткой программы, как правило, нет, и программа вынуждена содержать это слово целиком.

Слово случайно, если его сложность близка к его длине: $K(x) \geqslant |x| - c$.

Почему это не зависит от языка

Первое возражение очевидно: языков много, сложность у каждого своя. Ответ — теорема инвариантности, и она проще, чем кажется. Пусть $B$ — другой язык. Напишем на $A$ переводчик с $B$: программу фиксированной длины $c_{AB}$, которая принимает текст на $B$ и исполняет его. Тогда всякая программа для $B$ годится и для $A$ ценой этой добавки:

$$K_A(x) \;\leqslant\; K_B(x) + c_{AB}.$$

Языки расходятся в оценке сложности не более чем на константу, от $x$ не зависящую; для длинных слов это ничто. Язык, у которого такая добавка работает против всех остальных, называется универсальным, и его существование — это в точности универсальная машина Тьюринга.

Почти всё несжимаемо: доказательство в две строки

Сколько всего слов длины $n$? Ровно $2^n$. Сколько существует программ короче, чем $n-c$? Не больше, чем всех двоичных строк такой длины:

$$1 + 2 + 4 + \dots + 2^{\,n-c-1} \;=\; 2^{\,n-c} - 1 .$$

Каждая программа печатает не более одного слова. Значит, слов длины $n$ со сложностью меньше $n-c$ тоже меньше, чем $2^{\,n-c}$, а доля их среди всех слов —

$$\frac{2^{\,n-c}}{2^{\,n}} \;=\; 2^{-c}.$$

При $c = 10$ это меньше одной тысячной. Сжимаемых слов исчезающе мало; почти всякое слово случайно. Тем же счётом доказывается, что архиватора, сжимающего всякий файл хотя бы на один бит, не существует.

Цена: сложность нельзя вычислить

Определение есть — а вот проверки нет, и это тоже теорема.

Рассуждение — вариант парадокса Берри: «наименьшее натуральное число, которое нельзя описать по-русски менее чем двадцатью словами». Мы его только что описали, потратив одиннадцать.

Формально. Пусть существует программа $S$ длины $s$, вычисляющая $K$. Напишем тогда программу: «перебирай слова подряд, для каждого вычисляй $K$ и напечатай первое, у которого $K(x) > m$». Её длина — это $s$ плюс запись числа $m$, то есть примерно $s + \log_2 m$. Она печатает слово сложности больше $m$, а сама короче $m$ при достаточно большом $m$. Противоречие: значит, $S$ не существует.

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

Три подхода

Статья 1965 года называется «Три подхода к определению понятия „количество информации“» и перечисляет их прямо:

• комбинаторный — информации столько, сколько нужно бит, чтобы указать объект среди $N$ возможных: $\log_2 N$;
• вероятностный — энтропия Шеннона, мера неопределённости источника;
• алгоритмический — сложность, только что определённая.

Разница между вторым и третьим — главная. Энтропия ШеннонаКлод Шеннонамериканский математик и инженер · 1916–2001В магистерской работе связал булеву алгебру с электрическими схемами, а через одиннадцать лет измерил информацию в битах — и создал предмет, которого до него не было. есть свойство источника: чтобы её посчитать, нужно распределение. Сложность есть свойство отдельного объекта: никакого распределения не требуется. Шеннон отвечает на вопрос «сколько информации даёт в среднем этот источник», Колмогоров — «сколько информации вот в этом тексте».

Откуда взялся вопрос и кто был первым

Двумя годами раньше вышла заметка «О таблицах случайных чисел» (1963), где задача поставлена в самой прикладной форме: статистику выдают таблицу и уверяют, что она случайная, — что это значит? Мизес и Борель говорили о бесконечных последовательностях, а таблица конечна, и в их смысле всякая конечная таблица не случайна и не неслучайна. Сложность годится и для конечного — в этом её главная практическая сила.

Есть и совсем конкретный повод. В начале 1960-х Колмогоров считал информацию в русском стихе — и упёрся в то же самое неудобство: шенноновская мера говорит об источнике, а «Евгений Онегин» существует в одном экземпляре. Понятие, годное для единственного объекта, понадобилось ему по делу.

Приоритет принадлежит не ему. К тому же понятию несколькими годами раньше пришёл Рэй Соломонов (1960, 1964), искавший не определение случайности, а формализацию индукции: как машина должна угадывать продолжение ряда. Колмогоров, узнав о его работе, ссылался на неё сам. Третьим и независимо к тому же пришёл Грегори Чейтин, тогда ещё студент.

Что это дало

Определение оказалось не только ответом на старый вопрос, но и рабочим инструментом. Из него выросли метод несжимаемости в комбинаторике (доказательство идёт так: если бы объекта с нужным свойством не было, все объекты сжимались бы, а это невозможно), меры расстояния между текстами и геномами, оценки в теории сложности вычислений.

Через год Мартин-Лёф получит тот же класс последовательностей совсем с другой стороны — через статистические проверки, и совпадение двух независимых определений будет лучшим доводом в пользу того, что понятие поймано правильно.

А главное — вопрос перевернулся. Случайность перестала быть свойством мира и стала свойством описания. Спрашивать «случайна ли эта последовательность на самом деле» стало примерно так же осмысленно, как спрашивать, длинная ли она: смотря чем мерить. Мерить теперь есть чем.