Добавил:

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

Вуз:

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

Предмет:

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

Файл:

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

.pdf

Скачиваний:

Добавлен:

22.10.2023

Размер:

14.87 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 459 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

82	АЛГОРИФМЫ	И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА		[ГЛ. 1
причем в случае существования этой цепочки
	Ф6	(Рат) =	РатаРтат.

Алгорифм Фб уже очень близок к искомому. В самом деле, по теореме композиции построим алгорифм g так, что

		(E(Pam)~fi3 (D6 (Pam)),
где	В3	— такой алгорифм, что для любых слов 5 Ь 5 2 ,
.Ь'з,	5 4	в A U{0\|}
		В3 ( 5 , 0 5 2 0 5 3 0 5 4 ) = = 5 3 .

Ясно тогда, что применимость алгорифма (5 к слову Рат равносильна существованию указанной выше це почки Р0, ..., Рт, причем в случае существования та кой цепочки

(65)	S (Рат) = Рт.

Из (62) — (65) получаем

К (PaO) ~ 1 (Р),

6 (Pam + 1) ~ 23 (PamaS (Pam)),

что и требуется.

Предлагаем читателю в качестве упражнения по

строить с помощью теоремы повторения	нормальный
алгорифм, умножающий натуральные числа.
8. Изображение и запись нормального	алгорифма.

Теорема об универсальном алгорифме. В ряде случаев возникает необходимость привлекать одни нормальные алгорифмы в качестве исходных данных других алго рифмов. В таких случаях оказывается необходимой ко дировка схем нормальных алгорифмов словами неко торых специальных типов. Мы приведем здесь, следуя

монографии М а р к о в а	[2], два	простых способа та
кой кодировки. Каждый	из них	обеспечивает возмож

ность однозначного восстановления схемы нормального

алгорифма по его коду.			А, и пусть а,
Пусть	фиксирован	некоторый алфавит	А, и пусть а,
Р, у —Т РИ	различные	буквы, отличные от	стрелки и от

точки и не принадлежащие А. Обозначим через Б ал фавит A U {офу}-

	НОРМАЛЬНЫЕ	АЛГОРИФМЫ	83
Пусть	% — произвольный	нормальный	алгорифм в
алфавите	А. Изображением	91й алгорифма	21 назовем

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

новок	21, причем справа		от	каждой	формулы	ставится
буква	у. а	в с е стрелки	и	точки заменяются		соответ
ственно на		буквы а и р .	Например,		изображением тож
дественного		алгорифма	{-•

является слово аРу, а изображением алгорифма со схе мой

Р^Р2 Рз^-Р4

(где Pi, Р2, Рз, Pi — какие-то слова) является слово

Р1аР2уР3а^Р4у.

Одним из важнейших фактов теории нормальных алгорифмов (равно как и других общих концепций ал горифма) является существование универсального нор мального алгорифма, т. е. алгорифма, выполняющего в некотором смысле работу любого нормального алго рифма в данном алфавите. В качестве исходных данных этот алгорифм, естественно, использует, кроме подле жащего обработке слова, и код выполняемого алго рифма.

Имеет место следующая теорема, утверждающая су ществование универсального алгорифма при кодирова

нии нормальных алгорифмов их изображениями

(в этой

теореме

б — некоторая

буква,

не

принадлежащая

алфа

виту

Б).

Может

Т е о р е м а

13 ( М а р к о в

[2;

гл.

4, §

2]).

быть

построен

такой

нормальный

алгорифм

23 над

ал

фавитом

Б, что

23(21И 6Р)~2ЦР)

для

любого

нормального

алгорифма

21 в

алфавите

и любого

слова

Р в А.

Кодирование

нормальных

алгорифмов

посредством

их

изображений иногда

оказывается

неудобным

(ср.

из-за

большого

количества

используемых

нем

84 АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОХ<ЕСТВА [ГЛ. I

букв. В таких случаях прибегают к более сложным спо

собам	кодирования, обходящимся	меньшим числом
букв.	Следуя М а р к о в у [2; гл. 4,	§ 3], мы будем при

менять способ кодирования, использующий всего две буквы. Именно, каждому нормальному алгорифму 21 в алфавите А будет сопоставляться некоторое слово в

двухбуквенном	алфавите	{ 0 \| } * ) , называемое записью %
и обозначаемое	посредством		£ ^ 3 - Это	сопоставление
осуществляется	следующим		образом.	Определяется
операция перевода (п. 5)		из	алфавита Б	изображений

нормальных алгорифмов в алфавит {0|}, использующая кодирующие буквы 0 и | (сохраняемый алфавит в дан ном случае пуст), и записью данного нормального ал

горифма	объявляется	перевод его	изображения**).
По записи каждого нормального алгорифма в алфа
вите А	может быть	однозначно	восстановлена его
схема.

Приведем два примера записей алгорифмов. В каче стве алфавита А возьмем в этих примерах двухбуквенный алфавит {ab}, а в качестве букв а, р\ у соответ

ственно буквы с, d и е.

У1\

{ab}

Запись

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

алгорифма

в алфавите

(его схема {->• )такова:

E^i3

0[ | 100] | | 1001 | | | |0.

Пусть

21 — нормальный

алгорифм

алфавите

{ab}

со

схемой

(21 аннулирует любое слово в этом

алфавите).

Очевидно,

21й == acebce

*) Марков использует алфавит {ab}.

**)

Более подробно: выписываются

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

порядке

буквы

г|1,

г]п+з

алфавита

(положим

r | „ + i = = o c ,

г|„+2==р,

г|п+8=?=у).

Переводом

буквы r|j

(1 ^ i

п + 3 )

считается

слопо

0 | J _ ^ J 0.

раз

Наконец, перевод слова в алфавите Б получается

одновременной

заменой всех его букв их переводами.

Таким образом, при определении записей

алгорифмов

алфа

вите А надлежит как-то фиксировать порядок

букв в этом алфа

вите. В дальнейшем мы опускаем

детали

этого

рода.

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

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

перевод

Теорема 13 легко распространяется на новый способ

кодирования.

Т е о р е м а

14 (теорема об универсальном алгориф

ме; М а р ко в [2; гл. 4, § 4]). Можно

построить

нормаль

ный

алгорифм

над алфавитом

Л1){0|6} (б —

буква,

не принадлежащая

алфавиту

A U {0|}) так, что при

лю

бом

нормальном

алгорифме

31 в

алфавите

любом

слове

Р в этом алфавите

выполняется

23(£2G6P)

Алгорифм, удовлетворяющий теореме 14, мы будем

называть универсальным

алгорифмом

для

алфавита

А,

использующим

разделительную

букву

б.

Принцип

нормализации.

Из

ознакомления

с пре

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

нейшего знакомства	с теорией	нормальных	алгорифмов
и подтверждается	практикой	построения	конкретных

нормальных алгорифмов. Выражением этих обстоя тельств является следующий, высказанный М а р к о в ы м [2; стр. 91] принцип нормализации алгорифмов: всякий алгорифм (в интуитивном смысле) в алфавите А вполне эквивалентен относительно А некоторому нормальному алгорифму над А.

Принцип нормализации утверждает, таким образом, что концепция нормального алгорифма над алфавитом А в полной мере выражает наши интуитивные пред ставления об алгорифмах, перерабатывающих слова в А. Ясно, что принцип нормализации не может быть строго доказан (из-за фигурирующего в нем расплыв чатого общего понятия алгорифма) и носит характер естественнонаучной гипотезы.. Мы отсылаем читателя за более подробным обсуждением этого принципа к моно графии М а р к о в а [2]*).

*) Ввиду эквивалентности уточнений понятия алгорифма, дости гаемых с помощью нормальных алгорифмов, а также частично

86		АЛГОРИФМЫ И		ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА						[ГЛ. 1
Отметим, что со строго математической точки										зре
ния наши		построения		не	зависят от принципа				нормали
зации,	этот		принцип	не	используется		ни	в	определе
ниях,	ни	в	формулировках			и доказательствах теорем
(ср. введение, стр. 31).					От	принятия	или	непринятия
принципа		нормализации			зависит лишь		признание			боль

шей или меньшей общности излагаемой теории (отно сятся ли ее результаты только к нормальным алгориф мам или выражают свойства алгорифмов и вычисли мости вообще).

В дальнейшем будут рассматриваться, как правило, лишь нормальные алгорифмы, в связи с чем прилага


тельное		«нормальный»		будет	часто опускаться.
	10.	Моделирование		работы нормального алгорифма
по	шагам. Из		определения		нормального	алгорифма
(п.	3)	следует,	что процесс		применения	нормального

алгорифма к произвольному слову распадается на от дельные шаги, состоящие в выполнении соответствую щих формул подстановок. Уточним сказанное.

Пусть 91 — нормальный алгорифм в некотором ал фавите Л (который считается фиксированным на про

тяжении	этого	и следующего пункта).	Пусть, далее,
Р — слово	в Л	и п — натуральное число.	При разверты

вании процесса применения 91 к Р могут представиться три возможности (мы используем обозначения п. 4):

1)найдется слово Q такое, что

91:P K + i Q ;

2)найдется Q такое, что

91:Ph=nQ

иQ не поддается алгорифму 91 (мы пишем 91: Р\=0Р> если Р не поддается 91);

рекурсивных функций и машин Тьюринга, принцип нормализации вполне аналогичен тезису Черча и тезису Тьюринга (утверждающим совпадение последних двух концепций вычислимости и алгорифмов с соответствующими интуитивными концепциями). Читатель может, таким образом, воспринимать в качестве аргументации в пользу

принципа	нормализации	аргументацию	в пользу этих тезисов (см.,
например,	монографии	К л и н и [4],	М а л ь ц е в а [1] и У с п е н
с к о г о [3]).

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

найдется Q такое,

что

Я:

Р\=п-

(ясно, что в этом

случае

п >

0).

В случае 1) будем говорить, что 91 не

заканчивает

работу

над

Р за

шагов,

случае

будем

говорить,

что

заканчивает

работу

над

точности

за

п + 1

шагов,

случае

3) — в

точности за

шагов*).

Ска

жем,

что

91 заканчивает

работу

над

не

более

чем

за

шагов,

если

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

k ^

заканчивает

работу над Р в точности за k шагов.

Имея

нормальный алгорифм

91, слово

натураль

ное число ft, можно задаться вопросом:

заканчивает ли

91 свою

работу над

Р не

более

чем за

шагов? Интуи

тивное предписание для ответа на такой вопрос совер шенно очевидно: нужно выполнять шаг за шагом алго

рифм 91 и ждать, закончится ли						его	работа		до	ft-ro
шага (т. е. дойдем ли				мы	до ft-ro	применения			формул
подстановок).
	Можно построить и нормальный алгорифм, решаю
щий эту задачу.
	Т е о р е м а		15**). Пусть		91 — нормальный				алгорифм
в	алфавите	А	и а — буква,		не принадлежащая				А.	Мож
но	построить нормальный			алгорифм		[91]^	над	алфавитом
A ( J { 0 \| } U { a }			так, что для		любого	слова	Р	в	алфавите
А	и любого	натурального		п

1)l[9t]a (Paft);

2)	[Ща(Рап) =т= Л тогда				и	только	тогда,		когда	91
заканчивает		работу	над	Р не	более чем		за	п	шагов.
*)	Таким	образом,	число	шагов,		за которое	St	заканчивает		ра

боту над Р, определено нами как число применений формул под становок в случае заключительного обрыва и как число применений

формул подстановок плюс единица в	случае естественного	обрыва.
Эта небольшая непоследовательность	в определении, ничего	не ме

няя по существу, позволяет заметно упростить доказательство тео

ремы 15. Читатель легко заметит, что число							шагов			работы
алгорифма St над словом Р				равно	числу применений					формул
подстановок (при		работе	над	этим	же	словом)	замыкания				ST
алгорифма	SC.
**) Доказательства этой теоремы и теоремы							16	(п.	11)	почти
буквально	заимствованы		нами	из работы		Ц е й т и н а		[5]. В каче
стве полезного упражнения предлагаем читателю							непосредственно,
не используя теорем сочетания, написать схему							[St]a >		исходя		из
схемы алгорифма		St.


88	АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА						[ГЛ. 1
	Нам понадобится		следующая		лемма	( Р — буква, от
личная от всех букв			алфавита	Л U {а}).
Л е м м а		1. Для	любого	алгорифма		23 в	алфавите
A U {р} можно построить алгорифм					& так, что при лю
бом	слове	Р в A (J {р} и любом натуральном п

6 (РаО) ~ Р,

6 (Pare + 1)^33 (6 (Pare)).

Эта лемма без труда доказывается с помощью тео ремы 12 (п. 7). Ясно, что при п > О

g (Pare) ~ 23 (23 ( . . . 23 (Р)) .. . ) .

					п раз
	Докажем теперь			теорему 15. Построим					алгорифм 2Ii
в алфавите A U {р}, схема которого							получается			из схемы
51 следующим образом. Сначала перейдем									от	21 к его
замыканию 21*			(см. п. 3), затем			в	схеме		21*	заменим
все	точки	буквой р		и,	наконец,	все		знаки	—>• заменим
на	—• •.	Ясно,	что	21]	применим		к	любому		слову в
A U {р}, причем			всякое слово, содержащее						букву р, пе

рерабатывается этим алгорифмом снова в слово, со

держащее	р. Кроме того, при любых		словах Р, Q в ал
фавите А,	если 21: Р (— Q, то	5Xi(P) Q, и		если
21: Р \|— • Q, то 21] перерабатывает		Р	в некоторое	слово,
содержащее букву р.
Обозначим через 212 алгорифм,			построенный	по 2Ii

согласно лемме 1. Очевидно, 212 применим к любому


слову		Pan	(где Р е Л), причем	буква	р	входит в
5Х2(Раге) в том и только в том случае, когда						21 заканчи
вает	работу		над Р не более чем за п шагов. Пусть, да
лее,	513 — алгорифм, применимый			ко всем	словам в ал
фавите		Л U {р} и перерабатывающий в пустое слово те

и только те из этих слов, в которые входит буква р (читатель без труда выпишет схему такого алгорифма).

Искомый алгорифм [2l] a строим с помощью теоремы композиции так, чтобы

[2l]a (Pare) ~ 2 l 3 ( 2 I 2 (Pare)). Из теоремы 15 без труда получаем

	НОРМАЛЬНЫЕ АЛГОРИФМЫ						89
С л е д с т в и е	5.	Для		любого	алгорифма		21 в алфа
вите А и любого	слова		Р в этом		алфавите
Ш(Р)		=	Зп([Ща		(Рап)=Л).
С л е д с т в и е	6.	Если		при некотором		п
		[%}а(Рап)~А,
то и при всяком	m^z		п
		[Ща(Рат)-Л
Обозначение	типа		[Ща	сохраняется		на	протяжении

всей книги, причем нижний индекс а, указывающий на используемую разделительную букву, будет, как пра вило, опускаться (поскольку из контекста почти всегда ясно, каким он должен был бы быть). Описанная кон

струкция, как увидит читатель, играет			значительную
роль при сведении		алгорифмических проблем анализа
к некоторым внутренним алгорифмическим проблемам
теории	алгорифмов	(которые будут рассмотрены .в сле
дующем	параграфе).
11. Фиксирование одного из аргументов нормального
алгорифма. Часто		нас интересует работа	нормального

алгорифма на словах, представляющих собой объеди нение нескольких исходных данных. Например, рас

смотренный в		предыдущем пункте алгорифм [21] рабо
тал	на словах	вида Pan, т. е., по существу, использовал
два	аргумента	Р и п, объединенных, как обычно, в одно

слово с помощью разделительной буквы. Ясно, что при каждом фиксированном Р можно рассмотреть алгорифм 23р такой, что

23р (п) с- [21] {Pan).

Возникает вопрос об оформлении получаемых таким об разом алгорифмов в виде нормальных. Мы приведем соответствующую конструкцию, следуя Ц е й т и н у [5].

Пусть 21 — нормальный алгорифм в некотором расширении Б алфавита A, У 1 Р — алгорифм левого при соединения слова Р, т. е. алгорифм в алфавите Б со

схемой

{-•/>

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

[ГЛ. 1

Обозначим через % Р композицию (2l°SJtp ) этих двух алгорифмов. Очевидно, для любых слов Р и Q в алфа вите Б

		%P(Q)~%(PQ),
что и требовалось.
Алгорифм	$ р	является	алгорифмом в некотором
расширении Б{	алфавита Б		(£>ь очевидно, не зависит
от Р). Вместе	с	тем при	изучении алгорифмических

преобразований слов в исходном алфавите Л обычно бывает удобно ограничиться рассмотрением нормальных алгорифмов в фиксированном двухбуквенном расшире

нии Аа

алфавита

А (см. п. 5).

С целью

приведения

% Р

алфавиту

Аа

определяется

операция

перевода (см.

п. 5) из

5] в Аа,

сохраняющая

алфавит

А.

Перевод

ал

горифма

Щр мы будем обозначать через

21р,

причем

верхний

индекс А, как правило, будем опускать. Итак,

% Р

есть

нормальный алгорифм

в алфавите Аа,

эквива

лентный

21р относительно

А.

частности,

если

21 — ал

горифм

типа

( Л т * Л ) , то

при

любых словах

Р и Q в А

выполняется

%P(Q)~%(PQ).

Пусть

для

алфавита

Аа

определена

запись

алгориф

мов в этом алфавите (п.

8).

Нам

будет

полезна

теорема

( Ц е й -

т и н [5]).

16. Пусть

21 — нормальный

алгорифм

Т е о р е м а

алфавите

Б,

включающем

А.

Тогда

можно

построить

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

23, что

= £ € Р З

93(Р)

для любого слова Р в алфавите Б.

Д о	к а з а т е л ь с т в о . Поскольку	алгорифм 21 р	опре
делен	как композиция (2I°5ftp ), то	схема 21р имеет	вид
(см. п. 7, теорема композиции)

НОРМАЛЬНЫЕ	АЛГОРИФМЫ	91
где С — некоторая система	формул, не зависящая	от

слова Р, а 51« — система двух формул:

аР

Обозначим через т нормальный алгорифм, осуществляю щий перевод из алфавита Б\ алгорифма 91Р (этот ал фавит, являющийся расширением Б, не зависит от Р)

валфавит Аа. Алгорифм т перерабатывает всякое^слово

валфавите £>i в его перевод. Схема алгорифма 51Р , яв

ляющегося переводом %Р , имеет, очевидно, вид

-> г ( а Р )

-> т ( а )

где D — некоторая система формул, не зависящая от Р. Изображение алгорифма 91р запишется (с использова нием вспомогательных букв (3, у, б) как слово

Dpt (аР) брт (а) б,

где D — опять-таки некоторое слово, не зависящее от Р. Используя теорему объединения, легко построить алго

рифм 231, перерабатывающий всякое слово Р в			алфа
вите Б в	изображение алгорифма 91р. Пусть		теперь
ЗЗ2 — нормальный алгорифм,		перерабатывающий	изо
бражения	алгорифмов в Аа в	их записи (это, очевидно,

также некоторый алгорифм перевода). Искомый алго

рифм 23 строится как композиция (232 о331)	алгорифмов
ЗЗ1 и ЗЗ2.
Теорема 16 будет обычно использоваться	нами в сле

дующих ситуациях. Пусть для каждого слова Р в ал


фавите А нужно указать запись алгорифма						в Аа, опре
деленным образом		работающего на словах				в алфави
те А. Строим алгорифм над алфавитом А,						работающий
на	словах вида PaQ,		где Р,	Q — слова	в А, а — буква,
не	принадлежащая	А,	таким	образом,	что при каждом

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 459 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

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

#
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