Конструктивный Анализ

Рекурсивный анализ, вычислимый анализ,- название, объединяющее различные течения в основаниях математики и математич. анализе. При развитии К. а., как правило, преследуются обе или вторая из следующих двух принципиальных целей: (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, ... в двухбуквенном алфавите . Аналогично определяются рациональные числа как слова нек-рого типа в алфавите Определяются отношения порядка и равенства над рациональными числами, а также арифметич. операции над ними. Конструктивной последовательностью натуральных чисел (к. п. н. ч.) наз. (нормальный) алгорифм, перерабатывающий всякое натуральное число в натуральное число. Аналогичным образом трактуется понятие конструктивной последовательности рациональных чисел (к. п. р. ч.). Схемы нормальных алгорифмов однозначным образом кодируются словами в алфавите ; код данного алгорифма наз. его записью. К. п. н. ч. аназ. регулятором фундаментальности к. п. р. ч. Р, если для любых натуральных 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-ичных дробей. Понятие конструктивной функции (к. ф.) является естественным уточнением интуитивного понятия точечной вычислимой функции над вычислимыми действительными числами. Конструктивной функцией (одной действительной переменной) наз. (нормальный) алгорифм Fтакой, что для любых равных к. д. ч. хи у, если Fприменим к х, то Fприменим к у и F(x), F(y)суть равные к. д. ч. В терминах к. ф. могут быть введены элементарные функции (показательная функция, тригонометрия, функции и др.), обладающие обычными свойствами; для конструктивных функций могут быть развиты теории дифференцирования, интегрирования по Риману и т. д., близкие к традиционным. Вместе с тем возможны и необычные с традиционной точки зрения функции: напр., построена к. ф., всюду определенная, непрерывная на единичном сегменте и не ограниченная на нем (см. [17]). Не имеет аналогов в традиционном анализе и теорема, согласно к-рой всякая к. ф. конструктивно непрерывна в любой точке, в к-рой она определена (см. [18]). Система понятий и методы К. а., позволяя существенно продвинуться с точки зрения цели (1), оказались также удобными для выявления вычислительных связей в анализе, поскольку многие теоремы К. а. являются либо утверждениями об осуществимости алгоритмов, строящих нек-рые конструктивные объекты по тем пли иным исходным данным, либо утверждениями, что такие алгоритмы невозможны. В настоящее время (к 1978) установлена неразрешимость большого числа естественных массовых проблем анализа. Результаты этого типа (совершенно отсутствующие в курсах традиционного анализа) имеют очевидную теоретич. и практич. ценность, так как они выявляют потенциальные вычислительные тупики и способствуют четкому уяснению принципиальных границ вычислительных возможностей. Так, доказана невозможность следующих алгоритмов (в смысле одного из уточнений понятия алгоритма): 1) распознающего для произвольного конструктивного действительного числа равно оно нулю или нет; 2) находящего для каждой сходящейся к. п. р. ч. то к. д. ч., к к-рому она сходится; 3) находящего для каждой совместной системы линейных уравнений (над полем к. д. ч.) какое-либо ее решение; 4) находящего для каждой непрерывной кусочно линейной знакопеременной функции корень этой функции; 5) находящего для всякой непрерывной кусочно линейной на единичном сегменте функции ее интеграл Римана по этому сегменту. К этому же кругу результатов принадлежит и следующая теорема, полностью решающая вопрос о возможности эффективного перехода от одной системы счисления к другой: алгоритм, находящий для всякой m-ичной конструктивной дроби равную ей n-ичную конструктивную дробь, возможен тогда и только тогда, когда множество простых делителей псодержится в множестве простых делителей т(см. [6]). (В частности, возможен алгоритм перехода от десятичной системы счисления к двоичной, но невозможен алгоритм перехода от двоичной системы к десятичной.) Теоремы о невозможности алгоритмов часто сопровождаются в К. а. теоремами о существовании алгоритмов, решающих рассматриваемые задачи по более полным исходным данным (ср. теорему о полноте к. д. ч. и пример 2)) или с произвольной наперед заданной точностью (напр., можно построить алгоритм, находящий для каждой всюду определенной знакопеременной к. ф. f и каждого пк. д. ч. х f, п такое, что |f(xf, n)|<2-n). Сопоставление таких результатов позволяет во многих случаях получить отчетливое представление о том, как можно корректно ставить ту или иную алгоритмич. проблему. Лит.:[1] Turing A. M., "Proc. London Math. Soc. Ser. II", 1937, v. 42, p. 230-65; v. 43, part 6, p. 544-46; [2] Ваnach S., Mazur S., "Ann. polon. math.", 1937, v. 16, p. 223; [3] Mazur S., Computable analysis, Warszawa, 1963; [4] S p e ck er E., "J. Symbol. Log.", 1949, v. 14, № 3, p. 145- 158; [5] Grzegorczyk A., "Fundam. math.", 1955, v. 42, p. 168-202,232-39; 1957, V. 44, № 1, p. 61-71; [6] Mоstоwsk i А., там же, р. 37-51; [7] Кlaua D., Konstruktive Analysis, В., 1961; [8] Кreisel G., Lасоmbe D., Sсhoenfield J. R., "C. r. Acad. sci.", 1957, t. 245, № 4, p. 399-402; [9] Кreisel G., Lасоmbe D., там же, Ni14, p. 1106-1109; [10] Lacombe D., там же, 1955, t. 240, №26, p. 2478-80; t. 241, N4 1, p. 13-14, №2, p. 151-53, № 19, p. 1250-52; 1957, t. 244, № 7, p. 838-40, N5 8, p. 996 — 97; t. 245, № 13, p. 1040-43; 1958, t. 246, № 1, p. 28-31; [11] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [12] Гудстейн Р. Л., Рекурсивный математический анализ, пер. с англ., М., 1970; [13] Bishop E., Foundations of constructive analysis, N. Y., 1967; [14] Мартин-Лёф П., Очерки по конструктивной математике, пер. с англ., М., 1975; [151 Марков А. А., Теория алгорифмов, М.- Л., 1954; [16] Шанин Н. А., "Тр. матем. ин-та АН СССР", 1962, т. 67, с. 15-294; [17] Заславский И. Д., там же. с. 385-457; [18] Цейтин Г. С, там же, с. 295-361; [19] Кушнер Б. А., Лекции по конструктивному математическому анализу, М., 1973. Б. А. Кушнер.