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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

2С4

КДЧ; НЕВОЗМОЖНОСТЬ НЕКОТОРЫХ АЛГОРИФМОВ

ГГЛ. 4

слова Р

а'(Р)~а(£%Р1)

(где 91— алгорифм, построенный согласно лемме 1). Фиксируем произвольное Р и рассмотрим два слу­

чая: а) !ф(Р); б) ~\\$>{Р). В каждом из этих случаев, ввиду леммы 1, 21Р является ПРЧ, удовлетворяющей условиям теоремы. Следовательно, в каждом из этих случаев а' перерабатывает Р в О-индикатор фундамен­ тальности ПРЧ 21р.

Очевидно, в случае б)

(1)

Я(Я,а'(Р))=т=0.

Рассмотрим случай а). Пусть $ заканчивает работу над Р точно за k шагов. Если а'(Р) < к, то, очевидно,

191 (Л а'{Р))-%(Р,

к) |=^=1,

что невозможно, так как а'(Р) — О-индикатор фундамен­ тальности ПРЧ 91р. Следовательно, a'(P)^k и, таким образом, в случае а) выполняется

(2)

 

21 (Р, о/(Р))^=1.

 

 

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

а " такой, что

 

 

 

 

а " ( Р ) ~ 2 Ц Р ,

а'(/>)).

 

 

Ввиду

(1) —(2) при

любом

Р

выполняется

 

1) если ~М£(Р), то !а"(Р)

и

а"(Р) =

0;

 

2) если !&(Р), то !а"(Р) и

а" (/>)=?= 1.

 

 

Это, однако, в силу леммы 2 невозможно.

 

Из теоремы

1 вытекает

 

 

 

 

Т е о р е м а

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

алгорифм,

перерабаты­

вающий запись

всякой

фундаментальной

ПРЧ

в запись

регулятора

фундаментальности

этой ПРЧ.

 

Теорема 2 доказана

Г. С. Ц е й т и н ы м в

работе [6],

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

теорему 8, п. 2 данного параграфа).

 

Читатель без труда может убедиться,

что в теоре­

мах 1 и 2 вместо фигурирующих там ПРЧ

можно рас­

сматривать ПРЧ, обладающие всеми прежними свой­ ствами и, сверх того, сходящиеся к 0. (Для доказатель-

§ 2) ПРОБЛЕМЫ, СВЯЗАННЫЕ с о с х о д и м о с т ь ю 205

ства усиленных таким образом теорем 1—2 нужно не­ сколько модифицировать лемму 1.) Другими словами, знание предела сходящейся ПРЧ, вообще говоря, не об­ легчает нахождение эффективной оценки скорости схо­ димости этой ПРЧ.

Т е о р е м а

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

алгорифм

у, перерабаты­

вающий

запись

всякой неотрицательной

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

числом

1 сходящейся

ПРЧ р в конструктивное действи­

тельное

число

таким

образом,

что если х является пре­

делом р, то

U - Y ( E P 3 ) K y .

Д о к а з а т е л ь с т в о . Пусть такой алгорифм у по­ строен. Построим алгорифм у' так, что

Y ' ( P ) ^ Y ( C % 3 )

(где 91— алгорифм, фигурирующий в лемме 1). Фиксируем произвольное Р и рассмотрим случаи:

а) !§(Р); б) ~|! £ ( Р).

В каждом из этих случаев ПРЧ 91Р удовлетворяет воем условиям теоремы и поэтому у' перерабатывает Р в КДЧ. Кроме того, поскольку в случаях а) и б) 91Р сходится соответственно к 1 и к 0, то

1)

если

!#(Р), то

 

(3)

 

\ V ' ( P ) - U < Y -

2)

если

~1!#(Р), то

 

(4)

 

 

\y'(P)\<Y-

Построим алгорифм у"

так, что

 

 

Y " ( ^ ) ^ s g n (у'

(P)--jj-

Тогда ввиду (3) и (4) получаем

1)если !&(Р), то у"(Р)== 1;

2)если ~]!Ф(Р), то у"{Р)^ — \, что невозможно.

206

КДЧ; НЕВОЗМОЖНОСТЬ

НЕКОТОРЫХ АЛГОРИФМОВ

[ГЛ. 4

Т е о р е м а

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

алгорифм,

перерабаты­

вающий

запись

всякой

сходящейся ПРЧ в

КДЧ,

к кото­

рому она

сходится.

 

 

 

 

 

Эта теорема является тривиальным следствием пре­

дыдущей.

В работах

М и н ц а

[1] — [2] теоремы

2 и 4

распространены на случай

произвольных

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

ных метрических пространств, содержащих по крайней мере две различные точки.

Отметим, что теорема 3 является довольно точной:

очевидно, число ~ отличается от предела любой фигу­

рирующей в ее формулировке ПРЧ

не более чем на у .

Интересно сопоставить

теоремы

3

и 4 с теоремой

о полноте конструктивного

континуума

(§ 2 гл. 3). В до­

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

ной ПРЧ

 

информации.

 

 

 

 

 

 

 

 

 

Переформулируем полученные результаты в терми­

нах F-чисел и квазичисел.

 

 

 

 

 

 

 

 

 

Пусть

оси — по-прежнему

(ср. п.

4

§ 3

гл. 2)

алго­

рифм такой, что для любого слова Q е

Ч

 

 

 

 

_

f

Q,

если

О

не

входит

в

Q,

 

 

 

 

 

 

1 Q,,

если

Q^QlOQ2

и

О

не

входит

в Qx.

 

О п р е д е л е н и е

2. Будем

говорить,

что

слова

Qi,

Q2

имеют одинаковую

основу,

если

 

 

 

 

 

 

 

 

 

 

 

ocH(Qi) =т= O C H ( Q 2 ) .

 

 

 

 

 

Пусть

— некоторое

«-местное

отношение

над

кон­

структивными действительными числами.

 

 

 

 

О п р е д е л е н и е

3. Будем

говорить,

что слова Ри ...

...,

Ph

(где

0 <

k

п)

вместе

с

КДЧ

xk+l,

хп

условно

выполняют

зФ, если для любых

КДЧ

хи

xk

§2]

 

ПРОБЛЕМЫ,

СВЯЗАННЫЕ CO СХОДИМОСТЬЮ

 

207

с той же основой,

что Pif

. . . , Ph,

 

выполняется

 

 

 

 

 

 

 

бФ ( х ь

. . . ,

xk, xk+{,

 

...,

 

хп).

 

 

 

 

Прилагательное «условно» часто будет опускаться.

В частности, F-число q (условно)

равно

КДЧ

х,

если

всякое

КДЧ с той же

основной,

что

и (/

(а

такие

КДЧ

по определению F-чисел существуют), равно (в смысле

отношения

= )

х.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

з>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Непосредственно из теорем 2 и 4 вытекают следую­

щие

утверждения

( Ц е й т и н

[6]

и М и н ц

[1] — [2]).

 

Т е о р е м а

5.

Невозможен

 

алгорифм,

 

перерабаты­

вающий

всякое

F-число

в КДЧ

с

той же

основой.

 

Т е о р е м а

6.

Невозможен

 

алгорифм,

 

перерабаты­

вающий всякое F-число

в равное

ему

КДЧ.

 

 

 

 

Поскольку всякое F-число является квазичислом, по­

лучаем

 

 

 

 

Невозможен

 

алгорифм,

 

перераба­

С л е д с т в и е

1.

 

 

тывающий

всякое

квазичисло

в

КДЧ

с той же

основой.

С л е д с т в и е

2.

Невозможен

 

алгорифм,

 

перераба­

тывающий

всякое

квазичисло

в

равное

ему

 

КДЧ.

 

2. В связи с результатами п.

2 §

2

гл.

3

интересна

следующая

дополняющая

эти результаты

теорема Ц е й-

т и н а [6].

 

 

Каково

бы

ни

было

КДЧ

и,

невозмо­

Т е о р е м а

7.

жен

алгорифм,

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

запись

всякой

вло­

женной

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

сегментов

с

длинами,

не

меньшими

и,

в КДЧ,

принадлежащее

 

всем

сегментам

этой

 

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

 

 

 

 

 

 

 

 

 

 

 

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

Рассмотрим,

например,

случай

и =

1.

Покажем,

что

к

задаче

построения

фигурирую­

щего в теореме алгорифма сводится задача

пополнения

непополнимого алгорифма %.

 

 

 

 

 

 

 

 

 

 

Построим алгорифм 23 (ср. лемму

1 § 1)

так, что для

любого слова Р е

7ои любого п

 

 

 

 

 

 

 

 

 

 

 

 

• 0 A3,

 

если

 

[ЩР,п)=£А,

 

 

 

 

 

8 ( Р , п ) = ? '

0 Д 1 ,

если

№(P,n)=FA

 

 

и

 

g(P)==0,

 

 

 

2 Д З ,

если

№(Р,п)^А

 

 

и

 

g(P)=v= 1.

Очевидно, при любом Р алгорифм 53Р является вло­ женной последовательностью сегментов с длинами, не меньшими 1, причем

208 КДЧ? НЕВОЗМОЖНОСТЬ НЕКОТОРЫХ АЛГОРИФМОВ [ГЛ. 4

а)

если

~1 l§ (Р), то при

любом

i

 

 

 

 

 

 

 

 

 

23(Р, 0=^=0 Д З ;

 

 

 

 

 

б)

если

$

заканчивает

работу

над

Р

точно

за

k

шагов

и g(P)=rO,

то при

i^k

 

 

 

 

 

 

( 5)

 

 

 

8 ( Р , 0 = г О Д 1 ;

 

 

 

 

 

в)

если

3

заканчивает

работу

 

над

Р

точно

за

k

шагов

и Ъ{Р)=^\,

то при

i ^ k

 

 

 

 

 

 

(6)

 

 

 

23(Р, ( ) = ? 2 Д 3.

 

 

 

 

 

 

Предположим,

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

о

котором идет

речь

в теореме, построен. Тогда можно построить алгорифм ф, перерабатывающий всякое слово Р в КДЧ, принадлежа­ щее всем сегментам последовательности 23р. Построим алгорифм q/ так, чтобы

 

 

Ф ' ( Р ) ~ Р з ( 1 ( 2, Ф ( Р ) ) - 1 .

 

 

 

Очевидно, ф' перерабатывает

всякое Р в 0 или в 1.

Пусть

 

Если 3 ( Р ) = = 0 ,

то, ввиду

(5), Ф ( Р ) = ^ 1

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

Рз (1, 2, Ф ( Р ) ) =

1.

Таким

образом,

ф ' ( Р ) = 0 . Аналогично

показывается, что из

S(^> )=f=l

следует

ф ' ( Р ) = 1 .

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

ф'

является попол­

нением S, что невозможно.

 

 

 

 

 

 

С л е д с т в и е

3.

Невозможен

алгорифм,

перерабаты­

вающий

запись

всякой

вложенной

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

сегментов

в КДЧ,

принадлежащее

всем

сегментам

этой

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

 

 

 

 

 

7 при и — 0.

Это следствие

получается из

теоремы

Отметим,

что

из

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

теоремы

7 видно,

что

в ее формулировке

(так же, как

и в

 

формулировке

следствия 3) вместо произвольных вложенных последо­ вательностей сегментов можно было бы рассматривать вложенные последовательности рациональных сегментов.

В связи с теоремой 7 возникает вопрос о существова­ нии вложенной последовательности сегментов, для кото­ рой было бы невозможно КДЧ, принадлежащее всем сегментам этой последовательности. То что этот вопрос не праздный, показывает существование соответствую­

щих контрпримеров в случае метрических

пространств

(см. Г е л б а у м , О л м с т е д [1J) и теорема

З а е д а в -

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