Наша математическая вселенная - [132]

Давайте разберёмся с этим.

Иллюзия сложности

Сколько информации действительно содержит наша Вселенная? Информационное содержание (алгоритмическая сложность) чего-либо — это длина в битах его самого краткого самодостаточного описания. Чтобы оценить тонкость этого вопроса, сначала разберёмся, сколько информации содержит каждый из шести паттернов на рис. 12.7. На первый взгляд, два паттерна слева очень похожи. Это внешне случайные наборы 128 × 128 = 16 384 чёрных и белых пикселов. Можно предположить, что для описания каждого нужно около 16 384 битов — по одному биту для цвета каждого пиксела. Но хотя это верно для верхнего паттерна, который я построил с помощью квантового генератора случайных чисел, в нижнем есть скрытая простота: это просто двоичные цифры квадратного корня из двух. Этого простого описания достаточно для вычисления всего паттерна √2 ≈ 1,414 213 562…, что в двоичной системе счисления записывается как 1,0 100 001 010 000 110… Условно примем, что эту последовательность из 0 и 1 можно сгенерировать компьютерной программой длиной 100 битов. Тогда видимая сложность нижнего левого рисунка оказывается иллюзией: мы видим не 16 384 бита информации, а никак не более 100.

Рис. 12.7. Сложность паттерна (сколько битов информации нужно для его описания) не всегда очевидна. Слева вверху 128 × 128 = 16 384 квадрата, которые случайным образом окрашены в чёрный или белый цвет, что обычно нельзя описать, используя менее 16 384 битов. Маленькие фрагменты этого паттерна (вверху посередине и справа) состоят из меньшего числа случайным образом окрашенных квадратов, а значит, их описание требует меньше битов. С другой стороны, нижний левый узор может быть сгенерирован очень короткой (скажем, 100-битовой) программой, поскольку это просто двоичные цифры числа √2 (0 = чёрный квадрат, 1 = белый). Для описания нижнего среднего квадрата потребуется задать дополнительных 14 битов, указывающих, какие цифры числа √2 в нём используются. Наконец, для правого нижнего рисунка потребуется 9 битов — столько же, сколько и для рисунка над ним. Этот паттерн настолько мал, что здесь не поможет знание того, что это часть √2.

Дело ещё сильнее запутывается, когда доходит до информационного содержания малых частей. В верхнем ряду на рис. 12.7 всё обстоит так, как можно ожидать: чем меньше паттерн, тем он проще и тем меньше информации требуется для его описания — нам нужно по 1 биту для описания чёрного или белого пиксела. Но в нижнем ряду мы видим прямо противоположный пример. Здесь меньшее становится большим в том смысле, что средний паттерн сложнее левого, его описание требует больше битов. Теперь недостаточно просто сказать, что это двоичные цифры √2: следует также указать, с каких цифр начинается паттерн, а на это в данном случае потребуется ещё 14 битов. Короче говоря, целое может содержать меньше информации, чем сумма его частей, а иногда даже меньше, чем одна часть.

Наконец, описание двух крайних справа паттернов на рис. 12.7 требует по 9 битов. Мы знаем, что правый нижний паттерн спрятан среди 16 384 цифр √2, но для такого маленького паттерна это знание уже неинтересно и бесполезно: существует лишь 2⁹ = 512 возможных паттернов длиной 9, так что данный узор прячется в большинстве случайно выглядящих строк из тысячи 0 и 1.

На рис. 12.8 изображена красивая математическая структура, известная как множество (фрактал) Мандельброта. Она обладает тем замечательным свойством, что сложные паттерны существуют в ней на сколь угодно малых масштабах, и хотя многие из них кажутся похожими, повторяющихся среди них нет. Насколько сложны два приведённых изображения? Каждое содержит около 1 млн пикселов, которые, в свою очередь, представляются 3 байтами информации[86] (байт равен 8 битам), а значит, для описания каждого изображения требуется несколько мегабайт. Однако левое изображение можно вычислить с помощью программы длиной всего в несколько сотен байтов, многократно выполняющей простое вычисление z² + c.

Правое изображение тоже простое, поскольку является крошечной частью левого. При этом оно немного сложнее: чтобы указать 20-значный номер одной из 10²⁰ частей, дополнительно требуется 8 байтов информации. Так что вновь меньшее становится большим в том смысле, что видимое информационное содержание увеличивается, когда мы ограничиваем своё внимание малой частью целого, теряя симметрию и простоту, характерные для совокупности частей. А вот ещё более простой пример: алгоритмическое информационное содержание произвольного числа, записываемого триллионом цифр, существенно, поскольку кратчайшая программа, печатающая это число, не может быть чем-то гораздо лучшим, чем просто записью всего триллиона цифр. Однако список всех чисел 1, 2, 3, … может быть сгенерирован совершенно тривиальной компьютерной программой, так что сложность множества меньше сложности типичного его члена.

Рис. 12.8. Несмотря на миллионы искусно раскрашенных пикселов, множество Мандельброта (слева) имеет очень простое описание: точки на рисунке соответствуют тому, что математики обозначают комплексным числом