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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ

347

что противоречит

(10). Следовательно, из !31(Я)

следует

~~\\ф(Р) и эквивалентность (8) доказана.

 

 

Однако

алгорифм 91, удовлетворяющий

(8),

невоз­

можен. Теорема

доказана.

 

 

Заметим,

что

полученная нами оценка

(10)

связана

свыбором у-ограниченного покрытия Ф. Выбирая

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

Отметим два очевидных следствия теоремы 1.

С л е д с т в и е

1.

Невозможен

алгорифм,

перерабаты­

вающий

запись

всякой

ограниченной

числом

1, полиго­

нальной

на

0 А 1

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

ее

R-интегралом

на

O A 1,

в запись

регулятора

интегрируе­

мости этой функции

на 0 А 1.

 

 

 

 

С л е д с т в и е

2.

Невозможен

алгорифм,

перерабаты­

вающий

запись

всякой

интегрируемой

по

Риману

на

0 А 1 функции

в запись

регулятора

интегрируемости

этой

функции

на 0 А 1.

 

 

 

 

 

 

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

следующей теоремой.

 

 

 

 

Т е о р е м а

2. Невозможен

алгорифм о,

перерабаты­

вающий

запись

всякой

неотрицательной,

ограниченной

числом

1, полигональной

на 0 А 1 функции

f в КДЧ та­

кое, что для любого z,

если

z=

f, то \z

— cr(c73)l<

 

 

 

 

 

о

 

*) Вместо -yg- в этой теореме могло бы фигурировать любое

КДЧ, меньшее ~ (ср. с замечанием, сделанным после доказа­ тельства теоремы 1).

348

СИНГУЛЯРНЫЕ ПОКРЫТИЯ

[ГЛ. 8

Д о к а з а т е л ь с т в о .

Обозначим на

время доказа­

тельства

сегмент t n i i A t n

t i + i

через an>i.

Построим алго­

рифм F так, чтобы при любых п и х

 

 

F (я, х) = 2 A

(п, /) • Q (а„,ь

х).

1=0

Нетрудно проверить, что

(11)F является последовательностью функций, при­ чем каждая функция Fn полигональна и обра­

 

щается в 0 на сегментах Ф(0)

Ф ( " ) ,

(12)

при любом п

 

1 - ^ | Ф ( 0 1 ) = / ^ «

1=0

I

о

 

 

1

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

z =

оJ Fn, то

(13)функция Fn неотрицательна и ограничена едини­ цей.

Пользуясь леммой 1, построим для F, функции f, тождественно равной 0, и алгорифма ф такой алго­ рифм у, что имеет место

(14)

Md (f, F, ф, у).

Предположим теперь, что алгорифм а, невозмож­ ность которого утверждается теоремой, построен. По­ строим алгорифм о\ так, чтобы для любого слова Р в Ч0

(15)

0 , ( Р ) ~ а ( В р З ) .

Нетрудно далее (используя, например, алгорифм Рз) построить алгорифм а2 , применимый к любому КДЧ и такой, что

(16)

если

о2{х)=?А,

то

х<-^г,

(17)

если

о2{х)Фг\,

то

х > ~ .

ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ

349

Пусть ст3 — алгорифм, удовлетворяющий для любого слова Р в Ч0 условию

(18)

 

!а3 (Р)=нР== Л .

Построим

алгорифм

91 так,

чтобы

(19)

 

 

 

ад^стзМмя))),

и докажем,

что

 

 

 

 

 

(20)

 

!21(Р)= - ]!ф(Р) .

Пусть

~\\§(Р). Тогда

 

((14))

всюду на 0 Л 1

(21)

 

yP(x)

=

 

f(x)

=

0.

Следовательно,

 

 

 

 

 

(22)

 

0 =

 

уР.

 

 

 

 

 

 

о

 

а , ( Р ) - К Д Ч , причем

Ввиду

(15), (21) — (22)

!ог,(Р) и

 

J

 

 

lor, ( Я ) 1 < т ^ - Следовательно ((16) —(17)),

^ ( < т , ( Я ) ) = Л

и ((18))

!2ЦР).

Пусть теперь !21(Р). Предположим, что !ф(Р) и ф заканчивает работу над Р точно за k шагов. Тогда всюду на О Д 1

 

 

 

yp(x)

=

Fk(x)

 

 

и

поэтому ((11) —(13)) \аг{Р),

причем, ввиду

(12),

 

 

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

((16) —(17)),

 

 

 

 

 

^ ( а , (Р))=#Л

 

 

и

~1 !2t (Р), что противоречит

условию. Следовательно,

из

!21(Р)

следует

~]\$(Р)

и

эквивалентность

(20)

пол­

ностью

доказана.

Алгорифм

21, удовлетворяющий

(20),

однако,

невозможен. Теорема

доказана.

 

 

350

СИНГУЛЯРНЫЕ ПОКРЫТИЯ

[ГЛ. 8

Эту теорему

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

1 § 1

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

данных, кроме

самой

функции, ее регулятор

интегрируе­

мости.

 

 

 

3. Невозможен

алгорифм,

 

перерабаты­

С л е д с т в и е

 

вающий

запись

 

всякой

полигональной

на

0 Л

1

ограни­

ченной

числом

1 функции

в КДЧ,

являющееся

 

 

интегра­

лом Римана

этой функции

на ОД 1.

 

 

 

 

 

С л е д с т в и е

4. Невозможен

алгорифм,

 

перерабаты­

вающий

запись

 

всякой

R-интегрируемой

на 0 Д

1

ограни­

ченной

числом

1 функции

в КДЧ, являющееся

 

 

интегра­

лом Римана

этой функции

на ОД 1.

 

 

 

 

 

Поскольку

всякий

полигональный

интеграл

 

(опреде­

ление

б §

2)

является интегралом

Римана,

получаем

С л е д с т в и е

5. Невозможен

алгорифм,

 

перерабаты­

вающий

запись

 

всякой

полигональной

на

0 Д

1

 

функции

в определяющее

 

дробление

этой функции

(см. определе­

ние 6 § 1 гл. 5).

 

 

 

 

 

 

 

 

 

Кроме того,

из каждой

из теорем

1—2

вытекает тео­

рема И. Д. Заславского о невозможности алгорифма, пе­ рерабатывающего запись всякой равномерно непрерыв­

ной на ОД 1 функции в запись регулятора

равномерной

непрерывности

этой

функции

( З а с л а в с к и й

[4;

тео­

рема

5.6]).

 

 

 

 

 

 

 

 

2. Остановимся теперь на вопросе распознавания ин­

тегрируемости

функций.

 

 

 

 

 

Т е о р е м а

3.

Невозможен

алгорифм,

применимый

к записи функции

тогда и только тогда,

когда эта функ­

ция интегрируема

по

Риману

на ОД 1.

 

 

 

 

Т е о р е м а

4.

Невозможен

алгорифм,

применимый

к

записи

функции

тогда и только тогда, когда

эта

функция

неинтегрируема

по Риману на

ОД 1.

 

 

 

 

Разумеется,

эти

теоремы

остаются

в силе

для

лю­

бого сегмента положительной длины. В приводимых ниже доказательствах теорем 3—4 через /6 обозначается неинтегрируемая по Риману функция, построенная в до­ казательстве теоремы 8 § 2. Функция f6 является склей­ кой последовательности Н (стр. 323).

§ 3]

 

ТЕОРЕМЫ

НЕВОЗМОЖНОСТИ

АЛГОРИФМОВ

 

351

Д о к а з а т е л ь с т в о

 

т е о р е м ы

3.

Строим

алго­

рифм F так, чтобы

 

 

 

 

 

 

 

 

 

 

 

 

 

F(n,

*) =

 

Ы * ) -

2 я ( * , * ) .

 

 

 

 

 

 

 

 

п

 

1=0

 

Рп

 

 

 

 

Очевидно, при любом

алгорифм

является

функ­

цией,

обращающейся

в

нуль

на

сегментах

Ф(0), . . .

Ф(п) .

Кроме

того,

Рп

неинтегрируема

по

Риману

на О Д

1 (поскольку / 6

неинтегрируема, а все В\

интегри­

руемы на ОД 1).

 

 

 

 

 

 

 

 

 

 

 

Пусть f — функция,

тождественно

равная

нулю. По­

строим

по

лемме

1 алгорифм

у

так,

что выполняется

Md (/, F, Ф, у).

Пусть алгорифм, невозможность которого утвер­ ждается, построен. Обозначим его через U и построим алгорифм О так, что

U(P)~U(£yP3).

Тогда, очевидно,

Ш(Р)^1\Ь(Р),

что невозможно.

 

т е о р е м ы

4. Построим

алго­

Д о к а з а т е л ь с т в о

рифм F так, чтобы

 

п

 

 

 

 

F(n,

 

х).

 

 

* ) = 2 Я ( / ,

 

 

 

 

1=0

 

 

 

При

всяком п, i ^

п

и х ен O(i)

 

 

 

F(n,

x) = H(i,

x)=*U(x).

 

Следовательно, можно построить алгорифм у так, что

 

 

Md(/ 6 , F,

у).

 

 

Пусть алгорифм, невозможность которого утвер­

ждается

теоремой,_ построен и

обозначен через U,

По­

строим

алгорифм U так, что

 

•

 

Тогда

 

U(P)c*U(£yP3).

 

 

 

 

_

 

 

 

 

1С/(Р)^"1 !£(/>),

что невозможно.

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