4.1. Множества номеров

Начнём с такого примера. Рассмотрим множество но­меров нигде не определённой функции для какой-либо главной нумерации. Будет ли оно разрешимо? Другими словами, можно ли по номеру функции в главной нумера­ции определить, является ли эта функция нигде не определённой?

Прежде чем отвечать на этот вопрос, заметим, что ответ не зависит от того, какая главная нумерация вы­брана. В самом деле, если есть две разные главные нуме­рации, то они, как говорят, «сводятся» друг к другу: по номеру функции в одной нумерации можно алгоритмиче­ски получить номер той же функции в другой нумерации. Если бы в одной нумерации можно было бы проверять «нигде-не-определённость» функции, то это можно было бы делать и в другой (применив «функции перехода»).

Следующая теорема показывает, что ответ на исход­ный вопрос будет отрицательным.

Теорема 20. Пусть и — произвольная главная универ­сальная функция. Тогда множество тех п, при которых функция 11п является нигде не определённой, неразрешимо.

<] Используем метод, называемый «сведением» — по­кажем, что если бы это множество было разрешимым, то и вообще любое перечислимое множество было бы разре­шимым. (Что, как мы знаем, неверно.)

Пусть К — произвольное перечислимое неразреши­мое множество. Рассмотрим такую вычислимую функ­цию V двух аргументов:

Как видно, второй аргумент этой функции фиктивен, и она по существу совпадает с полухарактеристической функцией множества К от первого аргумента. Очевидно,

У(п,х)

0, если п £ К,

не определено, если п ^ К.эта функция имеет сечения двух типов: при п £ К сече­ние Уп является нулевой функцией, при п £ К — нигде не определённой функцией.

Так как функция [/ является главной, существует вы­числимая всюду определённая функция в, для которой У(п, х) = 1}($(п), х) при всех п и х, т. е. Уп = [/5(„). Поэто­му при п £ К значение в(п) является [/-номером нулевой функции, а при п ^ К значение в(п) является [/-номером нигде не определённой функции. Поэтому если бы мно­жество [/-номеров нигде не определённой функции раз­решалось бы некоторым алгоритмом, то мы бы могли применить этот алгоритм к в(п) и узнать, принадлежит ли число п множеству К или нет. Таким образом, мно­жество К было бы разрешимым в противоречии с нашим предположением. >

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

Кроме того, можно заметить, что множество номеров нигде не определённой функции не только не разрешимо, но и не перечислимо. В самом деле, его дополнение — множество всех номеров всех функций с непустой обла­стью определения — перечислимо. (Это верно для любой вычислимой нумерации, а не только для главной: парал­лельно вычисляя и(п,х) для всех п и х, мы можем пе­чатать те п, для которых обнаружилось х, при котором и(п,х) определено.) А если дополнение неразрешимого множества перечислимо, то само множество неперечи-слимо (по теореме Поста, с. 13).

Справедливо и более общее утверждение, называемое иногда теоремой Успенского - Райса. Обозначим класс всех вычислимых функций (одного аргумента) через Т.

Теорема 21. Пусть Л С Р — произвольное нетриви­альное свойство вычислимых функций (нетривиальность означает, что есть как функции, ему удовлетворяющие, так и функции, ему не удовлетворяющие, то есть что множество А непусто и не совпадает со всем Пусть 1} — главная универсальная функция. Тогда не существу­ет алгоритма, который по [/-номеру вычислимой функ­ции проверял бы, обладает ли она свойством Л. Другими словами, множество {п | 11п £ Л} неразрешимо.

<] Посмотрим, принадлежит ли нигде не определённая функция (обозначим её С) классу Л, и возьмём произволь­ную функцию £ «с другой стороны» (если С £ Л, то £ ^ Л и наоборот).

Далее действуем как раньше, но только вместо нуле­вой функции возьмём функцию £: положим

...     ч     Г £,(х), если п £ К,

{ не определено, если П (£ К .

Как и раньше, функция V будет вычислимой (для дан­ных виг мы ожидаем появления п в множестве К, после чего вычисляем При п £ К функция Уп совпадает

с £, при п £ К — с С. Таким образом, проверяя свой­ство Уп £ Л (если бы это можно было сделать вопреки утверждению теоремы), можно было бы узнать, принад­лежит ли число п множеству К или нет. >

Некоторым недостатком этого доказательства явля­ется его несимметричность (с одной стороны от Л мы берём нигде не определённую функцию, с другой сторо­ны — любую). Вот более симметричный вариант. Пока­жем, что если свойство Л можно распознавать по [/-но­мерам, то любые два непересекающихся перечислимых множества Р т отделимы разрешимым множеством. Выберем какие-нибудь две функции £ и г), находящиеся «по разные стороны» от Л. Рассмотрим функцию

У(п,х)

если п £ Р, г}(х), если п £ <5, не определено, если п    Р и <5-

Эта функция вычислима: для заданных п и х ожидаем, пока п появится либо в Р, либо в <5, после чего запускаем вычисление соответственно        или г}(х).

Если п £ Р, то Уп совпадает с £; если п £ <5, то Уп совпадает с ц. Поэтому, проверяя, принадлежит ли Упклассу Л, мы могли бы разрешимо отделить Р от По­лучаем противоречие, которое и завершает этот более симметричный вариант доказательства.

Второй вариант доказательства показывает, что вер­но следующее усиление этой теоремы: для любых различ­ных вычислимых функций (р и ф и любой главной уни­версальной функции 1} множества всех и-номеров функ­ции (р и функции ф не отделимы разрешимым множе­ством. (Заметим, что эти множества не перечислимы, как мы впоследствии увидим.)

Теперь легко указать пример вычислимой универсаль­ной функции, не являющейся главной. Достаточно сде­лать так, чтобы нигде не определённая функция име­ла единственный номер. Это несложно. Пусть и(п,х) — произвольная вычислимая универсальная функция. Рас­смотрим множество О всех 1}-номеров всех функций с не­пустой областью определения. Как мы уже говорили, это множество перечислимо. Рассмотрим всюду определён­ную вычислимую функцию ё, его перечисляющую: О = = {ё(0),ё(1),...}. Теперь рассмотрим функцию У(г,х), для которой У(0,х) не определено ни при каком х, а У(г + 1,х) = и(ё(г),х). Другими словами, функция Уд нигде не определена, а функция У%+\ совпадает с IIщу Легко понять, что функция У вычислима; она универ­сальна по построению, и единственным ^-номером нигде не определённой функции является число 0.

На самом деле существуют и более экзотические ну­мерации: как показал Фридберг, можно построить уни­версальную вычислимую функцию, для которой каждая вычислимая функция будет иметь ровно один номер. Соответствующие нумерации называют однозначными; очевидно, они не могут быть главными. Забавная пере­формулировка: можно разработать такой язык програм­мирования, в котором каждую программистскую задачу можно решить единственным образом. (Доказательство этой теоремы трудно и не приводится, на русском языке оно есть в книжке А. И. Мальцева «Алгоритмы и рекур­сивные функции» [5].) Аналогичное утверждение верно и для нумераций перечислимых множеств.