книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

202

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

[ГЛ. 4

могли бы построить алгорифм ф, перерабатывающий

вся­

кое

слово

и, v в ненулевое

решение

(5). Обозначим че­

рез

x U i „

и уи, v первую и вторую компоненты

вектора

ф(ы, v).

Пользуясь леммой 5, построим алгорифм ф',

указывающий для любых и,

v верный

член дизъюнкции

(хи. 0ФО)У

(уи,

„ Ф

0).

Пусть

теперь и и v таковы, что u-v = 0. Тогда из

хи,

v Ф 0

следует, очевидно, что и =

0

(иначе

v — 0 и

ф(«, У ) не является решением

(5)),

а

из Уи,х>Ф§

сле­

дует У =

0.

Таким образом, ф' для любых и, v таких, что u-v = 0,

указывает верный член

дизъюнкции

(ы =

0) V (о = 0),

мость

произвольного многочлена

(над полем КДЧ) .

5)

Невозможен

алгорифм, разлагающий произволь­

ный многочлен на

неприводимые

(в поле КДЧ) множи­

тели.

ПРОБЛЕМЫ,

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

203

ним к Р, то все члены

отвечающей

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

сти, начиная с некоторого места, равны 1.

Л е м м а

1.

Можно

построить алгорифм

91 таким об­

разом,

что для

любого

слова

Р

и

любых

натуральных

п,

k

если

~]!ф(Р), то

1)

ЩР,

п) =

0;

2)

если

!ф (Р) и f> заканчивает

работу

над

Р точно

за

k шагов

(см. п.

10 §

1

гл. 1), то при i < k

и при

всех

i~^k

я(/>, /) = о

9ЦР, /)=?= 1.

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

Искомый алгорифм

91 строит­

ся с помощью теоремы

разветвления:

0,

если

[ЩР,п)ф?\,

%

{ Р

'

П )

•

\ 1,

если

[ф](Р,

я) =

Л .

Очевидно,

91 обладает

нужными

свойствами*).

Нам потребуется следующая

очевидная

Л е м м а

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

алгорифм

а (над

Ч)

такой,

что для любого

слова Р

1)

если

~}\$(Р),

то ЩР) и

а(Р)^=0;

2)

если

\$(Р),

то la (Я)

и a ( P ) = £ 0 .

О п р е д е л е н и е

1.

Натуральное

число

п

назовем

k-индикатором

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

ПРЧ (ПДЧ)

а, если

при

любых

i, j ^

п

выполняется

| а ( 0 - а ( / ) | < 2 - \

Т е о р е м а

1.

Невозможен

алгорифм,

перерабаты­

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

любой

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

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

ной

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

числом

1 ПРЧ

в

0-индикатор

фунда­

ментальности

этой

ПРЧ**),

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

Пусть

такой

алгорифм

а по­

строен. Построим алгорифм а'

такой,

что для

любого

*)

Вместо ф в формулировке леммы мог бы фигурировать про­

извольный алгорифм.

всех п

**)

ПДЧ

а

мы

называем

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

при

0.

2С4

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

ГГЛ. 4

(1)

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

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

к) |=^=1,

(2)

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

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

а " такой, что

а " ( Р ) ~ 2 Ц Р ,

а'(/>)).

Ввиду

(1) —(2) при

любом

Р

выполняется

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

и

а"(Р) =

0;

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

а" (/>)=?= 1.

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

Из теоремы

1 вытекает

Т е о р е м а

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

алгорифм,

перерабаты­

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

всякой

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

ПРЧ

в запись

регулятора

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

этой ПРЧ.

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

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

работе [6],

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

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

что в теоре­

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

можно рас­

Т е о р е м а

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

алгорифм

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

вающий

запись

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

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

числом

1 сходящейся

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

тельное

число

таким

образом,

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

1)

если

!#(Р), то

(3)

\ V ' ( P ) - U < Y -

2)

если

~1!#(Р), то

(4)

\y'(P)\<Y-

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

так, что

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

(P)--jj-

206

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

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

[ГЛ. 4

Т е о р е м а

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

алгорифм,

перерабаты­

вающий

запись

всякой

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

КДЧ,

к кото­

рому она

сходится.

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

дыдущей.

В работах

М и н ц а

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

2 и 4

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

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

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

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

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

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

теоремы

3

и 4 с теоремой

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

континуума

(§ 2 гл. 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.

а)

если

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

любом

i

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

б)

если

$

заканчивает

работу

над

Р

точно

за

k

шагов

и g(P)=rO,

то при

i^k

( 5)

8 ( Р , 0 = г О Д 1 ;

в)

если

3

заканчивает

работу

над

Р

точно

за

k

шагов

и Ъ{Р)=^\,

то при

i ^ k

(6)

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

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

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

о

котором идет

речь

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

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

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

Пусть

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

то, ввиду

(5), Ф ( Р ) = ^ 1

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

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

1.

Таким

образом,

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

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

S(^> )=f=l

следует

ф ' ( Р ) = 1 .

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

ф'

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

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

С л е д с т в и е

3.

Невозможен

алгорифм,

перерабаты­

вающий

запись

всякой

вложенной

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

сегментов

в КДЧ,

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

всем

сегментам

этой

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

7 при и — 0.

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

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

теоремы

Отметим,

что

из

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

теоремы

7 видно,

что

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

(так же, как

и в

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

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

пространств

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

З а е д а в -

КДЧ И СИСТЕМАТИЧЕСКИЕ

ДРОБИ

209

с к о г о [4; теорема 4.1], дающая

пример

вложенной

сечением.

Отрицательный

ответ

на

поставленный

во­

прос вытекает

из следующей теоремы Г. С. Цейтина

(Ц е й т и н [6]).

Можно построить

алгорифм,

перераба­

Т е о р е м а

8.

тывающий

запись

всякой

вложенной

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

сегментов,

в квазичисло,

условно

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

всем

сегментам

этой

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

С л е д с т в и е

4.

Невозможна

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

вложенных

сегментов,

для

которой

не

существует

КДЧ,

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

всем

сегментам

этой

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

сти.

тельности

сегментов,

показывая, что дело здесь не

столько в

построении

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

сходимости этих приближений.

Такая

ситуация

часто

(но не

всегда — ср. К у ш н е р , Ц е й т и н

[1])

встре­

чается

в алгорифмических проблемах,

где

речь

идет

о нахождении КДЧ с некоторым

свойством, причем иско­

мое КДЧ не может не существовать.

пути

в

1936

г. Тьюрингом было введено одно

из

пер­

вых

понятий

вычислимого действительного числа

(Т ь го-

р и н г

[1]); вскоре, однако, Тьюринг констатировал,

что

новое определение

( Т ь ю р и н г

[2]), приводящее,

по су­

ществу, к понятию

вычислимого

действительного

числа,

счисления.

Круг вопросов, затрагиваемых в этом параграфе, по­

дробно

изучался

М о с т о в с к и м

[2]

и

У с п е н с к и м

[2] - [3].

Пусть

п — натуральное

число

и

О п р е д е л е н и е

1.

п >

1.

Слово

Q

назовем

п-ичной

дробью,

если

Q имеет

еид

't'&^O

п,

где

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

полный

алгорифм

(в

Ча)

такой, что 51 (0)

есть целое

число и

5i (i)

при

i ^ 1

есть натуральное

число,

меньшее

п. Слово

Q назовем

си­

стематической

дробью,

если

при

некотором k

(k

~> 1)

Q является

k-ичной

дробью.

Буква

х

(с

индексами или без индексов)

будет

ис­

Нетрудно построить алгорифм

ф 1

так, что при любом

я > 1 для любой я-ичной

дроби

£513 0 я и любого k

выполняется

к

(£5*3 On, k) =

51 (0) +

2

51 (/) • л - ' .

структивных действительных

чисел.

О п р е д е л е н и е

2.

1)

Будем

говорить,

что систе­

матическая

дробь т

равна КДЧ х,

и писать

х — х,

если

5>(т) =

х.

3>

Будем

говорить,

что систематические

дроби

Ть т2

2)

равны,

и писать х\ =

хг, если

2)(т,) =

£ ( т 2 ) .