Математическая энциклопедия - конструктивный анализ

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

В соответствии с этими целями, исследования по К. а. можно грубо разделить на два типа: претендующие и не претендующие на достижение цели (1). Для исследований первого типа характерно либо использование нестандартных логик, либо существенные ограничения в употреблении традиционных логнче'ских и математических средств, в то время как в работах второго типа свободно используются традиционная математика и логика. Ко второму типу относятся основополагающие работы (см. [1]-[4]), в к-рых были выработаны современные концепции вычислимого действительного числа (см. также [5]-[12]). К первому типу относятся исследования по интуиционистскому анализу (см. Интуиционизм), возникшие в связи с выдвинутой Л.

Э. Я. Брауэром (L. E. J. Brower) интуиционистской программой построения математики и оказавшие существенное влияние на формирование задач и методов К. а., рекурсивный анализ Р. Л. Гудстейна (R. L. Соodstein, см. [12]), а также оригинальная и чрезвычайно далеко продвинутая система К. а., развитая Э. Бишопом (см. [13]). (Конструктивный анализ Бишопа занимает промежуточное положение между интуиционистским анализом и системами, использующими точные концепции алгоритма.

) Своеобразная трактовка К. а. (в частности, теории меры) была предложена в 1970 П. Мартином-Лёфом [14]. В СССР начиная с 50-х гг. в трудах А. А. Маркова, Н. А. Шанина и их учеников (см. [15], [16], [19]) интенсивно разрабатывалась система К. а., относящаяся к первому типу и укладывающаяся в рамки конструктивного направления в математике. Являясь частью конструктивной математики, эта система (за к-рой ниже для краткости закрепляется термин "К.

а.") сохраняет характерные черты последней. В частности, рассмотрения ограничиваются конструктивными объектами (чаще всего словами в нек-рых алфавитах или объектами, допускающими очевидное кодирование словами) и проводятся в рамках абст ракции потенциальной осуществимости с применением специальной конструктивной логики, вырабатываемой с учетом специфики конструктивных объектов как результатов потенциально выполнимых конечных построений.

При этом полностью исключается использование абстракции актуальной бесконечности, и интуитивное понятие "эффективности" связывается с одним из точных понятий алгоритма (в большинстве работ, относящихся к рассматриваемой системе К. а., используется понятие нормального алгорифма). В рамках К. а. получено большое число результатов, интересных как с точки зрения круга вопросов (1), так и с точки зрения круга вопросов (2). По существу показана возможность построения средствами конструктивной математики ряда теорий, таких, как теория элементарных функций, теория рядов, интегрирования по Римануи Лебегу, теория функций комплексного переменного, теория обобщенных функций и т.

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

Фундаментальными понятиями К.

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

Сначала вводятся натуральные числа как слова вида 0, 01,011, ... в двухбуквенном алфавите {01}. Аналогично определяются рациональные числа как слова нек-рого типа в алфавите Определяются отношения порядка и равенства над рациональными числами, а также арифметич. операции над ними. Конструктивной последовательностью натуральных чисел (к.

п. н. ч.) наз. (нормальный) алгорифм, перерабатывающий всякое натуральное число в натуральное число. Аналогичным образом трактуется понятие конструктивной последовательности рациональных чисел (к. п. р. ч.). Схемы нормальных алгорифмов однозначным образом кодируются словами в алфавите {01}; код данного алгорифма наз. его записью. К. п. н. ч. аназ. регулятором фундаментальности к. п. р. ч. Р, если для любых натуральных I, m, n таких, что l,выполняется неравенство |b(l)-b(m)|<2^-n. К. п. р. ч. наз. фундаментальной, если можно построить ее регулятор фундаментальности.

Конструктивными действительными числами (к. д. ч.) наз. рациональные числа, а также слова в алфавите вида (играет роль разделительного знака), где Uзапись некоторой к. п. р. ч., V запись к. п. н. ч., являющейся регулятором фундаментальности этой к. п. р. ч. Описанное понятие к. д. ч. (предложенное Н. А. Шаниным, см. [20], называвшим такие к.

д. ч. "FR-числами" или "дуплексами") хорошо согласуется с интуитивным представлением о вычислимых действительных числах как объектах, допускающих эффективную сколь угодно точную аппроксимацию рациональными числами. Для к. д. ч. можно определить естественным образом отношения порядка и равенства и арифметич. операции (причем последние задаются алгоритмами).

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

Относительно такого понятия сходимости система к. д. ч. оказывается полной: существует алгоритм, находящий, исходя из записи всякой фундаментальной к. п. д. ч. g. и записи ее регулятора фундаментальности, такое к. д. ч., к к-рому (конструктивно) сходится g(теорема о полноте системы к. д. ч.). Методом, аналогичным канторовскому, можно доказать также теорему о конструктивной несчетности множества всех к. д. ч.: осуществим алгоритм, перерабатывающий запись всякой к. п. д. ч. в к. д. ч., отличное (в смысле равенства к. д. ч.) от всех членов этой к. п. д. ч. Теорема о полноте придает значительное сходство конструктивной и классич.

теориям пределов, особенно сильно проявляющееся в вопросах сходимости тех или иных конкретных используемых в анализе последовательностей и рядов. Вместе с тем здесь имеются и существенные отличия, проявляющиеся, напр., в следующем результате Э. Шпеккера (см. [4]): можно построить возрастающую к. п. р. ч. b такую, что всегда 0<b(n)<1 и, несмотря на это, b не является фундаментальной (и, следовательно, не сходится (конструктивно) ни к какому к.

д. ч.). Кроме того, из b нельзя выбрать сходящейся (конструктивной) подпоследовательности, и множество значений b не имеет в конструктивном континууме точной верхней границы. Другим напрашивающимся способом введения к. д. ч. является конструктивизация понятия систематической дроби в той или иной системе счисления. Именно, конструктивной m-ичной дробью (m>1) наз. (нормальный) алгорифм a. такой, что a(0) есть целое число и a(i) при i>0 есть натуральное число, причем (с m-ичной дробью a. связывается к. п. р. ч. Несмотря на простоту такого понятия к. д. ч., оно не получило распространения, поскольку обладает рядом существенных неудобств: напр., не сохраняется теорема о полноте и невозможен алгорифм, осуществляющий сложение любых двух m-ичных дробей.

.