КОНСТРУКТИВНЫЙ АНАЛИЗ, рекурсивный анализ, вычислимый анализ

— название, объединяющее различные течения в основаниях математики и математическом анализе. Как правило, при построении К. а. преследуются все или некоторые из следующих принципиальных целей: 1) построение системы анализа, спец. ориентированной на реальные конструктивные и вычислительные возможности (часто отступающие на второй план при традиционном теоретикомножественном построении анализа); 2) изучение принципиальных границ вычислительных возможностей в анализе, изучение «эффективности» в анализе (в частности, исследование вопроса о том, по каким исходным данным можно эффективно находить те или иные объекты анализа); 3) изучение вычислимых объектов анализа (вычислимых действительных чисел, вычислимых функций над ними и т. п.) самих по себе в том смысле, в котором, напр., в алгебре изучаются группы.

Имеющиеся здесь исследования можно очень грубо разделить на два типа: проводимые в рамках традиционного анализа и формально независимые от него. Первое направление представлено рядом работ, в том числе основополагающими работами А. Тьюринга, С. Банаха и С. Мазура, Э. Шпекера, в которых были, по существу, выработаны современные концепции вычислимого действительного числа. Ко второму типу относятся исследования по интуиционистскому анализу, возникшие в связи с выдвинутой Л. Брауэром интуиционистской программой построения математики и оказавшие существенное влияние на формирование задач и методов К. а., рекурсивный

анализ Р. Гудстейна, а также оригинальная и далеко продвинутая система К. а., развитая в последнее время Е. Бишопом. В Советском Союзе, начиная с 50-х годов, интенсивно разрабатывалась система К. а., относящаяся ко второму типу и являющаяся частью общей программы конструктивного построения математики (см. Конструктивное направление в математике). Основополагающий вклад в развитие этой системы (для краткости ее наз. «конструктивный анализ») внесли А. А. Марков, Н. А. Шанин и их ученики. Являясь частью конструктивной математики, К. а. сохраняет характерные черты последней. В частности, рассмотрения ограничиваются конструктивными объектами (чаще всего словами в некоторых алфавитах или объектами, допускающими очевидное кодирование словами) и проводятся в рамках абстракции потенциальной осуществимости с применением спец. конструктивных правил понимания матем. суждений. При этом полностью исключается использование абстракции актуальной бесконечности и интуитивное понятие «эффективности» связывается с одним из точных понятий алгоритма (в большинстве работ, относящихся к рассматриваемой системе К. а., используется понятие нормального алгоритма).

В рамках К. а. получено большое число результатов, интересных как с точки зрения проблематики цели 1-й, так и с точки зрения целей 2-й и 3-й. По существу показана возможность построения средствами конструктивной математики ряда теорий, таких как теория рядов, интегрирования по Риману и Лебегу, теория функций комплексного переменного, теория обобщенных функций и т. п. Получающиеся конструктивные теории обладают, наряду со сходством с одноименными традиционными теориями, и заметными отличиями от них, впрочем отличия эти проявляются не столько в конкретных вопросах, связанных с приложениями анализа, сколько в теор. концепциях (таких, напр., как концепция компактности и т. д.). Фундаментальными понятиями К. а. являются понятия конструктивного действительного числа (КДЧ) и конструктивной функции действительной переменной. Конструктивные действительные числа можно ввести различными (не всегда эквивалентными) способами. Одним из естественных путей является следующий путь, аналогичный канторовскому построению действительных чисел в традиционном анализе. Сначала вводятся натуральные числа, как слова в двухбуквенном алфавите вида . Аналогично определяются рациональные числа, как слова некоторого типа в алфавите Определяются отношения порядка и равенства над рациональными числами, а также арифм. операции над ними. Конструктивной последовательностью натуральных чисел нормальный алгоритм, перерабатывающий всякое натуральное число в [туральпое число. Аналогичным образом трактуется понятие конструктивной последовательности рациональных чисел (КПРЧ). Схемы нормальных алгоритмов однозначным образом кодируются словами в алфавите код данного алгоритма наз. его записью. КПНЧ а наз. регулятором фундаментальности КПРЧ Р, если для любых натуральных таких, что выполняется неравенство КПРЧ наз. фундаментальной, если можно построить ее регулятор фундаментальности. Конструктивными действительными числами рациональные числа, а также слова в алфавите вида где U — запись некоторой КПРЧ, V — запись КПНЧ, являющейся регулятором фундаментальности этой КПРЧ. Описанное понятие КДЧ хорошо согласуется с интуитивным представлением о вычислимых действительных числах как объектах, допускающих эффективную сколь угодно точную аппроксимацию рациональными числами. Для КДЧ можно определить естественным образом отношения порядка и равенства и арифм. операции (причем, последние задаются алгоритмами). Система КДЧ с этими отношениями равенства и порядка и арифм. операциями оказывается полем. Далее можно ввести в рассмотрение конструктивные последовательности КДЧ (КПДЧ) и определить в том же порядке идей, что и выше, понятие фундаментальной КПДЧ и понятие конструктивной сходимости КПДЧ к данному КДЧ. Относительно такого понятия сходимости система КДЧ оказывается полной: существует алгоритм, находящий, исходя из записи всякой фундаментальной КПДЧ у и записи ее регулятора фундаментальности, КДЧ, к которому (конструктивно) сходится у. Методом, аналогичным канторовскому, можно доказать также теорему о конструктивной несчетности множества всех КДЧ, состоящую в том, что осуществим алгоритм, перерабатывающий запись всякой КПДЧ в КДЧ, отличное (в смысле равенства КДЧ) от всех членов этой КПДЧ. Теорема о полноте придает значительное сходство конструктивной и классической теории пределов, особенно сильно проявляющееся в вопросах сходимости тех или иных конкретных, используемых а анализе, последовательностей и рядов. Но здесь имеются и существенные отличия, проявляющиеся, напр., в следующем результате Э. Шпекера: можно построить возрастающую КПРЧ Р такую, что всегда и, несмотря на это, не является фундаментальной следовательно, не сходится (конструктивно) ни к какому КДЧ).

Понятие конструктивной функции (КФ) является естественным уточнением интуитивного понятия точечной вычислимой функции над вычислимыми действительными числами. Конструктивной функцией (одной действительной переменной) наз. нормальный алгоритм такой, что для любых равных КДЧ х и у, если F применим к то F применим к у и равные КДЧ. В терминах КФ могут быть введены элементарные функции (показательная функция, тригонометрические функции и т. д.), обладающие обычными свойствами; для КФ могут быть развиты теории дифференцирования

интегрирования по Риману и т. д., близкие к традиционным. Вместе с тем, возможны и необычные с традиционной точки зрения функции: напр., существует всюду определенная КФ, непрерывная на единичном сегменте и неограниченная на нем. Не имеет аналогов в традиционном анализе и теорема, согласно которой всякая КФ конструктивно непрерывна в любой точке, в которой она определена.

Система понятий и методы К. а., позволяя существенно продвинуться с точки зрения цели 1-й, оказались также удобными для выявления вычислительных связей в анализе, поскольку многие теоремы К. а. являются либо утверждениями об осуществимости алгоритмов, строящих некоторые конструктивные объекты по тем или иным исходным данным, либо утверждениями, что такие алгоритмы невозможны. Установлена неразрешимость большого числа естественных массовых проблем анализа. Результаты этого типа (совершенно отсутствующие в курсах традиционного анализа) имеют теор. и практич. ценность, т. к. они выявляют потенциальные вычислительные тупики и способствуют четкому уяснению принципиальных границ вычислительных возможностей. Напр., доказана невозможность следующих алгоритмов (в смысле одного из точных понятий алгоритма): 1) распознающего для произвольного конструктивного действительного числа (КДЧ), равно оно нулю или нет; 2) находящего для каждой сходящейся конструктивной последовательности рациональных чисел то КДЧ, к которому она сходится; 3) находящего для каждой совместной системы линейных уравнений (над полем КДЧ) какое-нибудь ее решение; 4) находящего для каждой непрерывной, кусочно-линейной, знакопеременной функция корень этой функции; 5) находящего для всякой непрерывной, кусочно-линейной на единичном сегменте функции ее интеграл Римана по этому сегменту. Теоремы невозможности алгоритмов часто сопровождаются в К. а. теоремами о существовании алгоритмов, решающих рассматриваемые задачи по более полным исходным данным (сравните теорему о полноте КДЧ и 2-й пример) или с произвольной, наперед заданной точностью (напр., можно построить алгоритм, находящий для каждой всюду определенной знакопеременной конструктивной функции f и каждого n КДЧ так, что . Сопоставление таких результатов позволяет в ряде ситуаций получить представление о том, как можно корректно ставить ту или иную алгоритм. проблему.

Лит.: «Труды Математического института им. В. А. Стеклова АН СССР», 1958, т. 52; 1962, т. 67; 1964, т. 72; 1967, т. 93; Вейль Г. О философии математики. Пер. с нем. М.- Л., 1934; Turing А. М. On computable numbers, with an application to the Entscheidungs problem. «Proceedings of the London Mathematical Society», 1936, series 2, v. 42, part 3; Turing A. M. A correction. «Proceedings of the London Mathematical Society», 1937, series 2, v. 43; Specker E. Nicht Konstruktiv beweisbare Satze der Analysis. «The Journal of symbolic logic», 1949, v. 14, № 3; Mazur S. Computable analysis. «Rozprawy matematyczne» [Warszawa], 1963, t. 33 [библиогр. с. 109—110]; Гудстейн P. Л. Рекурсивный математический анализ. Пер. с англ. М., 1970; Кушнер Б. А. Лекции по конструктивному математическому анализу. М.. 1973 [библиогр. с. 427—440].

Б. А. Кушнер.