Конструктивное Метрическое Пространство

Концепция метрич. пространства, используемая в конструктивной математике. Близкий смысл имеет также понятие рекурсивного метрического пространства. Список где — некоторое множество конструктивных объектов (обычно слов в том или ином алфавите), р — алгоритм, переводящий любую пару элементов в конструктивное действительное число (к. д. ч., см. Конструктивный анализ), наз. К. м. п., если при любых выполняется: 1) r( Х, Х)=0,2) r( Х, У)r(X, Z)+r(Y, Z )(здесь и ниже термин "алгоритм" употребляется в смысле одного из точных понятий алгоритма). Множество и алгоритм р наз. носителем и метрическим алгоритмом соответствующего К. м. п., а элементы — точками этого К. м. п. Из аксиом 1), 2) следует, что всегда и r( Х, Y)=r(Y, X). Две точки называются эквивалентными (различными) в К. м. п. если r( Х, У)=0 (соответственно r(X, Y) неравно 0). Примеры К. м. п.: а) пространство натуральных чисел Н. Носителем Нявляется множество натуральных чисел (натуральные числа трактуются как слова вида О, 01, 011, ...), а метрич. алгоритм р таков, что р( т, п)=|m- п|. Аналогично определяются пространства Rи Е х- рациональных и конструктивных действительных чисел, соответственно; б) "-мерное евклидово пространство ЕД. Носителем Е п является множество слов вида x1* ... *х п, где х;,. есть к. д. ч., а метрич. алгоритм строится так, что в) пространство Сравномерно непрерывных на единичном сегменте конструктивных функций. Носителем Сявляется множество слов вида где f- всюду определенная на единичном сегменте конструктивная функция, а g — алгоритм, переводящий всякое натуральное число в натуральное число, причем( означает запись (код) алгоритма U). Метрнч. алгоритм р строится так, что Сложный вид носителя пространства Собусловлен требованием эффективной вычислимости метрики; г) бэровское пространство Вобщерекурсивных функций. Носителем Вявляется множество гёделевых номеров общерекурсивных функций, а метрич. алгоритм р строится так, что если j п и jm — общерекурсивные функции с номерами n и т, то р(га, т)= 0, если jn(i) = jm(i) при любом i, и r( п, m)=2-k, если jn(i) = jm(i) при i<k и Пусть — К. м. п. Алгоритм Р наз. последовательностью точек М, если при всяком пимеем Последовательность Р наз. регулярной, если при имеем r(b(т), b(n))<2-n. Регулярная последовательность b сходится к точке XК. м. п. М, если при любом пимеем р( Х, К. м. п. Мназ. полным, если существует алгоритм, находящий для каждой регулярной последовательности р (точек М)точку М, к к-рой сходится р. К. м. п. Мназ. сепарабельным, если существуют алгоритмы а, d такие, что а — последовательность точек М, и при любом и любом пимеем: d( Х*п). есть натуральное число, причем r(a(d( Х*п)), Х)<2-n. Все пространства Н, R, Е 1, Е п, С, В примеров а) — г) сепарабельны, пространства Н, Е 1, Е п, С, кроме того, полны. Пример несепарабельного К. м. п. дает рассмотрение подпространства Н, индуцированного не рекурсивно перечислимым множеством. В терминах К. м. п. могут быть изложены многие результаты классич. теории метрич. пространств; в частности, большое значение имеет конструктивный вариант теоремы Хаусдорфа, утверждающий, что для каждого К. м. п. может быть построено его пополнение. Процесс пополнения К. м. п. является сильным средством введения тех или иных структур конструктивной математики. На этом пути вводятся к. д. ч., могут быть определены естественные аналоги классич. понятий измеримых множеств и функций, интегрируемых по Лебегу функций, и т. д. Одной из основных целей теории К. м. п. является исследование алгоритмич. отображений, корректных относительно тех или иных вычислимых метрик. Пусть " — К. м. п. Алгоритмнческим оператором типа М 1->М 2 наз. алгоритм y, удовлетворяющий условиям: а) если и определено W(X), то б) если X,Y- эквивалентные точки М, (т. е. r( Х, Y) = 0) и определено Y(Х), то определено Y(Y), причем Y(Х), W(Y)- эквивалентные точки М 2. Алгоритмич. операторы типа суть конструктивные функции одной и ппеременных; алгоритмич. операторы типа принято наз. эффективными функционалами. Основным результатом теории алгоритмических операторов является теорема Цейтина, утверждающая, что в случае полного сепарабельного К. м. п. М 1 для любого алгоритмич. оператора Wтипа при каждом пможно построить алгоритмически (рекурсивно) перечислимое множество шаров, покрывающее область определения W, такое, что колебание Yна любом шаре этого множества не превосходит 2-n. Из этой теоремы вытекает известный результат о продолжимости эффективных функционалов до частично-рекурсивных функционалов. Другим важным следствием приведенного результата является теорема о непрерывности алгоритмич. операторов: если М 1- полное и сепарабельное К. м. п., М 2- произвольное К. м. п., то по любому алгоритмич. оператору Vтипа можно построить алгоритм aтакой, что для любых X, У из области определения Vи любого пчисло a(Х, n) есть натуральное, причем из r1(X, Y)<2-a(X, n) следует p2(Y(X),Y(Y))<2-n. В таком же порядке идей, что и в случае К. м. п., может быть развита теория конструктивных нормированных и гильбертовых пространств. Лит.:[1] Цейтин Г. С, "Тр. матем. ин-та АН СССР", 1962, т. 67, с. 295-361; [2] Моsсhоvakis G. N.. "Fundam, math.", 1964, v. 55, № 3, p. 215-38; [3] Шанин Н. А., "Тр. матем. ин-та АН СССР", 1962, т. 67, с. 15-294; [4] Кушнер Б. А., Лекции по конструктивному математическому анализу, М., 1973. Б. А. Кушнер.