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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

КДЧ И СИСТЕМАТИЧЕСКИЕ ДРОБИ

213

нальные числа (включая концы 21(0)). Поскольку каж­ дое г{ является концом некоторого базисного сегмента (в системе с основанием / ) , можно найти /, при котором

все rt являются концами базисных сегментов

ранга /

(в системе с основанием / ) . Тогда

сегмент

21(/)

включен

в точности в один из сегментов

г,- Л r,+i.

Этот

сегмент

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

2) Пусть не все простые делители т делят /. Тогда,

1

очевидно, число — не совпадает с концом никакого ба­ зисного сегмента системы счисления с основанием /.

Построим /-ичную дробь £ фЗО/, равную Эту

дробь обозначим на время доказательства через т. По­ строим алгорифмы гр и 0 так, что

 

 

•ф (л,

к)

 

Ф (k)

при

0 ^

к

^

п,

 

 

 

 

 

0

 

при

л <

к;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0 (л,

к)

 

ф(6)

при

 

0^.k^.n,

 

 

 

 

 

/ —- 1

при

л <

к.

 

 

 

 

 

 

 

 

 

 

 

 

 

Рассмотрим /-ичные дроби

Е"Ф«3 0 '

и

£8„3 0

обо­

значив

их соответственно

через т„

и х п .

 

 

 

 

 

Очевидно,

при любом

л

 

 

 

 

 

 

 

 

(1)

 

 

 

 

© ( T n ) < ^ - < S > ( f „ ) .

 

 

 

 

 

 

Пусть теперь $ ~

непополнимый алгорифм. Построим

алгорифм V типа (Ч0

-г* Ж) так, чтобы для любого

слова

Р е

Ч0

выполнялось

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

\V(P)

=

 

\%(P),

 

 

 

 

 

и

если

W (Р),

то

$

заканчивает

работу

над

Р

точно

за

V (Р) шагов.

 

 

 

 

 

 

 

 

 

 

 

 

 

Построим

далее

алгорифм

 

21 так, чтобы

 

 

 

 

 

[

 

 

Ф(т),

если

Ш(Р,

т ) # Л ,

 

 

21 (Р, т ) ~ |

${V(P),

 

т ) ,

если

Щ(Р,т)==Л

и

g(P)=0,

 

 

I

Q(V(P),

 

т),

если

[g](P, т)==Л

и

g ( P ) = l .

214

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

АЛГОРИФМОВ

[ГЛ. 4

 

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

Е ^ Р З О ^ является

/-ичной дробью. Обозначим эту дробь через Тр. Не­

трудно

убедиться,

что

 

 

 

 

1) если

1\Ъ(Р),

 

то

 

 

 

(2)

 

 

 

 

т Р

= т;

 

 

 

2 ) если

!g(P)

и

3 (Р) — 0, то

 

 

 

 

 

 

Тр = Т7

(р)

 

и,

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

ввиду

(1),

 

 

(3)

 

 

 

 

0 < т р < т

= ^ - ;

 

 

3) если

!§(Я)

и g ( P ) = 1, то

 

 

 

 

 

 

Тр = Т > (р)

 

и,

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

 

i

 

 

 

(4)

 

 

 

 

 

 

 

 

Для

произвольной

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

/==

=£ а 3 0 £ обозначим через {/},• целое число a(t). Предположим, что построен алгорифм 9i, сводящий

систему /-ичных дробей к системе m-ичных дробей. По­ строим алгорифм Зт/ такой, что

9 r ' ( P ) ~ 9 t ( T P ) .

Очевидно, 9?' применим к любому слову Р е V0 и перерабатывает всякое Я в m-ичную дробь, равную Тр. Построим алгорифм 9т/' так, чтобы

/ 1 , если {W (/>)}„> 0 и {W (/>)},><>, 1 0 в противном случае.

Ввиду (3), если \Щ(Р) и 3(Р)=рО, то 9х"(Р) = 0. Если же \%(Р) и ? ( Р ) - 1 , то, ввиду (4), -~ <9*'(Р) и,

следовательно, 9х"(Р)= 1.

Таким образом, 9т" является пополнением 3, что не­ возможно.

Следующее следствие является простым примером применения теоремы 2.

 

 

КДЧ

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

ДРОБИ

 

 

215

С л е д с т в и е

 

1.

1) Можно

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

пе­

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

всякую

десятичную

дробь

в равную

ей

двоичную

дробь.

 

 

 

 

 

 

 

 

 

2)

Невозможен

 

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

всякую

двоичную

дробь

в

равную

ей

десятичную

дробь.

 

Из теорем 1—2 легко следует

 

 

 

 

Т е о р е м а 3

 

( М о с т о в с к и й

[2],

У с п е н с к и й

[2] — [3] * ) ) . Каково

бы ни

было п >

1, система

КДЧ

не­

сводима

к системе п-ичных

дробей.

 

 

 

 

Из

теоремы

3

 

вытекает,

что для систематических

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

В заключение остановимся на естественно возникаю­ щем в связи с теоремой 3 вопросе о существовании КДЧ, для которых невозможны равные им n-ичные (при фи­ ксированном п) дроби. Отрицательный ответ на этот во­

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

 

 

Т е о р е м а

4.

Пусть

п>\.

Не существует КДЧ

х

такое, что невозможна

равная

ему

п-ичная

дробь.

 

Теорема

4 очевидным

образом

вытекает

из леммы 2

и следующей леммы.

 

 

 

 

 

 

Л е м м а

3. Можно

построить

алгорифм,

перераба­

тывающий

 

всякое

слово

вида х,

п,

где х —

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

ное КДЧ,

п >

1, в п-ичную

дробь, равную х.

 

 

Доказательство леммы 3 (и теоремы 4)

предостав­

ляется читателю.

 

 

 

 

 

 

 

*) При

п =

2 эта теорема была

по

существу

отмечена

еще

Т ь ю р и н г о м

[2].

 

 

 

 

 

 

 

Г Л А В А 5

КОНСТРУКТИВНЫЕ ФУНКЦИИ

§ 1. Основные определения. Некоторые примеры

1.

О п р е д е л е н и е

1.

Алгорифм

f в

алфавите

Ча

назовем конструктивной функцией

m

переменных

(m

^

^ 1), если

для любых

КДЧ

хи . , . , хт,

уи

..., ут

таких,

что

 

 

 

 

 

 

 

 

 

Х\—Уи

х2 — Уг> • • •» хт — Ут

и

!/(#!, ... ,

хт),

 

выполняется

 

 

 

 

 

 

 

 

1)

\!{Уи

•••» Ут);

 

 

 

 

 

 

 

2)

f(xu

хт) и

f(yu

ут)

суть

равные

КДЧ.

Непосредственно из определения усматривается, что конструктивная функция m переменных является алго­

рифмом типа (2)т

т> SD).

 

 

 

 

 

 

О п р е д е л е н и е

2. Будем

говорить,

что

конструк­

тивная функция

m

переменных

 

f определена

в

точке

Х\,

хт> если

\f(X\,

хт);

в

противном

случае

бу­

дем

говорить,

что f не определена

в этой точке.

 

 

 

Понятие

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

функции

было

введено

М а р к о в ы м

[5] и оказалось

весьма удобным

при по­

строении ряда

разделов конструктивного

анализа * ) .

Это понятие является естественным уточнением интуи­ тивных представлений о вычислимых (точечных) функ­ циях над КДЧ * * ) .

*) Наши определения отличаются от соответствующих опреде­ лений Маркова несущественными техническими деталями.

**) Более близким к реальной вычислительной практике пред­ ставляется аппроксимативный подход к определению вычислимой действительной функции, развивавшийся Г у д с т е й н о м [2], Ш п е-

к е р о м [1], Г ж е г о р ч и к о м

[2], [4], Л а к о м б о м

[1]. При этом

подходе исходными данными функции являются не сами КДЧ, а их

рациональные приближения:

параллельно уточнению

этих прибли­

жений

уточняются выдаваемые функцией приближения к резуль­

тату.

Вопрос о связи аппроксимативных и точечных вычислимых

 

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

217

Непосредственно из определений 1—2 следует, что

неопределенность

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

функции (скажем, од­

ной переменной)

в точке х связывается с

непримени­

мостью задающего ее алгорифма

ко всем

КДЧ, рав­

ным х. Такой подход не является единственно возмож­

ным (ср.

М а р к о в [3],

С л и с е н к о [3]). Мы еще

вернемся

к этому вопросу

в гл. 9.

В дальнейшем мы будем рассматривать в основном конструктивные функции одной переменной, называя их для краткости просто конструктивными функциями (КФ). КФ, определенную во всякой точке, будем назы­ вать всюду определенной. В тех контекстах, где явно не подразумевается противное, термин «функция» будет ис­ пользоваться нами как сокращение термина «всюду оп­ ределенная конструктивная функция».

Введем отношение условного вещественного равен­

ства

« ^ » :

два

выражения,

соединенные

знаком

« ^ » ,

либо

оба не определены, либо являются равными

КДЧ.

О п р е д е л е н и е

3.

Будем

говорить, что

КФ

fug

равны

(совпадают)

на

множестве КДЧ

Ж,

и

писать

f — g,

если

при

любом х из Ж

 

 

 

 

f(x)e*g(x).

Индекс Ж в тех контекстах, где это не приводит к не­ доразумениям, опускается.

Если КФ f и g равны на множестве всех КДЧ ЗУ, то будем просто говорить, опуская упоминание о множе­

стве 3), что f

и g

равны.

 

2. Приведем

некоторые примеры

конструктивных

функций.

 

 

 

. а) Простейшими примерами КФ

являются алго-

рифмы Id и

Idje

(где х — некоторое КДЧ) . Каково бы

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

вычислимых

функций, конструктивные функции напоминают

точеч­

ные функции

(в смысле Дирихле) традиционного анализа,

что де­

лает более компактными и привычными обозначения и несомненно облегчает первое знакомство с предметом.

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