Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

.pdf

Скачиваний:

Добавлен:

22.10.2023

Размер:

14.87 Mб

Скачать

☆

<<< < Предыдущая 8 9 10 11 12 13 14 15 16 17 18 1920 / 4520 21 22 23 24 25 26 27 28 29 30 31 32 > Следующая >>>

192

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

[ГЛ. 4

Л е м м а

1. Для

каждого

алгорифма

можно

по

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

3)^ типа (40-+2D)

так, что для

лю

бого

слова

1) если

~]!2)(Р),

то 5 Ы Р ) = 0;

!25(Р) и Ъ(Р) — 0,

з>

если

то 2 Ы Р ) >

если

!25(Р)

3 ) ( Р ) # 0 ,

то

Т>з>(Р)<0.

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

Используем

алгорифм

[25],

«разбивающий работу 55 на шаги»

(п. 10 § 1 гл. 1). По

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

V так, что

У ( Р ) ~ ц л ( [ 5 ) ] ( Р , га)== Л) .

При любом Р

! F ( P ) S ! D ( P ) ^ 3 / ( [ S ] ( P , /) = Л) .

Построим алгорифм 2)1 так, что

2)1 (Р, п)

2 " " _ I ,

если

[25](Р, л) #

Л ,

~ j

2 - t M P ) - 1

если

[ $ ](Р, л ) = Л

25(Р) = 0,

[ _ 2 - к ( Р ) - 1 )

е с л и

Г З ) ] ( р ; П ) = д

S)(P)^o .

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

алгорифм

2)], является ПРЧ.

Нетрудно также проверить, что при любом Р и /, m ^ л

|2)'(Р, т ) - 2 5 ' ( Р , / ) | < 2 ~ \ Поэтому алгорифм Id такой, что

Id (п) == л,

является регулятором фундаментальности ПРЧ 25J,. Искомый алгорифм 2)® строим так, что

я > Я ( Р ) = е £ > ) , З О Е И З -

Из сказанного выше следует, что этот алгорифм пе рерабатывает всякое слово Р в КДЧ.

Предположим, что ~1!25(Р). Тогда при любом п

[25] (Р, л) =£ Л

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

25'(Р, п)^2~я~\

§ I]	ПРОБЛЕМЫ, СВЯЗАННЫЕ С ОТНОШЕНИЯМИ					ПОРЯДКА	193
откуда вытекает,		что
		$ я	(Я) = 0.
Пусть теперь		!Ф(Я) и S)(P)=f= 0.			Тогда	IV(Я)	и при
п 5з	V(/>)	©"(Я, n) =		2 - K ( i 5 b	l .
		©"(Я, n) =		2 - K ( i 5 b	l .
Следовательно,
		Ш Я (Р) =	2 - ^ Н > 0 ,
чем	установлено	свойство	2)	алгорифма		Ф,®. Свойство

3)устанавливается совершенно аналогично.

Вдальнейшем мы будем использовать следующий со

кращенный оборот речи. Пусть si\,

sih — «-местные

отношения. Рассмотрим

дизъюнкцию

(1)

s4-x (х„ . . . , xn)V

si2

(*„ ....

хп) V

•••

. . . V stk{xu

хп).

Будем говорить, что алгорифм а указывает для лю

бых

КДЧ

х\,

хп

верный

член дизъюнкции (1),

если

он

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

всякое

слово

Х\,

. . . , хп

(где

все

Х{

— КДЧ)

в одно из натуральных

чисел от 1 до k,

при

чем если <х{х\, . . ., хп)~с,

то выполняется sii(xu

. . . ,

хп).

Будем

говорить,

что

алгорифм

а указывает

верный

член

дизъюнкции

(1) для

любых

КДЧ

хи

хп,

удо

влетворяющих

условию si,

если

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

лю

бое слово

хх,

...,

хп

(где

все Xi — КДЧ) такое,

что

вы

полняется

si(x\,

хп),

в одно

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

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

..., хп)

=?= i, то выполняется

StiiXi

х п

) .

При конструктивном

понимании

дизъюнкции

для

того,

чтобы утверждать,

что Vx(six

(х ) V «5^2(•*))> нужно

построить алгорифм, указывающий для каждого х вер

ный член дизъюнкции six	(х) V s4-2(x). Следовательно, ут
верждение "1 Vx (six (х)	V ^ 2 (#)) означает лишь невоз

можность такого алгорифма, тогда как при традицион ном понимании дизъюнкции это утверждение всегда свя зывается с существованием конкретного х, при котором выполняются 1sii(x) и "1 si2(х). Указанное различие в трактовке дизъюнкции приводит к внешней парадо ксальности некоторых формулировок, возникающей, по

7 Б. А. Кушнер

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

существу, вследствие обозначения одним и тем же зна

ком	разных логических	операторов.
Т е о р е м а 1. Невозможен			алгорифм,	применимый к
КДЧ	х тогда и только тогда, когда х = 0.
Д о к а з а т е л ь с т в о .		Предположим,		что построен
алгорифм ф такой, что
(2)	[<р(*) =		* = 0.

Построим алгорифм $д> согласно лемме 1 и алго рифм ф' такой, что при любом Р в Ч0

Ф'(Р)~Ф(Ф<2 (Р)).

Поскольку, ввиду леммы 1,

&в(/>) =

0 ^ - 1 ! ф ( Р ) ,

то из (2) вытекает, что при любом Р в

Ч0

!ф'(Р)^ - )!ф(Р) .

Это, однако,

невозможно.

С л е д с т в и е

Каково

бы

ни было

КДЧ

у,

невоз

можен алгорифм,

применимый

КДЧ

тогда

только

тогда, когда х

у.

ф по

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

Пусть

такой

алгорифм

строен. Построим алгорифм ф' такой, что

Ф' (г) ~ ф ( 2 +

у).

Очевидно,

!q>'(z)B3z =

Это, как только что доказано, невозможно.

С л е д с т в и е

Каково

бы

ни было КДЧ у, множе

ство КДЧ,

равных

у (т.

е. вырожденный

сегмент

у А у),

не является

перечислимым

* ) .

Т е о р е м а

2. Невозможен

алгорифм,

указывающий

для любого

КДЧ

х верный

член

дизъюнкции

1) ( * = 0 )

у{хф0);

2) (* =

0) V (х>

0) V

( * < 0 ) .

*) Как уже указывалось в конце § 4 гл. 3, нетрудно показать, что это множество продуктивно.

§ 1]	ПРОБЛЕМЫ, СВЯЗАННЫЕ С ОТНОШЕНИЯМИ								ПОРЯДКА		195
(При конструктивном понимании дизъюнкции эти ут
верждения		можно соответственно записать как ~] У/х((х =
= 0)У(хфО))			и	-\|Vjt((* =			0 ) V ( * > 0 ) V ( * < 0 ) ) . )
Д о к а з а т е л ь с т в о .					Эта теорема			очевидным			обра
зом вытекает из теоремы 1.
Следствие			1 показывает,				что вместо 0		в	формули
ровке	теоремы		2 могло		бы фигурировать				произвольное
КДЧ, т. е. имеет место следующая
Т е о р е м а			3. Каково		бы ни было			КДЧ	у,	невозмо
жен алгорифм,			указывающий				для любого х верный				член
дизъюнкции
1)	(x = y)V(x¥=			у);
2)	(x =			y)W(x>y)\/(x<y).
Тем более			невозможен			алгорифм,		указывающий для
любых х, у верный член дизъюнкции 1), 2)									(т. е. ~]Уху
((х = у) V (х ф			у))	и ~[Чху{(х			=	у)у(х>у)\/(х<у)).
Ниже переформулировки							результатов,		аналогичные
теореме 3, опускаются.
Теорема		2	утверждает			неразрешимость следующей

алгорифмической проблемы: «построить алгорифм, ука зывающий для каждого КДЧ х верный член дизъюнк ции (х — 0) V (* ф 0)». Поскольку ни для какого х не может одновременно выполняться х = 0 и х Ф 0, то ал горифм, о котором идет речь в этой проблеме, должен для каждого х давать строго определенный резуль тат — 1 или 2. По-другому обстоит дело в следующей задаче: «построить алгорифм, указывающий для каж

дого КДЧ х верный член дизъюнкции (х^О)					V	(х^О)».
Здесь	интересующий		нас алгорифм	мог бы для некото
рых х	(именно, для		х = 0) указывать любой			член
дизъюнкции. Это, как кажется, увеличивает					шансы на
существование		такого	алгорифма. Тем не менее			приве
денная	только	что алгорифмическая		проблема, как по
казал	Ц е й т и н [6],		неразрешима.	Другими	словами,

имеет место следующее, более сильное, чем теорема 2, утверждение.

Т е о р е м а 4.	Невозможен		алгорифм,	указывающий
для всякого КДЧ х верный		член	дизъюнкции
	[х >	0) V {х < 0)
(т. е. ~ ] V J C ( ( A : > 0 )	V (*<0))) .
7»

196

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

[ГЛ. 4

Теорема 4 очевидным образом вытекает из следую

щей леммы

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

Л е м м а

Невозможен

алгорифм,

применимый

к любому

КДЧ,

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

всякое

положительное

КДЧ

не

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

никакого

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

КДЧ*).

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

Применив лемму

1 к непопол-

нимому алгорифму Ъ, построим алгорифм

Ъз>. Предпо

ложим, что существует алгорифм <р, применимый к

лю

бому

КДЧ,

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

всякое положительное

КДЧ

и не

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

никакого отрицательного КДЧ.

Построим

алгорифм

q/ такой, что для любого Р

<?'(Р)~<(®Я(Р)).

Очевидно, для любого Р ! ф ' ( Р ) .

Построим далее алгорифм ср" так, чтобы

Г 0,

если

q/(/>)==

Д ,

{

П ~

\ 1,

если

Ф ' ( Р ) #

Л .

Поскольку ф' применим к любому слову в Ч0, ф" также применим к любому слову в Ч0 и перерабатывает всякое слово в этом алфавите в 0 или в 1.

Пусть \Ъ(Р) и $ ( Р ) = 0. Тогда по лемме 1 %&(P) > 0. Следовательно, ф ' ( Р ) = Л и ф"(Р)=г=0. Таким образом,

Ф " ( Р ) = 3 ( Р ) .

Предположим теперь, что ! § ( Р ) и $ ( Р ) = 1 . Тогда Ъз>{Р)<0, и потому ф ' ( Р ) ^ Л . Следовательно, ф " ( Р ) = 1 . Тем самым Ф"(Р)=Т=3(Р)-

Итак, мы доказали, что ф" является пополнением Ъ относительно Ч0. Это, однако, невозможно.

Отметим, что тогда как при доказательстве теоремы 2 мы воспользовались существованием алгорифма с не разрешимой проблемой распознавания применимости, для доказательства теоремы 4 потребовался более тон кий результат — существование непополнимого алго рифма.

Предоставляем читателю доказать следующее усиле ние леммы 2: для любого алгорифма, применимого ко

*) Мы говорим, что	алгорифм аннулирует данное слово, если
он перерабатывает его в	пустое	слово.	КДЧ х называется положи
тельным (отрицательным),	если х	> 0 (х	< 0).

§ 1] ПРОБЛЕМЫ, СВЯЗАННЫЕ С ОТНОШЕНИЯМИ ПОРЯДКА 197

всякому КДЧ и аннулирующего всякое положительное КДЧ, можно указать отрицательное КДЧ, аннулируемое этим алгорифмом.

Из леммы 2 и теоремы 21 § 3 гл. 2 вытекает уже упо

минавшаяся

раньше

невозможность

«доопределения

в нуле» алгорифма

sgn.

С л е д с т в и е

3.1)

Невозможен

алгорифм

а,

приме

нимый

любому

КДЧ

такой,

что если

lsgn(x),

то

а(х)

sgn(x);

невозможен

алгорифм

типа

(к)

—• St>) такой,

что если

!sgn (х),

то р (х) =

sgn (х).

з>

Отметим также

следующее

следствие

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

С л е д с т в и е

Каково

бы ни

было КДЧ

z ~> 0,

не

возможен

алгорифм,

применимый

любому

такому,

что

\x\<z,

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

всякое

КДЧ

х,

для

кото

рого

О <

х <

не

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

никакого

КДЧ

такого,

что —z <

х < 0.

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

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

что

при неко

тором

z >

такой

алгорифм

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

ал

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

Поскольку при любом X

< *

1 +

х2 ^

алгорифм ф' применим к любому КДЧ, аннулирует вся кое положительное КДЧ и не аннулирует никакое от

рицательное

КДЧ.

Это, однако, противоречит лемме 2.

С л е д с т в и е

Каково

бы

ни

было z > 0,

невоз

можен

алгорифм,

указывающий

для

любого

КДЧ

х та

кого, что \x\<i

верный

член

дизъюнкции

( * > 0 ) V ( * < 0 ) .

С л е д с т в и е

Невозможен

алгорифм,

указы

вающий для

всякого

х ^

верный

член

дизъюнкции

(х >

0)V(x

(т. е. 1Ух(х^0=>

((х > 0)V(* = 0)))).

Невозможен

алгорифм,

указывающий

для

всякого

х =g: 0 верный

член

дизъюнкции

(х<0)

V ( * =

(г. е.

~] V* (* <

0 => ((* <

0) V (х =

0)))).

198	КДЧ; НЕВОЗМОЖНОСТЬ НЕКОТОРЫХ	АЛГОРИФМОВ	[ГЛ. 4
	Д о к а з а т е л ь с т в о . Следствие	6 может быть	до

казано непосредственно (аналогично тому, как доказы валась теорема 2). Мы выведем его из теоремы 4. Сде

лаем это, например, для утверждения		1).
	Пусть ф — алгорифм, указывающий для		любого
х	0 верный член дизъюнкции (х >	0) V (х =	0). Обо

значим для произвольного х через х+ КДЧ max (х, 0) и построим алгорифм ф' такой, что

ф ' ( д : ) ~ ф ( х + ) .

Поскольку всегда х+ ^

то ф'

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

вся

кое

КДЧ

или

Если

ф'(л:) =

то

х+

0 и,

сле

довательно,

Тем

более

х ^

Если

же

ф'(лг)

==2,

то

х+ =

и,

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

х ^

Таким

образом,

ф'

указывает

для

каждого

верный

член

дизъюнкции

(х

0) V (х ^

0), что

невозможно.

Предоставляем

читателю

доказать

следующие,

два

утверждения.

Невозможен

алгорифм,

указываю

С л е д с т в и е

щий

для

каждого

х верный

член

дизъюнкции

(\x\

x)V(\x\=-x).

С л е д с т в и е

Невозможен

алгорифм,

указываю

щий

для

любых

х, у верный

член

дизъюнкции

(max (х,

у) =

х)у

(max {х, у) =

у)

(то же с заменой

max на

min).

Имеет также

место

С л е д с т в и е

Невозможен

алгорифм,

указываю

щий

для

любых

х,

у таких,

что х-у

= 0,

верный

член

дизъюнкции

(* =

0) V (У =

0).

Действительно, для произвольного х обозначим х+ = max (х, 0),

х_ = min (х, 0).

Очевидно, х+-х~ = 0. Если бы алгорифм, о котором идет речь в следствии 9, был возможен, то мы смогли бы построить алгорифм, указывающий для любого х верный член дизъюнкции

(х+ = 0) V (х- = 0).

§ I]	ПРОБЛЕМЫ, СВЯЗАННЫЕ С ОТНОШЕНИЯМИ		ПОРЯДКА	199
Легко	видеть, что этот алгорифм указывал бы для лю
бого х верный член дизъюнкции
	( * < 0 ) V	(х>0),
что невозможно.
Отметим некоторые простые алгебраические след
ствия	полученных результатов	( Ц е й т и н	[6]). (Все	ал

гебраические образования рассматриваются над полем КДЧ.)

Рассмотрим линейное уравнение (с неизвестным х)

(3)			и • х = v.
Л е м м а		3.	Невозможен	алгорифм,	применимый
к слову	и,	v,	где и, v — КДЧ, тогда и		только	тогда,
когда уравнение			(3) имеет	решение.
Д о к а з а т е л ь с т в о . Это утверждение вытекает из
теоремы	1 и того, что при и = 0 уравнение (3)					имеет
решение тогда и только тогда, когда v =					0.

Для последующих формулировок нужно выбрать ка кой-нибудь способ однозначного кодирования матриц и систем линейных уравнений словами в Ч. Например, можно использовать следующий способ: матрица (а,5- —

КДЧ)		. . . а1п
/ а \\	я 1 2	. . . а1п
Л I а21	#22	• • • а2п
V am\	апг2	• • •	апгп
кодируется словом
а11> а12> •••> а1п*а21>	а22>	•••>	а2п* • • • * Um\,
&m2i	• • •»	CLmn	*,

а система линейных уравнений с этой матрицей и столб

цом	свободных членов b\	bm кодируется словом
	К{А)*Ь{,	bm
(где К(А) — код матрицы		А).
Термин «вектор порядка п» понимается			нами так же
как	«кортеж КДЧ длины я». Многочлены		мы кодируем

векторами, составленными из их коэффициентов так, что многочлен (с переменной х) а0хп + аххп~х -f- . . . -f- а„ кодируется словом а0, а ь . . . , а„.

200	КДЧ; НЕВОЗМОЖНОСТЬ НЕКОТОРЫХ АЛГОРИФМОВ	[ГЛ. 4
	Ниже, говоря про алгорифмы, определенным	образом

работающие над матрицами, системами линейных урав нений, многочленами, мы подразумеваем алгорифмы, со ответствующим образом работающие над кодами этих объектов.

Из леммы 3, очевидно, вытекает невозможность эф фективного распознавания совместности (или несовмест

ности)

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

Т е о р е м а

При

любом

п ^

невозможен

алго

рифм,

применимый

ко

всякой

системе

линейных

уравне

ний

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

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

те и

только те

системы,

которые

совместны.

х)

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

уравнение

(с

неизвестным

вида

[Л)

\v\-x=v.

Л е м м а

Невозможен

алгорифм,

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

щий

всякое

КДЧ

КДЧ,

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

уравне

нию

(4).

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

Пусть

такой

алгорифм

по

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

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

а » ~ Р з ( о ,

у ,

а (о)).

По

определению

свойствам

алгорифма

Рз

(тео

рема

21 § 3 гл. 2)

мы

получаем,

что

а'

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

всякое

КДЧ

1 или

в 2,

причем если

а'(у)

— 1,

то

а ( у ) < у ,

если

а'(о) =

то

а ( а ) > 0 .

Однако

из

a (v)

вытекает,

что

v ^

из

a(v)

вытекает

v ^

Таким

образом,

а'

указывает

при

любом

вер

ный член

дизъюнкции

( У < 0 )

V(v>0),

что

невозможно.

При

любом

п ^

невозможен

алго

Т е о р е м а

рифм,

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

всякую

совместную

систему

линейных

уравнений

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

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

решение

этой

системы.

§ 1]

ПРОБЛЕМЫ,

СВЯЗАННЫЕ

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

ПОРЯДКА

201

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

хп

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

х\ Ф 0.

Л е м м а

Можно

построить

алгорифм,

указываю

щий

для

любого

ненулевого

вектора

Х\

хп

верный

член

дизъюнкции

(*i Ф

0) V (х2

Ф 0) V . . .

\/(хпф0).

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

Пусть х\

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

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

для

краткости

через

Ясно,

что I >

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

выполняться

вое

неравенства

х2< —

( l < i < n ) .

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

— ,

х2{

(где

1 ^

п)

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

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

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

a(*i.

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

jf,xfj

2]j,

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

хп

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

его

одно

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

от

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

xn)

то

х2{

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

[6]). При

любом

п ^

не

Т е о р е м а

( Ц е й т и н

возможен

алгорифм,

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

всякую

систему

п линейных

однородных

уравнений

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

имеющую

нулевой

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

ненулевое

решение

этой

системы.

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

рассмотреть

слу

чай

п =

Рассмотрим

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

систему

(с

неиз

вестными х,

у)

вида

(и • х +

v • у =

( '

[и • х + v • у = 0

(где

и,

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

КДЧ) .

Если

бы

алгорифм,

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

речь в

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

мы

<<< < Предыдущая 8 9 10 11 12 13 14 15 16 17 18 1920 / 4520 21 22 23 24 25 26 27 28 29 30 31 32 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ

#
29.10.20235.79 Mб13Куцый П.Ф. Повелители молний.pdf
#
25.10.202312.79 Mб19Кучко А.С. Аэрофотография. Основы и метрология.pdf
#
25.10.202318.43 Mб47Кушманов И.В. Электронные приборы учеб. пособие.pdf
#
27.10.202319.55 Mб11Кушнарев Д.М. Использование энергии взрыва в строительстве.pdf
#
19.10.20232.48 Mб24Кушнарев, Ю. М. Авторулевой Печора учебное пособие для студентов судоводительского факультета.pdf
#
22.10.202314.87 Mб19Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf
#
24.10.202311.94 Mб20Кушнерев Н.Т. Программирование для ЭВМ Минск-32.pdf
#
25.10.202312.78 Mб21Кушнирская М.Ц. Крашение древесины в производстве мебели.pdf
#
27.10.202320 Mб7Кэтермоул К.В. Принципы импульсно-кодовой модуляции.pdf
#
23.10.20234.75 Mб13Лабинский Ю.В. Корабельные ядерные реакторы учеб. пособие.pdf
#
23.10.20238.6 Mб4Лабозин П.Г. Качество крупнопанельного домостроения.pdf