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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

§ 3]

РАЗРЕШИМЫЕ

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

МНОЖЕСТВА

99

Точнее

говоря,

речь

идет

о

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

/л, /п. •••> In, Кп

( « ^ 2 )

таких, что при любых на­

туральных числах k, ki, ....

kn

 

 

 

 

Un(k)

( 1 < / < я ) ,

 

 

 

\Kn{kx,

....

kn),

 

 

In(k)

 

Kn{k\, ....

kn) — натуральные

числа и

 

In(Kn(ku

 

k,n)) =

ki

( 1 < * < п ) ,

 

 

K

„ ( / „

( A ) ,

 

In(k))

= k.

 

Легко видеть, что достаточно располагать алгориф­ мами Kz, l\, il- Алгорифмы с большими номерами строятся последовательно так, чтобы выполнялось

Kn+i(ku

kn+i) ^ Кп(К2 {kb k2), k3,

kn+i),

i l + l ( k ) ~ i 2 2 ( i l ( k ) ) ,

Для построения алгорифмов Кг> l\, й можно, на­ пример, воспользоваться тем, что любое натуральное число п допускает единственное представление в виде

я = 2"! -(2

+ 1 ) - 1.

 

Соответственно алгорифмы l\> l\,

К2 надлежит строить

так, чтобы

 

 

 

 

n =

2 I h n ) .(2-ll(n)+

l )

- l

и

 

 

 

 

К3(пи

п2 ) = 2 " 2 - ( 2 - « 1 + 1 ) - 1 .

Оказывается, что

эти три

алгорифма

могут быть за­

даны весьма простыми схемами, причем все алгорифмы

Кп

задаются одной схемой. Приведем

эти схемы ( Ц е й -

т и н [5; стр. 305—306]).

 

п

Алгорифм К (он годится в качестве Кп при любом

2) определяется как алгорифм в

алфавите {0|, оф}

4*

100

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

[ГЛ. 1

со схемой

| а -> а || а-> р|->ар

1 р - >

, 0->а|р

1 2

Алгорифмы h и h задаются соответственно схемами

а || -»• | а а|-> а —> •

0 - * 0 а

и

ааР->| аа аа->-

а||->| а

а|->р | а—>• а

0 - >0а

Обозначения

алгорифмов К,

l'n 0 ^ / ^ " .

п^2)

 

сохра­

няются на

протяжении

всей

книги.

 

 

 

 

 

 

2. Основные определения. Пусть Ж— некоторое мно­

жество слов в алфавите

А.

 

 

 

 

 

 

 

 

Будем

говорить,

что

Ж

 

алгорифмшески

 

разрешимо

(или,

короче,

разрешимо),

если можно

построить

 

алго­

рифм

21 над алфавитом А , применимый

к любому

слову

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

и

такой,

что при любом

слове

Р

в А

 

 

 

 

 

21 (Р)

== Л s P e

jK.

 

 

 

 

 

Алгорифм 21 будем называть разрешающим

алгориф­

мом

множества

Ж.

 

 

 

 

 

 

 

 

 

 

Множество

Ж

назовем

 

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

 

перечисли­

мым

(или,

короче,

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

 

если можно

по­

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

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

А Х такой,

что

для

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

101

любого натурального числа п и любого слова Р в А выполняется

1)

если

!31(/г), то

%{п)^Ж\

2)

если

Р е Ж,

то осуществимо i, при котором

Ш ( 0

и

 

 

Про алгорифм 91 мы говорим, что он перечисляет множество Ж. Множество Ж является, очевидно, мно­ жеством значений этого алгорифма на натуральных числах. Обратно, с каждым алгорифмом (£ типа можно связать множество слов в алфавите А, перечисляемое этим алгорифмом. Это множество мы

будем обозначать посредством {(5}.

Нетрудно привести примеры разрешимых и перечис­ лимых множеств. Например, пустое множество разре­ шимо и перечислимо. Множество всех слов в данном алфавите, очевидно, разрешимое, является также и пе­ речислимым — мы еще вернемся к этому вопросу. Раз­ решимым и перечислимым является множество нату­

ральных чисел (рассматриваемое

как множество

слов

в алфавите { 0 | } ) . Число подобного

рода примеров

мож­

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

ратное

утверждение неверно.

Будет

также приведен

пример

множества,

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

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

 

Сделаем некоторые замечания, связанные с алфави­

тами. Пусть алфавит Б является расширением

алфа­

вита А. Тогда множество Ж можно

рассмотреть

и

как

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

алфавите Б.

Легко видеть,

что

Ж,

рассматриваемое как множество слов в алфавите Б, яв­

ляется

разрешимым (перечислимым)

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

в этом

алфавите тогда и только тогда,

когда Ж обладает

одноименным свойством применительно к алфавиту А.

Таким образом, свойство разрешимости

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

сти), по существу, не зависит

от используемого алфави­

та. Заметим также, что теорема о переводе

 

(п. 5

§ 1)

позволяет заменить алгорифм

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

мно­

жество слов Ж в алфавите А, алгорифмом

в

алфавите

Af,

перечисляющим то же самое множество.

 

Таким

об­

разом, любое перечислимое множество слов

в

алфавите

А

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

алфавите

Л?;

рассмотре-

102

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

ГГЛ. 1

нием алгорифмов в этом алфавите и можно ограничиться при изучении перечислимых множеств в алфавите А. 'Аналогичное замечание можно было бы сделать и о раз­ решимых множествах.

Доказательство разрешимости

(перечислимости) мно­

жества связано, очевидно,

с

решением

конструктив­

ной задачи — построением

разрешающего

(перечисляю­

щего) алгорифма. Естественно, что этот алгорифм является весьма существенной характеристикой соответ­

ствующего

множества;

в тех

случаях, когда

речь идет

о каких-то

построениях

над

разрешимыми

(перечисли­

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

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

3. Некоторые стандартные способы перечисления пе­ речислимых множеств. Алгорифм 21 назовем арифмечески полным, если он применим к любому натураль­ ному числу.

Л е м м а

1.

Пусть

Ж—

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

множество,

Р — некоторое

 

слово. Можно

построить

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

полный алгорифм, перечисляющий

такое множество

Ж',

что Ж <= Ж'

<= Ж U {Р}.

 

 

 

 

 

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

Пусть

алгорифм

21

перечис­

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

Ж. Рассмотрим

алгорифм

[21]

(см. п.

10

§ 1) и построим, пользуясь теоремами сочетания, алго­

рифм

21' так,

что

 

 

 

 

,

|

Р,

если

[21](/J(п),

/ 1 ( п ) ) #

Л .

Д

{ П ) ~ (

21 (II («)),

если

[21] 01 (п),

It (п)) =

Л .

Алгорифм 21' искомый. Действительно, из определе­ ния алгорифмов [21] и l\, l\ следует, что 2Г арифметц-

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