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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

278

ДИФФЕРЕНЦИРОВАНИЕ

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

ФУНКЦИЙ

[ГЛ. 6

Тогда, ввиду

(1),

 

 

 

 

 

 

 

 

 

 

 

 

Отсюда очевидным образом вытекает, что

 

 

 

 

 

 

 

 

 

 

/ | Е ( / Д г .

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Имеем

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I f

-

f (/) -

Г (/) • (/,-01=1 (f (/,)-/

 

( у ) - / ' 0/) • (*,

- !/))+

+ (/

(у)

-

/ (0 -

/' (у) • (у -

 

0) + (/' М

-

/' (0) • (*. - 1 ) I <

<1/С,)-/(</)-/'(</)

 

 

 

 

1

 

+

 

1

1

+

 

 

 

 

 

 

 

 

 

 

 

+ 1 П я ) - П 0 1 - 1 ' 1 - * 1 .

Используя

(1)

и

определение

W3,

отсюда

получаем

\f(ti)-f(t)-f'(t)-{t>-t)\<

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

< |

f, -

/1 • (2~п-2

+

2 " 1 - 2 + 2 - " - ' )

=

2 _ "

• I r, — /1,

что противоречит предположению

(2).

 

 

 

 

Таким образом, из (2) вытекает, что

 

 

 

 

(4)

 

 

 

 

 

 

 

 

t<£xAy.

 

 

 

 

 

 

 

Точно так же из (2) следует, что

 

 

 

 

 

 

(5)

 

 

 

 

 

 

 

1фу

А

г.

 

 

 

 

 

 

 

Однако

(в

силу

леммы

1

§

2

гл.

5)

одновремен­

ное

выполнение

(4)

и

(5)

невозможно.

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

(2)

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

 

 

 

 

 

 

 

 

 

 

 

I / (/,) -

/ (0 -

Г (0

• (*1 - 1 )

I <

 

2""

• | /, -

/1,

что и требовалось.

 

 

 

 

 

 

 

 

 

 

 

 

Использование

леммы

 

«о

склеивании

конструктив­

ных функций»

(§

1 гл. 5)

и теоремы

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

поз­

воляет вывести из этой леммы

следующее

 

 

 

 

С л е д с т в и е

 

1.

Пусть

функции

 

f\, f2

являются

про­

изводными

функции

 

f

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

 

на

сегментах

х А у и у A z,

причем

 

 

 

 

 

 

 

 

 

 

 

П(у)=П(у).

 

 

НЕВОЗМОЖНОСТЬ НЕКОТОРЫХ

АЛГОРИФМОВ

 

279

Тогда

осуществима функция

f

такая, что

 

 

 

 

 

 

 

п о

 

 

'(О

 

при

 

 

t^.y,

 

 

 

 

 

 

 

|

/2 (0

 

ир«

 

г>г/,

 

 

 

и эта функция

является

производной

 

f

на х

Az.

 

 

Т е о р е м а

1

( Ц е й т и н

[6]).

 

Можно

построить

функции

f

и f

таким

образом,

что

 

 

 

 

 

 

1)

У является

производной

 

f на О А 1;

 

 

 

2)

невозможен

алгорифм,

 

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

всякое

слово

вида

х,

у,

где

х

и у — КДЧ

из

О Л 1 такие,

что

х < у,

в

КДЧ

из

ОД 1, придающее

f

значение,

равное

 

 

 

 

 

 

f(v)-f(x)

 

 

 

 

 

 

 

 

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

В

качестве

f

возьмем

ту

же

самую функцию, что и в теореме 1 § 4 гл. 5:

 

 

 

 

 

Г(х)

 

 

 

 

 

 

+

2 • х -

1.

 

 

Очевидно,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2-х-±

 

 

при

 

.

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(6)

п * ) = -

 

0

 

при

1

^

.

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 . * - |

 

при

 

 

 

 

 

 

В качестве / возьмем функцию такую, что

 

 

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

при

 

^

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(7)

 

f ( * ) =

 

(

 

 

при

 

 

 

 

 

 

 

 

 

 

 

1\2

при

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Используя (6) — (7) и лемму 1, легко показать, что функция /' является производной / на ОД 1,

280 ДИФФЕРЕНЦИРОВАНИЕ КОНСТРУКТИВНЫХ ФУНКЦИЙ [ГЛ. 6

Положим теперь

Уи — "е + ">

X a = j + U.

Очевидно, если | и | <

- i - ,

то хи , z/u е

0 Л 1, уи

— л;ц > 0

и

 

 

 

 

 

f(yu)-f(xg)

= ( " + б " )

" ( " " )

_ ц

 

г/а -

 

 

.2.

 

 

 

 

 

3

 

 

Таким образом,

если

бы алгорифм,

о котором идет

речь в утверждении

2)

теоремы, существовал,

то мы

смогли бы построить алгорифм а, перерабатывающий всякое и, для которого | и | < в КДЧ из 0 Д 1 такое, что

/' ( а (и)) = и.

Вдоказательстве теоремы 1 § 4 гл. 5 фактически уже было показано, что такой алгорифм невозможен. Действительно, располагая алгорифмом ос, можно по­ строить алгорифм а\ так, что

 

0 , ( 1 0 2 * Р з ( у ,

 

у , О ( И ) ) .

 

 

Поскольку П 0 > 0

при г > у и Г ( 0 < 0 при

 

алгорифм

а, указывает для

 

каждого и

такого,

что

| « | < - g - ,

верный

член

дизъюнкции

 

 

 

 

 

( ы < 0 ) V ( и > 0 ) ,

 

 

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

следствию

5 § 1 гл. 4.

 

 

С л е д с т в и е

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

алгорифм,

перерабаты­

вающий

всякое

слово

вида

£/3. £/'3> £ ^3 .

г^е f и f

—

функции

такие,

что f(0) =

f(l)

= 0, f — производная

f

на 0 А I, причем

выполняется

Пр (О А 1, /, f, №), в ЛД*/

цз 0 Д 1, придающее

f значение,

равное О,

 

 

 

 

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

НЕКОТОРЫХ

АЛГОРИФМОВ

 

281

Это

следствие

легко

выводится

из

теоремы

1 с

по­

мощью

рассмотрения вспомогательных

функций

 

 

Fx. y{t) = f{(y-x)-t

+

x)-(f

(у)

-

f (X)) -t-f

(X),

 

где x, у — произвольные

КДЧ

из О Д

1 такие, что х <

у,

a f—

функция, фигурирующая

в теореме 1.

 

 

В

§

1 мы отмечали,

что,

располагая регулятором

дифференцируемое™ в себе данной функции на данном промежутке, можно построить производную рассматри­ ваемой функции на данном промежутке. В связи с этим

возникает

вопрос

о

возможности

 

 

 

эффективного

вычисления

 

произ­

 

 

 

водных чисел

дифференцируемых

 

 

 

функций, исходя лишь из значе­

 

 

 

ний этих

функций

(т.

е.

 

распо­

 

 

 

лагая

лишь вычисляющим

 

функ­

 

 

 

цию алгорифмом). Нетрудно ви­

 

 

 

деть, что ответ на этот вопрос

 

 

 

отрицательный.

 

 

 

 

 

 

 

 

 

 

Т е о р е м а

2

( М и н ц

 

[1]—

 

 

 

[3]).

Невозможен

алгорифм,

пе­

 

 

 

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

запись

всякой

 

дифференцируемой

на

всей

оси

функции

 

в

КДЧ,

являющееся

производным

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

в 0.

 

 

 

 

 

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

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

 

Рассмотрим

ности

КФ

F

и

F'

такие,

 

что

F'(п, х)

' ( | х + 2 - " |

+

+ \х-2-п\-\2-х\)-2п-х

х{)-2"

 

 

 

(рис.

15),

 

 

 

 

 

 

 

 

0

 

 

 

 

при

— 2 п,

 

F(n,

X):

\П—1 X

+

х +

 

2~п- 1

при

- 2 _ " < x < 0 ,

 

 

•х2

+

х + 2' " r t

_ 1 при

0 < x < 2 ~ r t ,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

при

2 ~ " < j t .

 

С помощью леммы 1 нетрудно убедиться, что при

любом п функция

Fn

является

производной функции

Fn

на всей оси. Кроме того, при всяких п и х

 

 

(8)

 

 

 

 

М * ) | < 2 "

 

 

 

Пусть теперь § — тот же самый алгорифм с не­ разрешимой проблемой распознавания применимости

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