Является ли множество Мандельброта рекурсивным?
Существенной характеристикой нерекурсивных множеств является их сложноорганизованность. Это свойство должно, в некотором смысле, препятствовать любым попыткам систематизации, которая, в противном случае, привела бы к некоторой «работающей» алгоритмической процедуре. Для нерекурсивного множества не существует общего алгоритмического пути к решению вопроса о принадлежности ему произвольного элемента (или «точки»), В начале третьей главы мы встретились с неким чрезвычайно сложно выглядящим множеством — с множеством Мандельброта. Хотя правила, по которым оно строится, поразительно просты, само множество представляет собой бесконечное разнообразие в высшей степени замысловатых структур. Может ли это быть примером настоящего нерекурсивного множества, явленного глазам смертных?
Читателю, однако, не понадобится много времени, чтобы сообразить, что эта парадигма сложности была создана специально для наших глаз волшебством вычислительных технологий с использованием современных быстродействующих компьютеров. А не являются ли компьютеры истинным воплощением алгоритмических действий? Конечно, это так, но все же мы должны принимать во внимание способ, с помощью которого компьютеры, в действительности, создают эти картинки. Чтобы проверить, принадлежит точка плоскости Аргана — комплексное число с — множеству Мандельброта (закрашено черным) или его дополнению (светлая область), компьютер, начиная с нуля, применит отображение
z → z 2 + с
сначала к z = 0 , чтобы получить с ; потом к z = с , чтобы получить с 2 + с ; затем к z = с 2 + с , чтобы получить с 4 + 2с 3 + с 2 + с ; и так далее. Если эта последовательность 0 , с , с 2 + с , с 4 + 2с 3 + с 2 + с … остается ограниченной, то соответствующая точка с будет черной; в противном случае — белой. Как машина определяет, что такая последовательность остается ограниченной? В принципе, этот вопрос предполагает наличие информации о том, что происходит после бесконечного числа ее элементов! Сама по себе эта задача вычислительными методами не решается. К счастью, существуют способы предсказать исходя уже из конечного числа членов, когда последовательность станет неограниченной. (На самом деле, если последовательность достигает окружности радиуса 1 + √2 с центром в начале координат, можно с уверенностью сказать, что она будет неограниченной.)
Таким образом, дополнение к множеству Мандельброта является, в некотором смысле, рекурсивно нумеруемым. Если комплексное число с расположено в светлой области, то существует алгоритм, подтверждающий этот факт. А как насчет самого множества Мандельброта — темного участка рисунка? Существует ли алгоритм, способный точно установить, что точка, принадлежащая предположительно темному участку, действительно ему принадлежит? Ответ на этот вопрос в настоящее время, похоже, отсутствует [85]. Я справлялся у многих коллег и экспертов, но ни один из них не слышал о подобном алгоритме. Равно как и никто из них не сталкивался с указанием на то, что такого алгоритма не существует. По крайней мере, насколько можно об этом судить, алгоритм для темной области на сегодняшний день неизвестен. Возможно, множество, дополнительное по отношению к множеству Мандельброта, действительно является примером рекурсивно нумеруемого, но не рекурсивного множества!
85
Недавно я узнал от Леоноры Блюм, что (заинтересовавшись моими комментариями в первом издании этой книги) она установила, что множество Мандельброта (и его дополнение) на самом деле являются, как я и предполагал, нерекурсивными в том смысле, который описан в десятом примечании.