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

ТЕОРЕМЫ НЕВОЗМОЖНОСТИ

АЛГОРИФМОВ

343

Пусть

\D(P).

Тогда

IV(Р) и Ф заканчивает

работу

над Р

точно за

V(P)

шагов. Если

а ( х ) <

V (Р),

то

\Ъ](Р,а(х))^Л,

и так

как

а, (х),

а2(х)

^а(х)

и

то

у (Я, x)~f(<f(x))

=

F(V(P),<p(x)).

В

случае, когда

a(x)^V

(Р),

у(Р,

x)~F(V(P),

q>(*)).

Таким

образом,

при всяком х

у(Р,

x) =

F(V{P),v{x)),

что при х е О А

1 дает

у(Р,

x) =

F(V(P),

х).

Осталось показать, что при любом Р

ур

является

функцией. Пусть х = у и

у(Р,

х)>у(Р,

у).

Аналогично,

Y (Р,

х)

У)-

х)>у(Р,

у).

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

у(Р,

< у (Л

Y (Р,

х) =

у (Р,

у),

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

Заметим,

что

при любом Р

ур

(х) =

=

YP(°) П РИ х < 0

и YP(^) =

Y P ( 0

П Р И

х^1.

Нам понадобятся некоторые вспомогательные по­

строения.

Построим последовательность D положительных ра­

циональных дроблений

сегмента О Л 1 такую,

что

я ф (я)) < 2""

и

рациональные числа

rh

st

( O ^ t ' ^ n )

входят

в

D{n).

(Алгорифм я введен в

§

1 гл. 7.)

Ъ{П)

=Ftn,0*

. ..*•//»,

kn

(где 0 =

г„, о <

tn,

1 <

• • • <

ft„

= 1 и все /„, , — рацио­

нальные

числа).

D{

п и

Построим

алгорифм

так,

что

при

любом

0 < / < £ „ -

1

О,

если

сегмент

г„,, Д / „ ,< + 1

входит

в ка­

D, (п, /) =?=

кой-нибудь из сегментов Ф(0),

Ф(«);

I

в

противном

случае.

Пусть

Q — тот

же

самый

алгорифм,

что и

в

§ 2

(см. рис. 17).

Обозначим через ф алгорифм в алфавите Ча со сле­

дующим

свойством: невозможен

алгорифм

91 над Ч0 та­

кой, что при любом Р <= Ч0

!И (Я) s

i

!$(/>).

Т е о р е м а

1.

Невозможен

алгорифм,

перерабаты­

вающий

запись

всякой

полигональной,

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

числом 1 функции

f такой, что

O - J f .

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

число,

являющееся

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

инте­

грируемости

этой

функции

на

О Л 1

(см. определение 1

§ 3 гл. 7).

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

Обозначим

на время

доказа­

тельства

tn,tA

' " • » + 2 ' « ' ' + 1

через

ап,{,

in,,

+ b.t+r

A

t

n

{

ч е р е з

К

и

t n

, i + t n

A +

l

~ t

n A

через

сп,и

tn,i

+

' * ' { t

n ' i +

r t n

' l

)

через

dnil.

ТЕОРЕМЫ

НЕВОЗМОЖНОСТИ

АЛГОРИФМОВ

345

Построим алгорифм F так, что

(1)

F (я, х) =

S

А

(я,

0 • (Qe „. , W -

& я > ,

(*)).

Очевидно, Р является последовательностью функций,

причем

на каждом

сегменте tn< г- Д

tfn>

i + 1

(2)

Fn (х) =

Dl

(п,

i) • (Qan

t

(х)

-

йьп

. (JC)).

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

(3)

К(с*,)=1.

Fn(dn,i)

=

-

L

Из

(1) — (2) получаем,

что Рп

— полигональная функ­

ция, ограниченная

числом

1 и обращающаяся

в 0 на

сег­

ментах Ф(0),

Ф(п).

При

этом, очевидно,

0 -

/ 4 .

о

Пусть f — функция,

тождественно

равная

0 на

всей

оси. Применяя к /,

F и §

лемму

1, получаем

алгорифм

у такой, что выполняется

(4)

Md(/, F,

£>, у).

(5)

a1(P)a5=or(EYp3).

Пусть алгорифм о2 таков, что для любого Р в Ч0

(6)

\о2(Р)^Р=£Л.

(7)

ЩР)^оЛШР,<*ЛР))),

и покажем,

что

(8)

1 Я ( Р ) ^ - | ! $ ( Р ) .

346

СИНГУЛЯРНЫЕ ПОКРЫТИЯ

[ГЛ. 8

Далее согласно (4) всюду на ОД 1

М*) = /(*) = о.

Поэтому lei(P) и oi(P)—натуральное

число. Следова­

тельно,

и

((6)) выполняется !21(Р).

Пусть теперь !21(Р). Предположим, что \$>(Р), и

обозначим через k число шагов, затрачиваемое

алгориф­

мом § на слово Р. Согласно (4) всюду на 0 Д 1

(9)

k > а, (Р),

•Si =5=8/3»

DW)>

Cn,0*Cn,\*

. . .

*С„,ьп-1,

•S2= = = 8/3.

dn,o*dn,i*

. . .

*dn,kn-\.

(Ю)

a(s 2 ) - a(s, ) = 2 . ( i - i i < D ( Q i ) > 1.