Новый ум короля: О компьютерах, мышлении и законах физики

Существуют также и другие подходы, которые могут использоваться с тем, чтобы обойти проблему несчетности комплексных чисел. Вместо того, чтобы рассматривать все вычислимые комплексные числа, можно ограничиться только подмножеством таких чисел, для любой пары которых можно вычислительным путем установить их равенство. Простым примером такого подмножества могут служить «рациональные»комплексные числа, у которых как мнимая, так и вещественная части могут быть представлены рациональными числами. Я не думаю, однако, что это дало бы многое в случае «усиков» множества Мандельброта, поскольку такая точка зрения накладывает очень значительные ограничения. Более удовлетворительным могло бы оказаться рассмотрение алгебраическихчисел — тех комплексных чисел, которые являются алгебраическими решениями уравнений с целыми коэффициентами. Например, все решения zуравнения

129z ⁷— ЗЗz ⁵+ 725z ⁴+ 16z ³— 2z— 3= 0

— это алгебраические числа. Такие числа будут счетными и вычислимыми, и задача проверки двух из них на равенство будет решатся путем прямого вычисления. (Как выясняется, многие из них будут лежать на границе единичного круга и «усиков» множества Мандельброта.) И мы можем по желанию рассматривать вопрос о рекурсивности множества Мандельброта в терминах этих чисел.

Возможно, что алгебраические числа оказались бы подходящим инструментом для двух обсуждаемых нами множеств, но они не снимают все наши трудности в общем случае. Пусть мы рассматриваем множество (темная область на рис. 4.5), определяемое неравенством

y>= e ^z,

где х+ iy(= z) — точка в плоскости Аргана.

Рис. 4.5.Множество, определенное экспоненциальным соотношением у>= е ^z, должно также рассматриваться как рекурсивное

Внутренняя часть множества, равно как и внутренняя часть его дополнения, будут рекурсивно нумеруемыми в соответствии с любой из вышеизложенных точек зрения, но (как следует из знаменитой теоремы Ф.Линдеманна, доказанной в 1882 году) граница, у= е ^х, содержит только одну алгебраическую точку, а именно точку z = i. В этом случае алгебраические числа никак не могут нам помочь при исследовании алгоритмической по своей природе границы!

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

Некоторые примеры нерекурсивной математики

Существует немало областей математики, где возникают проблемы нерекурсивного характера. Это означает, что мы можем сталкиваться с задачами, ответ к которым в каждом случае либо «да», либо «нет», но определить, какой из них верен, — нельзя из-за отсутствия соответствующего общего алгоритма. Некоторые из этих классов задач выглядят на удивление просто.

Например, рассмотрим задачу об отыскании целочисленных решений системы алгебраических уравнений с целыми коэффициентами. Эти уравнения известны под именем диофантовых(в честь греческого математика Диофанта, который жил в третьем веке до нашей эры и изучал уравнения такого типа). Подобные уравнения выглядят, например, как

z³- y — 1= 0,

yz ²— 2x— 2 = 0,

у ²— 2xz + z + 2 = 0,

и задача состоит в том, чтобы определить, могут ли они быть решены в целых x, y, z. Оказывается, что в этом конкретном случае существует тройка целых чисел, дающая решение этой системы:

х= 13, у= 7, 2= 2.

Но для произвольной системы диофантовых уравнений никакого алгоритма не существует [87]. Арифметика Диофанта, несмотря на простоту входящих в нее выражений, является частью неалгоритмической математики!