Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 131

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

S3]

ВЫБОР

ПЕРЕЧИСЛИМОГО ПОКРЫТИЯ. НЕПРЕРЫВНОСТЬ 4Ц

пример, записи

алгорифмов типа

(2@—*Ж). При этом на оператор

естественно

наложить требование

корректности, состоящее в дан­

ном

случае

в том, что если два входных предписания определяют

одну

и ту же функцию,

то получаемые по ним с помощью опера­

тора

предписания также

определяют вычисление одной и той же

функции. Такой характер носят эффективные функционалы и кон­

структивные

функции. Следуя

Ц е й т и н у [5], назовем

операторы

описанного

типа

операторами

Маркова. При втором подходе

опера­

тор использует

не предписания

для вычисления аргументной

функ­

ции — такое

предписание может

быть неизвестным, — а

лишь зна­

чения исходной функции, которые предполагаются доступными вся­ кий раз, когда в них возникает необходимость. Можно представить себе, что имеется «оракул», вычисляющий исходную фунцию, к ко­ торому обращается оператор в процессе вычисления значений ре­ зультирующей функции. При таком подходе можно даже не пред­ полагать вычислимости исходной функции — вычислимость резуль­ тата носит здесь относительный характер; именно, результирующая

функция вычислима в той степени, в какой умеет

вычислять исход­

ную функцию «оракул». Условие корректности в данном случае вы­

полнено автоматически, более того, если результирующая

функция

оказалась, например, определенной в 0, то при вычислении

ее зна­

чения были использованы лишь значения

исходной функции в не­

котором конечном

числе

точек, так что для любой

другой

функции,

совпадающей с исходной

в этих точках, результирующая

функция

примет в нуле то же самое

значение. В случае

операторов над

арифметическими

функциями

в качестве

общего

варианта

описан­

ного типа операторов естественно принять частично рекурсивные

операторы

в смысле

К л и н и

[4, § 63]*).

Аналогичный

характер

носят

вычислимые

функционалы

Г ж е г о р ч и к а [2] и

определяе­

мые

на их основе

вычислимые

действительные

функции.

(Вычисли­

мые

действительные

функции

такого типа

рассматриваются

также

К л а у а

[2],

[4].)

Операторы

описанного

типа мы,

следуя

 

*) Приведем определение частично рекурсивного оператора (от

одного

функционального

аргумента), следуя Л а х л а н у [2]. Назо­

вем

/-кортежем

пустое

слово

или кортеж

пар натуральных

чисел

(24)п{, т1»п2, т2* ... * nk, mk.

Пусть ф — (частичная)

арифметическая

функция.

Скажем,

что ф

продолжает

кортеж (24), если ф(/1( )=/п(

(1 ^'t ^fe) . Будем

так­

же считать,

что любая

функция продолжает пустой

/-кортеж.

Про­

извольное слово вида i » /» Р, где i, j — натуральные числа, Р — /-кор­

теж, назовем

0-кортежем. Пусть Ф — оператор (в

традиционном

смысле этого

слова), переводящий всякую арифметическую функ­

цию ф в арифметическую функцию Ф (ф). Назовем

Ф частично ре­

курсивным, если можно построить перечислимое множество 0-кор-

тежей

W так, что

при любой

функции ф и натуральных

<', /

ф ^ф) (j) = j тогда

и только

тогда,

когда

существует 0-кортеж

i*j*P

из W такой,

что ф продолжает

Р. С

топологической

трак­

товкой частично рекурсивных операторов можно ознакомиться в ра­ ботах У с п е н с к о г о [1] и Л а х л а н а [2].

412

КОНСТРУКТИВНЫЕ МЕТРИЧЕСКИЕ ПРОСТРАНСТВА

[ГЛ. 8

Ц е й т и н у [5], назовем операторами Клини * ) . Ясно, что от опера­ тора Клини нетрудно перейти к совпадающему с ним (на вычислимых функциях) оператору Маркова: оракул может быть заменен уни­ версальным алгорифмом, который, получив запись исходного алго­ рифма, выдает требуемые в процессе вычисления значения исход­ ной функции. Соединение этого универсального алгорифма с описа­ нием самого оператора позволит построить алгорифм, который по записи исходной функции и п выдает значение результирующей функции в точке п (если оно определено). От этого алгорифма легко перейти к алгорифму, переводящему запись алгорифма вы­ числения исходной функции в запись алгорифма, вычисляющего ре­

зультирующую

функцию. Обратный переход

от

оператора

Маркова

к

оператору

Клини, напротив,

отнюдь не очевиден: в самом деле,

в

то время

как

оператор Клини

использует

при

вычислении

данного

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

раторов такой

переход возможен—например, вычисление суммы

двух

К Д Ч (определенное нами посредством

некоторого

оператора

типа

Маркова)

может быть реализовано

посредством

оператора

Клини: для того чтобы найти рациональное приближение к резуль­ тату с точностью до 2 - п , вовсе не нужно знать исходные числа с любой степенью точности, достаточно иметь рациональные при­ ближения к ним с точностью до 2 - " - 1 . Оказывается, теорему 3 можно в определенном смысле трактовать как утверждение о про­ должимости марковских операторов из некоторого достаточно ши­ рокого класса до операторов" клиниевского типа.

Действительно, всякая точка X сепарабельного

КМП

может

быть

некоторым

стандартным образом

представлена

сходящейся

к ней последовательностью элементов плотного множества;

члены

этой

последовательности можно рассматривать

как

приближения

к X,

а само слово X трактовать как код

алгорифма, вычисляющего

соответствующую

X последовательность.

В свете

сказанного

есте­

ственно считать, что рассматриваемые в теореме 3 операторы имеют марковский характер. Теорема 3 позволяет определить клиниевский

процесс

вычисления приближений фигурирующего в ней

опера­

тора

W,

использующий

не саму точку

X,

а

лишь

приближения

к ней. Этот процесс для данной точки X и точности 2~т

можно

коротко описать так: пользуясь приближениями к X, ищем /, при

котором

\о(т, I) и X принадлежит шару

о(т,

I);

в

случае

нахож­

дения

такого / х(т,1)

считаем приближением

W(X)

с точностью

2 _ т

(в смысле метрики

М 2

) . Если ^ ( J ) ,

то

соответствующее

I

дей-

*) Ясно, что клиниевский характер носят, например, тожде­

ственный оператор и оператор наименьшего

числа:

 

 

 

 

V

( Ф )

(я) а« ф (л),

 

 

 

 

 

 

 

 

 

((£Н*Сi—Q

5 31

ВЫБОР

ПЕРЕЧИСЛИМОГО

ПОКРЫТИЯ. НЕПРЕРЫВНОСТЬ

413

ствительно найдется*).

Вместе

с тем

описанный процесс

может

дать

результат

и при X,

на котором

Ч/ не определен. Возникает

естественный вопрос об усилении теоремы 3, при котором эта воз­ можность была бы исключена. Из результатов следующего пункта следует, что такое усиление невозможно. В самом деле, при каж­ дом фиксированном т описанный нами процесс будет завершаться нахождением требуемого / для любого X, принадлежащего какому-

нибудь из шаров a(m,k). Другими

словами,

область

определения

этого процесса будет лакомбовым множеством

(объединением ша­

ров, перечисляемых алгорифмом бт).

Вместе

с тем в

следующем

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

3. Следствие 4 п. 4 § 2 показывает, что если алго­ рифмический оператор определен в некоторой точке X

слабо

полного

КМП,

то в любой последовательности

точек,

(конструктивно)

сходящейся к

X, сколь угодно

далеко

имеются

точки

определенности

этого оператора.

В большинстве реально встречающихся случаев оказы­

вается, что, сверх того, существует

шар с центром в

точке X, на котором всюду определен

рассматриваемый

оператор. В частности, таким свойством обладают все элементарные конструктивные функции и функции, по­ лучаемые из них с помощью арифметических операций и суперпозиций. Построение алгорифмических операто­ ров, не обладающих этим свойством, требует достаточно тонких конструкций. Первые примеры такого рода — примеры эффективных функционалов, области опреде­ ления которых не являются открытыми множествами — построены Ф р и д б е р го м [1] и А. А. Мучником **) (ре­ зультат Мучника, не опубликованный автором, воспро­ изведен в работе Ц е й т и н а [8], там же указано, что Мучник доказал аналогичную теорему и для конструк­

тивных

функций).

 

 

Мы будем следовать общей конструкции, принад­

лежащей

М о с к о в а к и с у [1] и

позволяющей

получить

*)

Очевидно, если Ч / — эффективный функционал,

\W(X) и

т = 1,

то

находимое нами приближение

совпадает с Ч/(Х). Таким

образом, мы получаем клиниевский функционал, являющийся про­ должением исходного.

**) И тот и другой автор имели в виду получение примера эф­ фективного функционала, не совпадающего (на общерекурсивных функциях) ни с каким частично рекурсивным оператором.

414 КОНСТРУКТИВНЫЕ МЕТРИЧЕСКИЕ ПРОСТРАНСТВА [ГЛ. 9

единообразным способом интересующие нас примеры как для бэровского пространства, так и для конструк­ тивной прямой.

Пусть 33 — тот

же

самый алгорифм, что и в п. 3 § 2,

т. е. при любом алгорифме 21 (в алфавите А")

и любом

слове

Q (в алфавите

А)

 

 

 

 

(25)

 

 

23(Е213, Q ) ~ 2 l (Q) .

 

 

 

Для

произвольного слова Р в алфавите

^ 0 =

{0]} обо­

значим через

{Р)

алгорифм 33р. В

силу

(25),

если

Р==

= £213, т 0 П Р И

любом

Q

 

 

 

 

 

 

 

<P)(Q)~2I(Q).

 

 

 

 

Обозначим

через

3Su такие множества слов в

алфа­

вите

^о, что

 

 

 

 

 

 

 

(26)

P e J j S

VI

((!<Р> (0) & «Р> (0 е

Ж))

 

 

 

 

 

<<fe

 

 

 

 

(где

Ж — множество

натуральных

чисел).

 

 

Пусть М — сепарабельное КМП

с метрическим

алго­

рифмом р и алгорифм р перечисляет плотное подмноже­

ство М.

Обозначим через Ж\

такие множества слов

в Ч0, что

 

 

(27)

Р е М Й ( Р е а д &

V/(!р(<Р)(/))).

Для Р е= Ж\ мы будем использовать следующее со­ кращение:

(28)через {Р\ (при г'</г) обозначается Р((Р)(/)).

Очевидно,

{P}i

есть

элемент КМП М.

 

 

Введем в

рассмотрение множества

Жk

слов

в Ч0

такие,

что

 

 

 

 

 

 

(29) Р^мк={Р^Ж\)&

 

Vij {i < / <k ZD р({Р}г , {Р}/) <

2 - ' ) .

Из

(25) — (29)

легко

усматривается,

что

все множе­

ства Жь. перечислимы. Обозначим через Жао пересече­ ние множеств Жь, т. е.

(30) Р ^ Ж ^ Vk (Р е Жк).

Ясно, что Р принадлежит Жх в том и только в том случае, когда: 1) ( Р ) есть последовательность нату-.

Смотрите также файлы