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

Скачать файл
Заказать решение

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

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

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

Добавлен: 15.10.2024

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

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

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

108

 

АЛГОРИФМЫ И

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

 

[ГЛ. 1

алгорифм %ра перечисляет некоторое

множество

{21ра}

слов

в Л.

 

 

По всякому

двухместному

перечисляю­

Т е о р е м а

7.

щему

алгорифму

21 можно

построить

алгорифм

21' так,

что при

любом

слове

Р в

А алгорифм

%ра

 

является

стройным

алгорифмом,

перечисляющим

 

без

повторений

множество

{%Ра}.

 

 

 

 

 

 

 

Т е о р е м а

8. При

тех же условиях,

 

что в

теореме 7,

и дополнительном

условии

непустоты

всех

 

множеств

{ЩР а } можно

построить алгорифм 2F так, что при

каж­

дом

Р алгорифм

21ра

арифметически

полн

и

перечис­

ляет множество

{21ра}.

 

 

 

 

 

 

 

Использованные здесь обозначения введены в п. 2

данного

параграфа и в п. 11 § 1; через

21ра обозначается

перевод

% Р а в алфавит Л?.

области определе­

4. Перечислимые множества как

ния алгорифмов. Перечислимость разрешимых множеств.

Пусть Ж — множество

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

% — алго­

рифм над Л. Назовем Ж областью

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

(об­

ластью определения)

21 относительно А, если для

любого

слова Р в этом

алфавите

 

 

 

 

 

 

 

 

РеЖ^Ш(Р).

 

 

 

 

 

Т е о р е м а

9. Всякое

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

множество

слов

в алфавите А

является

областью

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

относи­

тельно А некоторого

алгорифма.

а — буква,

 

 

 

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

Пусть

не

принад­

лежащая алфавиту Л. По лемме

1 построим

арифмети­

чески полный

алгорифм

21', перечисляющий

некоторое

множество Ж'

такое, что

 

 

 

 

 

 

ЛГ s= J " S ЛГ U {а}.

Нетрудно построить алгорифм (ср. п. 7 § I) S3 так, что 33 применим к любому слову вида Р8п ( Р е Л , п — натуральное число, б — буква, отличная от а и от всех букв алфавита А\), причем

Ъ(РЬп)= А ==Р = 21'(я).

Построим теперь алгорифм (5 (по теореме И § 1) так,

что

e ( p ) ^ i i / ( » ( p 6 0 * ! - A ) .

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

109

Ясно, что

 

 

&{P)~\ii(P==

%'(?)>).

 

Следовательно, для любого слова Р в алфавите

А

! б ( Р) =

Ре= Ж.

 

Таким образом, Ж является областью применимости й относительно А, чем и заканчивается доказательство.

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

Л е м м а 2. Множество всех слов в алфавите А пере­ числимо.

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

подробностями

мы

отсылаем читателя к

работе

Д е т -

л о в с а [1].

 

Область применимости

любого

алго­

Т е о р е м а

10.

рифма относительно алфавита А является

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

множеством слов в этом

алфавите.

Ж является

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

Пусть множество

областью применимости алгорифма (5 относительно ал­ фавита А. Обозначим через 351 арифметически полный алгорифм, перечисляющий множество всех слов в алфа­

вите А. Пусть далее А 2 — а л ф а в и т

алгорифма f£ и алго­

рифм 352 аннулирует всякое слово

в этом

алфавите

(см.

пример 3 п. 4 § 1). По теоремам

композиции и объеди­

нения построим алгорифм

91 так, что

 

 

2t (ft) ~ 35, (ft) D2 (S(35,(tt))).

 

 

Ясно, что

 

 

 

 

!2t (ft) =3 16(35, (ft)),

 

 

причем, если ! & (35,(/г)),

то

 

 

 

91 (п)

= 35, (/г).

 

 

Легко видеть, что 21 перечисляет Ж.

В самом

деле,

если 121 (п), то КЦ35,(«))

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

 

35, (/г) е= Ж.

по

АЛГОРИФМЫ

И ПЕРЕЧИСЛИМЫЕ

МНОЖЕСТВА

 

[ГЛ. I

Поэтому

 

 

% (л) <=

Л.

 

 

 

 

 

 

 

 

 

 

 

 

 

Обратно,

если Р^Ж,

то

при

некотором

п

 

 

 

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

P=f=®l (я)

 

 

 

 

 

IG (©,(»))•

 

 

 

 

 

Тогда

 

 

 

 

 

 

 

 

 

21 («) = £>, (п) — Р .

 

 

 

 

 

 

 

 

 

 

 

Таким

образом,

множество

слов

в данном

 

алфавите

перечислимо

тогда

и только тогда,

когда

оно

является

областью

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

некоторого

алгорифма

относи­

тельно этого

алфавита.

 

 

 

 

 

 

 

 

Т е о р е м а

11. Всякое

разрешимое

множество

пере­

числимо.

 

 

 

 

 

 

 

 

 

 

 

Действительно, пусть алгорифм 21 разрешает множе­

ство Ж. Построим алгорифм 2li в алфавите А,

примени­

мый лишь к пустому слову (пример 4

п. 4

§

1).

По­

строим, наконец, алгорифм 212

так, что

 

 

 

 

 

 

 

2l2 (P)~2I,(2l(P)).

 

 

 

 

 

Ясно, что для любого

слова

Р

в алфавите

А

 

 

 

 

 

Р<=М = Ш2

(Р).

 

 

 

 

 

Отсюда на основании теоремы 10 получаем, что Ж пе­ речислимо.

Пусть теперь ф — алгорифм, построенный согласно теореме 4 § 2. Обозначим через Ж множество тех слов в алфавите {0|}, к которым неприменим этот алгорифм. Из теоремы 4 вытекает, что Ж не является областью при­ менимости относительно {0|} никакого алгорифма. Сле­ довательно, Ж неперечислимо. Обозначим через Ж мно­ жество тех слов в {0|}, к которым ф применим. Очевид­ но, Ж перечислимо. Вместе с тем по теореме 5 § 2 это множество не является разрешимым. Таким образом, имеет место

§ 3]

РАЗРЕШИМЫЕ И

ПЕРЕЧИСЛИМЫЕ

МНОЖЕСТВА

 

111

Т е о р е м а 12.

1)

Существует

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

множе­

ство слов в

алфавите

{0|}, дополнение

которого до

мно­

жества

всех

слое в

этом алфавите неперечислимо

* ) .

2) Существует

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

множество слов

в

ал­

фавите

{0|},

не являющееся

разрешимым.

 

 

Необходимое и достаточное условие разрешимости перечислимого множества дается следующей теоремой Поста (доказательство которой предоставляется чита­ телю): множество Ж (слов в алфавите А) разрешимо тогда и только тогда, когда оно само и его дополнение (до множества всех слов в А) перечислимы.

5. Пересечение и объединение перечислимых мно­

жеств.

 

Пересечение

конечного

числа

перечис­

Т е о р е м а 13.

лимых

множеств

перечислимо.

Ж\,

Жп—

 

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

перечис­

лимые множества. По теореме 9 построим

алгорифмы

%\

21„ так, что каждое множество

Ж\

является об­

ластью определения алгорифма 2Ij относительно алфа­ вита А (если исходные множества были в разных алфа­ витах, то можно рассмотреть их все в объединении этих

алфавитов). По теореме объединения

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

91 так, что

 

 

%(Р)~%(Р)%2(Р)

. . .

%п(Р).

Ясно, что

 

& Шп (Р),

131 (Р) Е 121! (Р) & |Я2 (Р) & . . .

т. е.

 

 

!?I(P)=Pe= f]

Ли

 

Отсюда, ввиду теоремы 10, следует перечислимость

п

множества f") Ли

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

*) Дополнением множества Ж слов в алфавите Л_до множества всех слов в этом алфавите мы называем множество Ж слов в А, оп­ ределяемое условием

P e i s " ] ( P £ Л),

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