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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

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

ДРОБИ

209

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

пример

вложенной

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

сечением.

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

ответ

на

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

во­

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

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

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

 

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

алгорифм,

перераба­

Т е о р е м а

8.

тывающий

запись

всякой

вложенной

 

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

сегментов,

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

условно

 

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

всем

сегментам

этой

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

 

 

 

С л е д с т в и е

4.

Невозможна

 

 

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

вложенных

сегментов,

для

которой

не

существует

КДЧ,

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

 

всем

сегментам

этой

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

сти.

 

 

 

 

 

 

 

 

 

 

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

тельности

сегментов,

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

столько в

построении

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

к искомому КДЧ (такую последовательность согласно теореме 8 можно построить), сколько в оценке скорости

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

Такая

ситуация

часто

(но не

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

[1])

встре­

чается

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

где

речь

идет

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

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

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

 

 

 

§3. Конструктивные действительные числа

исистематические дроби

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

пути

в

1936

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

из

пер­

вых

понятий

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

(Т ь го-

р и н г

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

что

это понятие является недостаточно общим, и предложил

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

( Т ь ю р и н г

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

по су­

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

вычислимого

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

числа,

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

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

с систематическими дробями в той или иной системе

счисления.

 

 

 

 

 

 

 

 

 

 

 

 

 

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

дробно

изучался

М о с т о в с к и м

[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 (/) • л - ' .

Очевидно, для любой систематической дроби т алго­ рифм £>| есть ПРЧ и алгорифм Id (ld(k)~k при лю­ бом k) является регулятором фундаментальности этой ПРЧ.

Построим алгорифм 5) такой, что для любой систе­ матической дроби т

£ ( T ) ^ c " © J 3 0 E I d 3 .

Очевидно, Ъ перерабатывает всякую систематиче­ скую дробь в КДЧ. Алгорифм 5D осуществляет естествен­ ное вложение систематических дробей в систему кон­

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

чисел.

 

 

 

О п р е д е л е н и е

2.

1)

Будем

говорить,

что систе­

матическая

дробь т

равна КДЧ х,

и писать

х — х,

если

5>(т) =

х.

 

 

 

 

 

 

 

3>

Будем

говорить,

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

дроби

Ть т2

2)

равны,

и писать х\ =

хг, если

 

 

 

 

 

 

 

2)(т,) =

£ ( т 2 ) .

 

 

 

 

 

 

 

 

КДЧ

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

ДРОБИ

 

 

 

 

211

О п р е д е л е н и е

3.

I)Будем

говорить,

что

система

КДЧ

сводима

к системе

п-ичных дробей, если можно

по­

строить

алгорифм,

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

всякое

 

КДЧ

в

равную

ему п-ичную

дробь.

 

 

 

 

 

 

 

 

 

 

2)

Будем

говорить,

что система

п-ичных

дробей

 

сво­

дима

 

к

системе

КДЧ,

если

осуществим

алгорифм,

 

пере­

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

 

всякую

п-ичную

дробь

в равное

ей

КДЧ.

3)

Будем

говорить,

что система

п-ичных

дробей

 

сво­

дима

 

к

системе

k-ичных

дробей,

если

можно

построить

алгорифм,

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

всякую

п-ичную

 

дробь

в равную

ей k-ичную

дробь.

 

 

 

 

 

 

 

 

 

 

4)

Про

алгорифм,

фигурирующий

в каждом

из

разде­

лов

1)—3),

будем

говорить,

что он

сводит

первую

из

со­

ответствующих

систем ко второй.

 

п

 

 

 

 

 

 

Очевидно,

алгорифм

35 при любом

(п >

1)

сводит

систему п-ичных дробей

к системе КДЧ. Таким

образом,

выполняется

 

 

При

любом

 

 

система

 

п-ичных

Т е о р е м а

1.

п > 1

 

дробей

сводима

к системе

КДЧ.

 

 

 

 

 

 

 

 

 

Пусть п

>

1. Рассмотрим сегменты вида

-А- А

р

"t

1 ,

где р — любое

 

 

число, i — любое

 

 

га' га'

 

целое

натуральное

чис­

ло. Эти сегменты назовем базисными сегментами ранга i

для системы счисления с основанием

п.

 

 

21

О п р е д е л е н и е

4.

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

сегментов

назовем

п-правильной,

если

91 является

вложенной

по­

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

сегментов

и

при

любом i

сегмент

91 (i) является базисным

сегментом ранга

i для

системы

счисления

с основанием

п.

 

 

 

 

 

 

Ясно, что построение n-ичной

дроби, равной

данному

КДЧ, эквивалентно построению n-правильной последо­ вательности сегментов, общей точкой которой является

это К Д Ч * ) .

Точнее

говоря,

имеет

место

следующая

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

которой

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

телю.

 

1) Можно построить алгорифм

пере­

Л е м м а

1.

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

всякое

слово

вида

£213, п,

где п >

1 и

21 — п-правильная

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

сегментов,

в

*) Нетрудно понять, что непрекрываемость базисных сегментов любого фиксированного ранга является источником возникающих при таком построении затруднений.

212

 

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

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

[ГЛ. 4

п-ичную

 

дробь

такую,

что КДЧ

<D(S'(£2I3,

п))

при­

надлежит

всем

сегментам

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

21.

 

2)

Если

21 — п-правильная

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

сег­

ментов

и

КДЧ

х принадлежит

всем

сегментам

21,

го х

равно

п-ичной

дроби

 

£213. п ) -

 

 

 

 

 

3)

Можно

 

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

®2 таким

образом,

что при

любом

п >

1 для

всякой

п-ичной дроби т

алго­

рифм

 

Щ

является

п-правильной

 

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

сегментов

такой, что КДЧ

Ф(т)

принадлежит

всем

сег­

ментам

этой

 

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

 

 

 

 

 

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

из

леммы

1 усматривается

следую­

щая

очевидная

 

 

 

 

 

 

 

 

 

Л е м м а

2.

Можно

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

перерабаты­

вающий

всякое

слово

вида

г, п,

(где

г —

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

число « п > 1 )

в п-ичную

дробь,

равную

г.

 

 

Вопрос о сводимости друг к другу систем системати­ ческих дробей при различных основаниях счисления пол­

ностью

решается

следующей

теоремой

Мостовского —

Успенского.

2.

Система l-ичных дробей

тогда и

толь­

Т е о р е м а

ко тогда сводима

к

системе

m-ичных

дробей, когда

все

простые

делители

m

являются

простыми

делителями

I.

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

1)

Пусть

все

простые

дели­

тели m

делят

/. Тогда при некоторых i и k

 

 

 

 

 

 

t

=

6 •

m.

 

 

 

 

Следовательно, всякий конец базисного сегмента для си­ стемы счисления с основанием пг является концом неко­ торого базисного сегмента для системы счисления с ос­ нованием /. На этом простом замечании и основана кон­ струкция сводящего алгорифма * ) .

Пусть т — /-ичная дробь и 21 — соответствующая /-правильная последовательность сегментов. Очевидно,

21(0)

есть

сегмент

нулевого

ранга (в системе

с

основа­

нием

пг)

и 21 (0)

содержит

т. Чтобы

найти

базисный

сегмент 1-го ранга

(в системе с основанием пг),

содер­

жащий т,

разделим

21(0) на

пг равных

частей.

Обозна­

чим через г0, ..., rm

участвующие в этом делении

рацио-

*) Мы лишь излагаем соображения, лежащие в

основе сводя­

щего алгорифма. Строгое изложение можно найти

у М о с т о в ­

с к о г о [2] и У с п е н с к о г о [3].

 

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