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

200

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

[ГЛ. 4

Ниже, говоря про алгорифмы, определенным

образом

ности)

систем линейных уравнений.

Т е о р е м а

5.

При

любом

п ^

1

невозможен

алго­

рифм,

применимый

ко

всякой

системе

линейных

уравне­

ний

с

п неизвестными

и

аннулирующий

те и

только те

системы,

которые

совместны.

х)

Рассмотрим линейное

уравнение

(с

неизвестным

вида

[Л)

\v\-x=v.

Л е м м а

4.

Невозможен

алгорифм,

перерабатываю­

щий

всякое

КДЧ

v

в

КДЧ,

удовлетворяющее

уравне­

нию

(4).

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

Пусть

такой

алгорифм

а

по­

строен. Построим

алгорифм а' такой, что

а » ~ Р з ( о ,

у ,

а (о)).

По

определению

а

и

свойствам

алгорифма

Рз

(тео­

рема

21 § 3 гл. 2)

мы

получаем,

что

а'

перерабатывает

всякое

КДЧ

v

в

1 или

в 2,

причем если

а'(у)

— 1,

то

а ( у ) < у ,

и

если

а'(о) =

2,

то

а ( а ) > 0 .

Однако

из

a (v)

<

вытекает,

что

v ^

0,

а

из

a(v)

>

0

вытекает

v ^

0.

Таким

образом,

а'

указывает

при

любом

v

вер­

ный член

дизъюнкции

( У < 0 )

V(v>0),

что

невозможно.

При

любом

п ^

невозможен

алго­

Т е о р е м а

6.

1

рифм,

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

всякую

совместную

систему

линейных

уравнений

с

п

неизвестными

в

какое-нибудь

решение

этой

системы.

§ 1]

ПРОБЛЕМЫ,

СВЯЗАННЫЕ

С ОТНОШЕНИЯМИ

ПОРЯДКА

201

Вектор х\, ...,

хп

назовем ненулевым, если

i

х\ Ф 0.

Л е м м а

5.

Можно

построить

алгорифм,

указываю­

щий

для

любого

ненулевого

вектора

Х\

хп

верный

член

дизъюнкции

(*i Ф

0) V (х2

Ф 0) V . . .

\/(хпф0).

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

Пусть х\

п

хп — ненулевой

вектор. Обозначим

для

краткости

2

А

через

X.

Ясно,

что I >

0 и что не могут одновременно

выполняться

вое

неравенства

х2< —

( l < i < n ) .

X

X

Поэтому алгорифм Рз хотя бы одно из слов

,

— ,

х2{

(где

1 ^

i

^

п)

перерабатывает

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

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

a(*i.

* „ ) ^ ц / ( 1 < * < л & Р з ( - | ^ ,

jf,xfj

=

2]j,

применим к любому ненулевому вектору х\,

хп

и

перерабатывает

его

в

одно

из натуральных чисел

от

1

до п, причем, если а(хх

xn)

=

i,

то

х2{

>

>

0.

Лемма доказана.

[6]). При

любом

п ^

не­

Т е о р е м а

7

( Ц е й т и н

2

возможен

алгорифм,

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

всякую

систему

п линейных

однородных

уравнений

с

п

неизвестными,

имеющую

нулевой

определитель,

в

ненулевое

решение

этой

системы.

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

рассмотреть

слу­

чай

п =

2.

Рассмотрим

произвольную

систему

(с

неиз­

вестными х,

у)

вида

(и • х +

v • у =

0,

( '

[и • х + v • у = 0

(где

и,

v — произвольные

КДЧ) .

Если

бы

алгорифм,

о котором идет

речь в

теореме, был возможен, то

мы

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.