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

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

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

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

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

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

Добавлен: 15.10.2024

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

Скачиваний: 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 Р — алгорифм левого при соединения слова Р, т. е. алгорифм в алфавите Б со

схемой

{-•/>

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

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

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

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

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

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

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

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

Информация

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

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