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

Скачать файл (14,18Мб)

Заказать решение

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

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

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

Добавлен: 15.10.2024

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

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

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

§ 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, а ь . . . , а„.

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

Лебедев, Н. Н. Курс инженерной геодезии. Геодезические работы при проектировании и строительстве городов и тоннелей учебник.pdf

Лурье, Г. Б. Основы технологии абразивной доводочно-притирочной обработки учебник.pdf

Маринов, И. А. Устройство и эксплуатация преобразовательных подстанций городского электротранспорта учеб. пособие.pdf

Межотраслевые связи и народнохозяйственные пропорции Восточной Сибири и Дальнего Востока..pdf

Мирзоян, Э. Н. Развитие учения о рекапитуляции.pdf

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

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

Информация

Списки файлов

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