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

90

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

[ГЛ. 1

%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

где С — некоторая система

формул, не зависящая

от

рифм 231, перерабатывающий всякое слово Р в

алфа­

вите Б в

изображение алгорифма 91р. Пусть

теперь

ЗЗ2 — нормальный алгорифм,

перерабатывающий

изо­

бражения

алгорифмов в Аа в

их записи (это, очевидно,

рифм 23 строится как композиция (232 о331)

алгорифмов

ЗЗ1 и ЗЗ2.

Теорема 16 будет обычно использоваться

нами в сле­

фавите А нужно указать запись алгорифма

в Аа, опре­

деленным образом

работающего на словах

в алфави­

те А. Строим алгорифм над алфавитом А,

работающий

на

словах вида PaQ,

где Р,

Q — слова

в А, а — буква,

не

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

А,

таким

образом,

что при каждом

92

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

[ГЛ. 1

неразрешимых

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

проблем, встречаю­

щихся

в этой

книге.

1.

Проблема

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

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

Везде

в этом пункте мы считаем фиксированным

алфа­

вит А,

содержащий

буквы 0 и

| * ) .

Алгорифм 21 в алфавите А назовем

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

(несамоприменимым),

если он

применим

(неприменим)

к своей записи.

Примерами

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

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

алгорифмов могут

служить всюду

определенный

и ни­

где

не

определенный алгорифмы

в алфавите

А

(см.

п. 4,

§

1).

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

следующей

теоремы

весьма

сходно

Рассела (см., например, К л и н и

[4]).

Т е о р е м а

1. Невозможен

алгорифм**)

в

алфави­

те А,

применимый

к

записи

алгорифма

в А тогда

и

только

тогда,

когда

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

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

Действительно, предположим, что такой алгорифм 23

построен. Поскольку

53 есть

алгорифм

в

алфавите

А,

можно поставить вопрос о его самоприменимости.

Предположим, что 23 самоприменим, т. е.

(1)

!23(£233).

*)

Существенным

является не

то,

что

А

содержит

именно

буквы 0 и |, а то, что

А содержит не менее

двух

различных

букв.

**)

Здесь и

ниже

мы

пользуемся

нашим

соглашением

(§

1)

об

НЕРАЗРЕШИМЫЕ ЛЛГОРИФМИЧЕСКИЕ ПРОБЛЕМЫ

93

(2)

~1123 (£233).

Таким образом,

23 — несамоприменимый алгорифм и по­

этому

(3)

!23(£233).

можно. Теорема

доказана.

Обозначим

через

Аа

двухбуквенное

расширение

A U {сф} алфавита А.

Т е о р е м а 2. Невозможен

алгорифм

над

алфавитом

{0|},

применимый

к записи

алгорифма

в алфавите

Аа

тогда

и только

тогда,

когда

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

несамопри-

меним.

Д о к а з а т е л ь с т в о . Предположим,

что такой

ал­

(следствие

1 п.

5 § 1) можно построить алгорифм 23'

в

алфавите

{0|сф} так, что для любого Р в {0|}

!23(Р)=!23, (Р).

Обозначим

через ЯЗ" естественное распространение 23'

на

алфавит

Аа

(23" — алгорифм в Аа с той же схемой,

что и 23').

При любом Р в {0|}

153' (Р) =

!23"(Р).

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

!23"(Р) =

!23(Р).

Аа,

Отсюда

следует, что 23" есть алгорифм в

алфавите

применимый

к записям тех и только тех алгориф­

мов в Аа,

которые несамоприменимы. Это, однако, не­

возможно в силу предыдущей теоремы. .

Из теоремы

2 вытекает

неразрешимость

проблемы