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

ПРИМЕР ШПЕКЁРА

181

2)

если

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

число

и

существует

i

та­

кое, что 0 <

i <

Р(Р +

1)

и a(t) =r= Р,

то

35 (Р) =F Л ;

3)

если

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

число

и для

всех

t

таких,

что 0 ^

i ^

р(Р + 1),

выполняется

a ( i ) v #

Л

то

5) (Р) =?= 0.

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

в { 0 | } . По­

кажем, что P e l s

®(Р) ==Л.

а)

Пусть

55(Р) == Л . Тогда

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

число

и при некотором i таком, что 0 ^

i ^

Р(Р + 1), OC(/)=FP.

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

P e i .

б)

Пусть

P e l .

Тогда

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

число

п

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

/

a(j)==

Р. Ввиду (4) при f >

Р(Р +

П

выполняется

ос(/)> Р. Следовательно,

0

/ ^

р(Р +

1)

и 5>(Р) == Л .

Таким образом, регулятор фундаментальности © не­

возможен.

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

©,

построенная

Т е о р е м а

2.

согласно

теореме

1, не сходится

ни к какому

КДЧ.

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

Если

бы

©

сходилась

к

ка­

кому-нибудь КДЧ, то согласно теореме 7

§

1 последо­

вательность © была бы фундаментальной.

О п р е д е л е н и е

1. Пусть

а,

р— ПДЧ.

Будем

гово­

рить,

что р я&ляется

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

а,

если

можно

построить возрастающую

ПНЧ

у

так, что при

любом

п

Р(л) =

а(у(я)).

Вполне

очевидна

Л е м м а

1. Если

ПДЧ

а

сходится

к

некоторому

КДЧ,

то любая

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

а сходится

к это­

му же КДЧ.

В случае монотонных ПДЧ имеет место обратное ут­

верждение.

Если

какая-нибудь

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

Л е м м а

2.

ность монотонной

ПДЧ

а

сходится

к некоторому

КДЧ,

то а сходится к этому же КДЧ.

а. — ПДЧ,

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

Пусть

р—возрас­

тающая

ПНЧ и а 1 — т а к а я

ПДЧ, что при любом п

а'(л) =

а(Р(л)).

182

КОНСТРУКТИВНАЯ

сходимость

[ГЛ. 3

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

что

р1 — регулятор

сходимости

а1

к

некоторому КДЧ х .

Построим ПНЧ

р2

такую, что

Р2(/г) =

Р(Р'(п)).

Покажем, что р2 является регулятором

сходимости

а

к х.

а — неубывающая

Пусть,

например,

ПДЧ.

Тогда,

очевидно, а 1 — также

неубывающая ПДЧ. Следователь­

но, при любом i

а1 (г) <

х.

Пусть теперь при произвольном п натуральное число i

таково, что i ^

Р 2 (я) . Тогда

а(/)>а(р(р'(п))).

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

а (0 >

а1 (р1 («)).

Поскольку ПНЧ р возрастает, можно найти / такое,

что

Р ( / ) > * .

Тогда мы получим

и так

как

а' (Р'(я)Х а

О'Х «' ( / ) < * ,

(р1 (л)) <

то

х-а'

2~п,

U - a ( i ) r <

2"",

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

Из теоремы 2 и леммы

2 немедленно вытекает

Т е о р е м а

3.

Никакая

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

ПРЧ

<& (построенной

согласно

теореме 1)

не

является

сходя­

щейся.

ПДЧ

назовем

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

О п р е д е л е н и е

2.

а

если

осуществимо

КДЧ

х

такое,

что при

всех i

\a(i)\^.x

(мы

будем

также

говорить,

что КДЧ

х

ограничивает

ПДЧ

а).

ПДЧ а такую, что

О п р е д е л е н и е

3.

184

КОНСТРУКТИВНАЯ с х о д и м о с т ь

[ГЛ. 3

2.

О п р е д е л е н и е

5.

Будем

говорить, что ПДЧ

а

псевдосхо-

дится

к КДЧ

х,

если

V« ~1 "1 3mVZ (l >m

=> | * -

а (/) | < 2~").

Имеет

место

следующая

теорема

(М а з у р [1]).

Т е о р е м а

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

ПРЧ,

псевдосходящуюся,

но не

сходящуюся

к

нулю.

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

Пусть

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

полный алго­

рифм,

перечисляющий

без

повторений

некоторое

неразрешимое