Существуют также и другие подходы, которые могут использоваться с тем, чтобы обойти проблему несчетности комплексных чисел. Вместо того, чтобы рассматривать все вычислимые комплексные числа, можно ограничиться только подмножеством таких чисел, для любой пары которых можно вычислительным путем установить их равенство. Простым примером такого подмножества могут служить «рациональные» комплексные числа, у которых как мнимая, так и вещественная части могут быть представлены рациональными числами. Я не думаю, однако, что это дало бы многое в случае «усиков» множества Мандельброта, поскольку такая точка зрения накладывает очень значительные ограничения. Более удовлетворительным могло бы оказаться рассмотрение алгебраических чисел — тех комплексных чисел, которые являются алгебраическими решениями уравнений с целыми коэффициентами. Например, все решения z уравнения
129z 7— ЗЗz 5+ 725z 4+ 16z 3— 2z— 3= 0
—это алгебраические числа. Такие числа будут счетными и вычислимыми, и задача проверки двух из них на равенство будет решатся путем прямого вычисления. (Как выясняется, многие из них будут лежать на границе единичного круга и «усиков» множества Мандельброта.) И мы можем по желанию рассматривать вопрос о рекурсивности множества Мандельброта в терминах этих чисел.
Возможно, что алгебраические числа оказались бы подходящим инструментом для двух обсуждаемых нами множеств, но они не снимают все наши трудности в общем случае. Пусть мы рассматриваем множество (темная область на рис.4.5), определяемое неравенством
y≥ e z,
где х+ iy(= z)— точка в плоскости Аргана.
Рис.4.5. Множество, определенное экспоненциальным соотношением у≥ е z, должно также рассматриваться как рекурсивное
Внутренняя часть множества, равно как и внутренняя часть его дополнения, будут рекурсивно нумеруемыми в соответствии с любой из вышеизложенных точек зрения, но (как следует из знаменитой теоремы Ф.Линдеманна, доказанной в 1882 году) граница, у= е х, содержит только одну алгебраическую точку, а именно точку z= i. В этом случае алгебраические числа никак не могут нам помочь при исследовании алгоритмической по своей природе границы!
Несложно определить другой подкласс вычислимых чисел, которые будут подходить в данном конкретном случае, но при этом все равно останется ощущение, что правильный подход нами до сих пор так и не был найден.
Некоторые примеры нерекурсивной математики
Существует немало областей математики, где возникают проблемы нерекурсивного характера. Это означает, что мы можем сталкиваться с задачами, ответ к которым в каждом случае либо «да», либо «нет», но определить, какой из них верен,— нельзя из-за отсутствия соответствующего общего алгоритма. Некоторые из этих классов задач выглядят на удивление просто.
Например, рассмотрим задачу об отыскании целочисленных решений системы алгебраических уравнений с целыми коэффициентами. Эти уравнения известны под именем диофантовых(в честь греческого математика Диофанта, который жил в третьем веке до нашей эры и изучал уравнения такого типа). Подобные уравнения выглядят, например, как
z3- y — 1= 0,
yz 2— 2x— 2 = 0,
у 2— 2xz +z + 2 = 0,
и задача состоит в том, чтобы определить, могут ли они быть решены в целых x, y, z. Оказывается, что в этом конкретном случае существует тройка целых чисел, дающая решение этой системы:
х= 13, у= 7, 2= 2.
Но для произвольной системы диофантовых уравнений никакого алгоритма не существует [87]. Арифметика Диофанта, несмотря на простоту входящих в нее выражений, является частью неалгоритмической математики!
(Несколько менее тривиальным является пример топологической эквивалентности многообразий. Я упоминаю об этом только вкратце, ибо в главе 8 будут рассматриваться вопросы, имеющие к данному определенное отношение. Чтобы понять, что такое «многообразие», представьте для начала петлю, которая является многообразием в одном измерении; затем представьте замкнутую поверхность — многообразие в двух измерениях. Далее попробуйте представить некую «поверхность», имеющую три и более измерений. «Топологическая эквивалентность» двух многообразий означает, что одно из них может быть деформировано в другое путем непрерывных преобразований — без разрывов и склеек. Так, сфера и поверхность куба являются топологически эквивалентными, хотя они не эквивалентны поверхности кольца или чашки с ручкой — хотя последние топологически эквивалентны друг другу. При этом для двумерных многообразий существует алгоритм, позволяющий определить, эквивалентны ли произвольные два многообразия друг другу или нет — в сущности, заключающийся в подсчете «ручек», которые имеет каждая из поверхностей. Для случая трех измерений вопрос о существовании такого алгоритма на момент написания книги остается без ответа; однако для четырех и более измерений уже известно, что такого алгоритма быть не может. Возможно, четырехмерный случай имеет некое отношение к физике, поскольку согласно теории общей относительности Эйнштейна пространство и время совместно образуют четырехмерное многообразие (см. главу 5, «Специальная теория относительности Эйнштейна и Пуанкаре»). Герох и Хартли в 1986 году высказали предположение о том, что свойство неалгоритмичности может иметь отношение к «квантовой гравитации» (см. также главу 8).)
Давайте теперь рассмотрим иной тип задач, называемых задачами со словами[88]. Допустим, у нас есть некий алфавит символов, и мы рассматриваем различные строки этих символов, трактуя их как слова. Слова могут сами по себе не иметь никакого значения, но мы должны иметь некоторый (конечный) список «равенств» между ними, которые мы сможем использовать для дальнейшего построения таких «равенств». Это делается путем подстановки слов из исходного списка в другие (как правило, более длинные) слова, которые содержат их в виде составных частей. Каждая такая часть может быть заменена на равную ей в соответствии с используемым списком. Тогда для любой данной пары слов мы должны решить задачу об их равенстве согласно этим правилам.
В качестве примера мы можем взять для нашего исходного списка, скажем, такие равенства:
EAT = АТ
АТЕ = А
LATER = LOW
PAN = PILLOW
CARP = ME.
Отсюда мы можем, например, вывести
LAP = LEAP,
используя последовательные замены из второго, первого и снова второго соотношения из нашего исходного листа:
LAP = LATEP = LEATEP = LEAP.
Проблема теперь заключается в том, чтобы выяснить, сможем ли мы для любой наперед заданной пары слов осуществить вышеописанным образом переход от одного из них к другому? Можем мы перейти от CATERPILLAR к MAN, или, скажем, от CARPET — к MEAT? Ответ в первом случае оказывается утвердительным, тогда как во втором — отрицательным. Когда ответ утвердителен, стандартный путь показать его справедливость заключается в построении цепочки равенств, где каждое из слов получается из предыдущего с учетом допустимых соотношений. Итак, имеем (обозначая буквы, назначенные к замене, жирным шрифтом, а только что измененные — курсивом):
Как мы можем утверждать, что посредством разрешенных подстановок невозможно получить MEAT из CARPET? Для демонстрации этого факта придется подумать чуть больше, однако показать это не так уж сложно, причем множеством разных способов. Простейшим представляется следующий: в каждом «равенстве» из нашего списка число букв А плюс число букв W плюс число букв М с каждой стороны одинаково. Значит, общая сумма указанных букв не может меняться в процессе преобразования по допустимым нашим списком правилам. Однако, для CARPET эта сумма равна 1, а для MEAT— 2. Следовательно, не существует способа получить из первого слова второе при помощи вышеприведенного списка равенств.
Заметьте, что когда два слова «равны», мы можем показать это, просто приведя допустимую формальную строчку символов, построенную с помощью заданных нами правил; тогда как в случае их «неравенства» мы должны прибегать к рассуждениям об этих самых правилах. Существует четкий алгоритм, который мы можем использовать для установления «равенства» между двумя словами в том случае, когда они действительно «равны». Все, что нам требуется, это составить лексикографический перечень всех возможных последовательностей слов, и потом вычеркнуть из этого списка любую строчку, где имеется пара слов, в которой последующее нельзя получить из предыдущего при помощи какого бы то ни было правила из исходного списка. Оставшиеся последовательности дадут нам набор всех искомых «равенств» между словами. Однако, в общем случае нет такого явного алгоритма для случая, когда два слова «неравны», и нам, возможно, пришлось бы применить «интеллект» для установления этого факта. (Конечно же, мне потребовалось некоторое время, прежде чем я заметил описанный выше «трюк», при помощи которого доказал, что CARPET и MEAT«неравны». А для другого примера «трюк» мог бы понадобиться совершенно иной. Кстати, интеллект помогает — хотя и не обязательно — и в случае, когда необходимо установить существование некоторого «равенства».)
В действительности, для нашего конкретного списка из пяти «равенств», которые составляют исходный список в рассмотренном выше примере, привести алгоритм, устанавливающий «неравенство» в случае, когда два слова и вправду «неравны» — не так уж сложно. Однако, чтобы