Кривые Коха демонстрируют новое и весьма интересное сочетание простоты и сложности. На первый взгляд они выглядят гораздо более сложными, чем любая стандартная евклидова кривая. Однако теория математических алгоритмов Колмогорова-Чайтина утверждает обратное: кривая Коха ничуть не сложнее окружности! Эта теория оперирует некоторым набором «букв» или «атомных операций», причем длина кратчайшего известного алгоритма построения искомой функции принимается за объективный верхний предел сложности этой функции.

От англ. squiggle — «извилина, загогулина». — Прим. перев.

6 о Снежинки и другие кривые Коха

69

Попробуем применить вышеописанный подход к построению кривых. Условимся изображать буквы или «атомы» графического процесса прямыми «штрихами». При использовании такого алфавита построение правильного многоугольника требует конечного числа штрихов, каждый из которых можно описать с помощью конечного числа инструкций, и, как следствие, является задачей конечной сложности. В построении же окружности, напротив, участвует «бесконечное количество бесконечно коротких штрихов», и поэтому окружность представляется нам как кривая бесконечной сложности. Однако если производить построение окружности рекурсивно, можно видеть, что необходимо лишь конечное число инструкций, и значит построение окружности также является задачей конечной сложности. Начнем, например, с правильного многоугольника, число сторон которого равно 2т (т > 2), затем заменим каждый штрих длины 2sin(7r/2m) двумя штрихами длины 2 sin(7r/2m+1); далее процесс повторяется снова и снова. Для построения кривых Коха применяется тот же подход, но с использованием более простых операций: длину каждого штриха нужно всего лишь умножить на г, причем относительное расположение штрихов остается неизменным на протяжении всего построения. Отсюда и следует парадоксальное заявление: когда сложность определяется длиной лучшего на настоящий момент алгоритма, выраженного средствами данного алфавита, кривая Коха оказывается проще окружности.

Это необычное распределение кривых по относительной сложности их построения не следует принимать всерьез. Самое интересное, что, используя алфавит, основанный на окружности и линейке (т. е. взяв в качестве «атома» окружность), мы придем к противоположному выводу. И все же, при разумно подобранном алфавите, любая кривая Коха не только имеет конечную сложность, но оказывается проще большинства евклидовых кривых.