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

Скачать файл (14,18Мб)

Заказать решение

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

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

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

Добавлен: 15.10.2024

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

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

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

§2]		СОГЛАСОВАННЫЕ МНОЖЕСТВА. ОПЕРАТОРЫ					383
1)	W	является	алгорифмом		типа	(М\-г> Ж%),	т. е.
перерабатывает всякий				элемент	Ж\, к	которому он	при
меним,	в	элемент	Ж2;
2)	для	любых	X и	Y из М Ь	если	lip(X) и X =	Y, то

гф (У) и г|>(П = !>(*).

В этом параграфе, за исключением особо оговари

ваемых

мест,

все

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

алгорифмические

операторы

считаются

операторами типа

M I T * M 2 . В

этой

связи

упоминание

о Mi и М 2

, равно

как

прилагательное

«алгорифмический»,

часто

опускается.

О п р е д е л е н и е

Будем

говорить,

что

алгориф

мический

оператор

W определен

(не

определен)

в точке

X e J U i если

{^(Х)

(соответственно

~ W ( X ) ) .

Будем

говорить,

что множество

Ж <=М{

является

областью

определения

оператора

у¥,

если

для

любого

Хиз

X<=X

\ib (X).

Назовем

оператор

всюду

определенным,

если

он определен

в каждой

точке КМП

Мх.

5—6

следует

Непосредственно

из определений

2—3,

Т е о р е м а

4. 1)

Всякий

алгорифмический

оператор

является

согласованным

алгорифмом.

Если

множество

является

областью

определе

ния какого-нибудь

алгорифмического

оператора,

то

Ж—

согласованное

множество.

Обратно,

если

М 2

содержит

хотя

бы

один

элемент

Z, то

любое

согласованное

множество

(точек

Мх)

яв

ляется областью определения некоторого алгорифмиче

ского	оператора			(типа		M I T > M 2 ) .		Действительно,			если
алгорифм		21	согласует			множество		Ж^Жи	то	алгорифм
W, перерабатывающий в Z всякое слово, к которому он
применим, и такой, что при любом слове Р
					lW(P)^m(P),
является		искомым			алгорифмический оператором.						Та
ким образом,			имеет		место		М2 содержит
Т е о р е м а			5.	Если		КМП			хотя бы		один
элемент,		то множество				Ж s	Ж\	согласовано		тогда и
только	тогда,		когда		оно	является		областью		определения
некоторого алгорифмического							оператора.

384

КОНСТРУКТИВНЫЕ

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

[ГЛ. 9

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

Я 0

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

пространства

натуральных

чисел Н,

индуцированное

одноэлементным

множеством

{0}.

Множество

Ж Е

Л\

согласовано

С л е д с т в и е

тогда

и только

тогда,

когда

оно

является

областью

определения

алгорифмического

оператора

типа М\-т*Н0.

Теорема 5 и следствие

1 устанавливают

тесную

связь

между алгорифмическими операторами и согласован ными множествами, позволяющую формулировать ре зультаты о согласованных множествах в терминах опе

раторов

и наоборот.

Ясно,

что

конструктивные

функции

одной

перемен

ной

являются

алгорифмическими

операторами

типа

Е, т*Ей

конструктивные

функции

переменных

(п >

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

любого

из трех типов: Еп

—> Е\,

Е\

-Г* Ей

Е2п

Е\.

О п р е д е л е н и е -7.

Алгорифмические

операторы

типа В т * Я

(где

В — бэровское

пространство,

Н — про

странство натуральных

чисел)

будем

называть

эффек

тивными

функционалами.

Эффективные функционалы есть, очевидно, алгориф

мы,

перерабатывающие

те

записи

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

натуральных

чисел (ПНЧ),

которым

они

применимы,

в натуральные числа; при этом совпадающие ПНЧ пе реводятся в равные натуральные числа.

Наряду с эффективными функционалами в смысле определения 7 естественно рассматривать вычислимые функционалы более общего рода, областью согласован ности которых является множество записей алгорифмов типа (Ж^*Ж)*). (Переход от ПНЧ к таким алгориф мам вполне аналогичен переходу от общерекурсивных функций к частично рекурсивным.) Более точно, вычис лимый функционал задается алгорифмом f, перерабаты

вающим запись всякого алгорифма типа (Ж-т>Ж),					к ко
торой он применим, в		натуральное число,		причем	если
*) Легко видеть, что на этом множестве нельзя ввести кон
структивную	метрику, согласованную		с совпадением алгорифмов
как функций	типа (Эё'^Ш).	Точнее	говоря, если	обозначить че
рез Т0 множество записей		алгорифмов типа		то	невоз
можен алгорифм р такой, что список {Го, р} является КМП и

Р (£YI3, £Y*3) = 0 ss у " (Yi (") ^ Y2 («))•

§ 2]

СОГЛАСОВАННЫЕ МНОЖЕСТВА. ОПЕРАТОРЫ

385

при любом п

Y, (я) ~ Y2 (л),

то

Такие вычислимые функционалы с точностью до тех нических деталей представляют собой частный случай эффективных операций, введенных и исчерпывающим

образом	изученных		в	работе		М а й х и л л а и		Ш е -
п е р д с о н а		[1].
Наиболее существенные свойства эффективных функ
ционалов (или вполне аналогичных им объектов)								были
установлены		в работах		К р а й з е л а ,			Л а к о м б а ,	Ш ё н -
ф и л д а	[1]—[2], Ц е й т и н а				[3]—[5],		Ф р и д б е р г а [1].
Некоторые из результатов этих						работ приведены		ниже.
2. В	этом	пункте	будет		доказано		естественное	обоб

щение известной теоремы Маркова о неразрывности кон

структивных функций	( М а р к о в [3], [5]; доказатель
ство для случая КМП	впервые опубликовано в работе

С л и с е н к о [3]). Хотя теорема неразрывности и вытекает из доказываемых в п. 5 более сильных результатов, мы предпочитаем привести отдельное доказательство, тем

более, что это	доказательство, во-первых, приложимо
к значительно	более широкому, чем алгоритмические

операторы, классу алгорифмов, во-вторых, не опирается на принцип Маркова и, в-третьих, благодаря своей прозрачности способствует фиксации используемых в таких ситуациях идей.

Пусть 21 — алгорифм,

X — точка КМП

М,.

О п р е д е л е н и е

Будем

говорить,

что 91

является

алгорифмом

типа ( М 1 - > М 2 ) в

точке X,

если

при

любом

Y е

М{

таком, что Y =

выполняется

!9l (F),

91 (Y) е

М2

и %(Y)

%(X).

м2

Будем

говорить,

что

алгорифм

О п р е д е л е н и е

91 имеет конструктивный

разрыв типа

(М\ —*М2)

в точ

ке

если

91 является

алгорифмом

типа

(Mi -> М2)

этой точке

и осуществимы

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

точек

и рациональное

число

г >

0 такие,

что при

любом

ке

91 является

алгорифмом

типа

(Мх—*iH2)

6 т о ч ~

р(п);

13 В. А. Кушнер

386

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

[ГЛ. 9

2)РЛХ, Р ( « ) ) < 2 - " ;

3)р 2 ( а д , « ( Р ( я ) ) ) > г « ) .

(Напомним,	что р ь	р2 — метрические алгорифмы про
странств М{,	М2.)	алгорифм 21 (фигурирующий в опре
В случае, когда		алгорифм 21 (фигурирующий в опре

делении 9) есть алгоритмический оператор, можно ска зать, что этот оператор определен в точке X и во всех

точках	Р(п),	причем всегда p2 (9l (X), 21 (Р(п))) ^			г.
Т е о р е м а		6 (теорема неразрывности). Пусть			М\ —
слабо	полное,	М2	— произвольное КМП.	Никакой	алго
рифм	не может		иметь конструктивного	разрыва	типа

(Af,- >Af2 ).

Доказательству этой теоремы предпошлем следую

щую лемму

(ср. § 1 гл. 4).

Л е м м а

Пусть

21 — алгорифм,

X е

Ми

р — по

следовательность

точек Ми

причем

при

любом

(3)

р, (Я, р ( п ) ) < 2-".

Тогда

можно

построить

алгорифм

у такой,

что

для

любого

слова

(в

фиксированном

нами

алфавите

А)

выполняется

если

~]№(Р),

то \у(Р),

у(Р)сгМ1

у(Р)

Х;

л».

если

!2ЦР)

заканчивает

работу

над

точно

за k

шагов,

то \у{Р),

у{Р)^М1

y(P) —

${k-\-\).

ж,

у1,

у2,

у3

Д о к а з а т е л ь с т в о . Построим

алгорифмы

так,

что

У ( Р ) ~ ц / ( [ 2 1 ] ( Р , i)=*=

Л);

р ( « + 1 ) ,

если

[91](Р, я ) # Л ,

р ( у 1 И + 1 ) ,

если

[2Х](Р,я) =

Л ;

*) Приводимая ниже теорема неразрывности почти точно так же может быть доказана и при более общем понятии конструктив ного разрыва, связанном с отказом от требования Я (Y) — Ж (X)

в определении 8. Заметим также, что условие 2) определения 9 (ре-

	СОГЛАСОВАННЫЕ МНОЖЕСТВА.	ОПЕРАТОРЫ	387
Пусть Lim — алгорифм слабого предельного			перехода
в М\	(определение 7 § 1). Строим	искомый алгорифм у
так,	чтобы

Y ( P ) ~ L i m ( y 3 ( P ) ) .

Если П!91(Р), то при любом п
Поэтому	[91] (Р, п) =			А.
	Y 2 (P ,		п)~$(п+1).

Из (3) тогда	получаем,		что у2р		есть регулярная по
следовательность точек, сходящаяся к X. Следователь
но, !Lim(y3 (P)) и Lim (у3		(Р)) =		X,	что и требуется.
Пусть теперь	191 (Р) и 91 заканчивает					работу над Р
точно за k шагов. Тогда
	( 8 ( л + 1 )		при		0 < п < 6 ,
Y { F ' H ) '	1 p(jfe+	1)	при		k<n.
Следовательно ((3)), ур является регулярной после
довательностью.	Кроме	того,		очевидно,		у2р сходится
к р (&--[- 1). Отсюда так же, как и выше,						получаем, что
\|у(Р), v ( P ) e « i	и Y (P ) =		p ( f e + l ) .

м1

Теперь нетрудно доказать теорему неразрывности.

Обозначим через $ алгорифм со следующим						свойством:
невозможен		алгорифм 2) (над алфавитом			А)	такой, что
для любого слова			Р (в А)
				т(р)*а-]19(р).
Пусть Mi — слабо полное КМП и алгорифм 91 имеет
конструктивный			разрыв типа (Mi -> М2 ) в			точке X.
Пусть	далее	В и		г — соответствующие	последователь
ность	точек	Mi	и	рациональное число	(см. определе

ние 9). Применим к р и X лемму 1 и обозначим че рез у алгорифм, построенный согласно этой лемме.


гулярная сходимость в к X) можно						было бы заменить			требованием
(конструктивной)		сходимости			6 к X	(именно	так определяется			кон
структивный	разрыв		в	работе	М а р к о в а		[5]): при		наличии	кон
структивного	разрыва		в	этом	более	широком		смысле	имеет	место
и конструктивный		разрыв в смысле определения						9.

13*

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

Лебедев, Н. Н. Курс инженерной геодезии. Геодезические работы при проектировании и строительстве городов и тоннелей учебник.pdf

Лурье, Г. Б. Основы технологии абразивной доводочно-притирочной обработки учебник.pdf

Маринов, И. А. Устройство и эксплуатация преобразовательных подстанций городского электротранспорта учеб. пособие.pdf

Межотраслевые связи и народнохозяйственные пропорции Восточной Сибири и Дальнего Востока..pdf

Мирзоян, Э. Н. Развитие учения о рекапитуляции.pdf

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

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

Информация

Списки файлов

Дополнительно