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

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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

АЛГОРИФМЫ И

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

[ГЛ. 1

алгорифмы,

выполняющие

любые

алгорифмические пре

образования

слов

в алфавите

А).

Т е о р е м а

Невозможен

алгорифм

над

алфавитом

{0|},

применимый

к записи

любого

алгорифма

алфа

вите

Аа и

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

запись

алгорифма

Аа

тогда

и только

тогда,

когда

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

самоприменим.

Проблема

распознавания

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

Пусть

21 — алгорифм

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

А.

Под

проблемой

рас

познавания

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

алгорифма

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

алфавита А мы понимаем следующую задачу: по

строить алгорифм 23 над А,				применимый к любому сло
ву Р в алфавите А и такой,				что
	23(Р) =		Л = !21(Р).
В случае, когда искомый алгорифм S3 можно по
строить,	мы говорим, что для алгорифма 21					разрешима
проблема	распознавания		применимости		относительно А.
В противном случае		будем		говорить, что для 21 проб
лема распознавания		применимости относительно алфа
вита А	неразрешима.
Ясно,	что, располагая алгорифмом 23, мы могли бы
избежать	подачи на	вход		алгорифма	21 тех	слов, для
которых	работа алгорифма			21 никогда	не заканчивается.

Из этого замечания ясен практический интерес, пред ставляемый проблемой распознавания применимости. Похожая задача при ограничении числа шагов алго

рифма 21 рассматривалась				в п. 10 §	1 и оказалась разре
шимой для любого алгорифма.
В этом пункте будет приведен пример алгорифма с
неразрешимой		проблемой		распознавания применимости.
Обозначим через Ах алфавит {0\|сф}.						ф в ал
Т е о р е м а		4.	Можно	построить	алгорифм
фавите А\	таким		образом,	что невозможен		нормальный
алгорифм	21 над		{0\|}, удовлетворящий		условию
			Ш(Р)=-]\$(Р)
для любого	слова		Р в алфавите {0\|}.
Д о к а з а т е л ь с т в о .				Пусть б— буква, не		входящая
в алфавит Ах.		По теореме об универсальном				алгорифме

(п. 8 § 1) построим алгорифм £>i так, что для любого алгорифма <5 в алфавите А\ и любого слова Q в том

§ 2]		НЕРАЗРЕШИМЫЕ АЛГОРНФМПЧЕСКПЕ						ПРОБЛЕМЫ		95
же	алфавите
(4)					£ , ( £ 6 3 6 Q ) ~ 6 ( Q ) .
Построим далее алгорифм \| ) 2 над алфавитом А{ так,
что при любом Q
(5)					£ 2 ( Q ) ~ § , ( Q 6 Q ) .
По		следствию			1 п. 5 § 1 (следствие теоремы о пере
воде)		можно		построить алгорифм			ф	в алфавите		Ах
с той же областью применимости относительно									{0\|}, что
и $2 ,		т. е. для		любого слова		Р в {0\|}
(6)					! £ ( Р) =	! £ 2 ( Р) .
Покажем, что ф обладает требуемыми свойствами.
Предположим, что построен алгорифм 91 над									алфави
том	{0\|} так, что				для любого слова Р в этом				алфавите
					Ж (Р) ^	1 !£> (Р).
Тогда			((6))
(7)					Ш(Р)^1\ЫР)-
Пусть			теперь		К — произвольный		алгорифм		в алфа
вите А\. Ввиду				(4) —(5)
					Ф 2 ( £ е З ) ^ е ( Е е З ) .
Следовательно				((7)),
				!Я(Е< £ 3)^ - 1!( ЦЕеЗ),
т. е.	91 применим				к записям тех и только тех алгориф
мов в алфавите Аи					которые несамоприменимы. Это					про
тиворечит,			однако, теореме			2.

Из теоремы 4 легко получаем искомый пример алго рифма с неразрешимой проблемой распознавания при

менимости.		5. Можно построить			алгорифм		в алфа
Т е о р е м а
вите	{01 а^} с	неразрешимой	проблемой			распознавания
применимости		относительно	алфавита		{0\|}.
Очевидно, всем требованиям теоремы 5 удовлетво
ряет алгорифм ф из теоремы 4.
3.	Непополнимый алгорифм.			Пусть		91 — алгорифм
над алфавитом А. Будем говорить,					что 91 полн		над А,
если	91 применим к любому		слову	в	этом	алфавите.

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

[ГЛ. 1

Алгорифм 23 над алфавитом А будем называть по полнением 21 относительно А, если 23 полн над А и для любого слова Р в этом алфавите, к которому при меним 21, выполняется

23(Я) = 2ЦР).

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

нием 21 относительно			А.
Как и в предыдущем пункте, обозначим через Ах
алфавит	{0\|ар}.
Т е о р е м а 6		(о	существовании			неисполнимого			ал
горифма,	принимающего			два	значения).		Можно		по
строить алгорифм		§	в алфавите		А{	такой, что		которому
1) для любого		слова		Р в алфавите {0\|}, к				которому
применим	S,		Ъ(Р)^0
или			Ъ(Р)^0
или			8 ( Р ) = р О \| ;
			8 ( Р ) = р О \| ;
2) 5	непополним		относительно {0\|}.
Д о к а з а т е л ь с т в о .				Пусть	б — буква,		не	принад

лежащая алфавиту А\. По теореме об универсальном

алгорифме		построим				алгорифм			Si так, что для любого
алгорифма		£	в Ах		и любого			слова Q в этом алфавите
(8)				3,(£<53 6Q)~S(Q) .
Построим			далее		алгорифм				так, что
(9)					g 2 (Q)~g,(Q6Q) .
(До сих	пор		мы в		точности			следовали		доказательству
теоремы	4.)
Используя теоремы сочетания, легко построить ал
горифм	Ъъ над			алфавитом				{0\|} так, что для любого
слова Р в этом				алфавите
и в том случае, когда						\i$2(P),
						О,	если		g 2 (Р) Ф О,
						0\|,	если		& ( Р ) =	0.

§ ZJ	НЕРАЗРЕШИМЫЕ	АЛГОРИФМИЧЕСКИЕ	ПРОБЛЕМЫ	97
Очевидно, Зз перерабатывает всякое слово в алфа
вите	{0\|}, к которому	он применим, в	0 или в 0\|.	По

кажем, что Зз непополним относительно {0|}. Предпо ложим, что алгорифм 93 над {0|} является пополнением Зз- Определим операцию перевода из алфавита алго

рифма 93 в алфавит		Л ь	сохраняющую	алфавит	{0\|} и
использующую кодирующие буквы а и				6. Пусть	93' —
перевод	алгорифма	93.	Легко проверить, что 93'		также
является	пополнением		Зз относительно	{0\|}. Так как
93' полн	над {0\|}, то

!23'(£23'3).

Следовательно (93' — алгорифм в алфавите ^ i l ) ,

откуда вытекает ((9))

!&(Е23'3).

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

!Зз(Е»'3).

Поскольку 93' — пополнение Зз, должно выполняться

»'(Е»'3)=5=8з(£ а'3).

Но ( ( 8 ) - ( 9 ) )

93' (Еаз'З) — S2 (£33'3). Таким образом, выполняется

что невозможно по построению Ъз- Алгорифм %з удовлетворяет всем условиям теоремы,

за исключением того, что он не является, вообще го воря, алгорифмом в алфавите А\. Легко добиться вы полнения и этого условия. Пусть Л 2 — алфавит алго рифма Ъъ- Определим операцию перевода из А2 в Аи сохраняющую алфавит {0|} и использующую кодирую щие буквы а, р\ Для перевода Ъ алгорифма Зз при любом слове Р в алфавите {0|}, как легко видеть, вы полняется

g ( P ) ~ & ( P ) .

4 Б. А. Кушнер

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

{ГЛ. 1

Таким образом, % обладает всеми требуемыми свой ствами.

Заметим, что для Ъ неразрешима проблема распо знавания применимости относительно алфавита {0|}. Отметим также, что из доказательства теоремы 6 легко извлекается следующее, более сильное чем непополни мость, свойство 3. Для любого алгорифма 23 можно указать слово Q в алфавите {0|} так, что

!8(Q) = !g(Q),

и если !23(Q), то

				» ( Q ) # S ( Q ) .
В	частности,		для	каждого	полного над		{0\|}	алгорифма
23 можно указать				слово Q так, что !8(Q)			и
				»(Q)=#S(Q) .
§	3.	Разрешимые и перечислимые множества
	В	этом параграфе мы изложим, следуя						в основном
гл.	2	работы	Ц е й т и н а		[5],	некоторые	элементарные
факты теории			алгорифмически			перечислимых		множеств.

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

речислимых	множеств, для знакомства с которой	мож
но обратиться к монографиям У с п е н с к о г о		[3],
М а л ь ц е в а	[1] и Р о д ж е р с а [1].

Сделаем некоторые технические замечания. Под на туральными числами мы, как и раньше, подразумеваем

слова	в	алфавите {0\|} вида			0, 0\|,	0 \| \| ,	. . . Начиная
с п. 2, мы считаем			фиксированным			некоторый		(непу
стой)	алфавит А.		Через	А\	обозначается			алфавит
Л и { 0 \| } ,		а через	А\ — какое-нибудь				фиксированное
двухбуквенное расширение Ах.					Множество натуральных
чисел	мы обозначаем		через	Ж.

1. Некоторые вспомогательные алгорифмы. Нам по требуется эффективное взаимно однозначное соответ ствие между натуральными числами и кортежами на туральных чисел произвольно фиксированной длины п.

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

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

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

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

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

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

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

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

Информация

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

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