4.4. Перечислимые свойства функций

Мы уже видели (теорема 21), что никакие (нетриви­альные) свойства функций не являются разрешимыми. Но некоторые являются перечислимыми (в том смысле, что множество всех номеров всех функций, обладающих этим свойством, перечислимо). Например, таково свой­ство функции «быть где-то определённой» (см. выше). Другой пример: свойство «/(19) определено и равно 98».

Имеется довольно простое описание всех перечисли­мых свойств. Чтобы его сформулировать, нам потребу­ются некоторые определения.

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

Каждому образцу I соответствует свойство функции «продолжать этот образец», то есть множество Г(/) всех (вычислимых) функций, которые являются продолжени­ями t. (Заметим в скобках, что множества Г(/) образу­ют базу топологии на множестве всех вычислимых функ­ций.) Легко проверить, что для любого / и для любой вычислимой нумерации и множество всех номеров всех функций из Г(/) перечислимо. В самом деле, надо парал­лельно вычислять значения 11п (х) для всех пшх; как толь­ко накопленные данные позволяют утверждать, что 11п £ £ Г(/), надо печатать п. (Если 11п £ Г(/), то это обнару­жится на конечном шаге, так как область определения образца t конечна.)

Пусть Т — произвольное множество образцов. Че­рез Г (Г) обозначим множество всех вычислимых функ­ций, которые продолжают хотя бы один образец из Т, то есть объединение множеств Т({) по всем < £ Г. Теперь мы можем сформулировать обещанный результат:

Теорема 24. (а) Пусть Т — произвольное перечисли­мое множество образцов, а II — вычислимая универсаль­ная функция для класса вычислимых функций одного ар­гумента. Тогда множество всех [/-номеров всех функций из Г (Г) перечислимо, (б) Пусть II — главная универсаль­ная функция (для класса вычислимых функций одного аргумента). Пусть 0 — некоторое подмножество этого класса. Если множество {п | [/„ £ £/} всех [/-номеров всех функций из класса 0 перечислимо, то 0 = Г (Г) для некоторого перечислимого множества образцов Т.

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

<] Часть (а) утверждения доказывается легко: надо параллельно вычислять все значения 11(п,х) и перечи­слять все образцы из Г; как только обнаруживается, что какая-то из функций [/„ является продолжением како­го-то образца из Т, следует печатать п.

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

Лемма 1. Если вычислимая функция К является про­должением вычислимой функции д, принадлежащей клас­су 0, то и функция К принадлежит классу 0.

Лемма 2. Если вычислимая функция д принадлежит классу 0, то существует функция К с конечной областью определения (образец), принадлежащая классу 0, продол­жением которой д является.

(Замечание в скобках. В совокупности эти две леммы утверждают, что любое перечислимое свойство 0 явля­ется открытым в описанной выше топологии.)

Покажем, как из этих лемм вытекает требуемое ут­верждение. Заметим, что множество Т всех образцов,принадлежащих классу 0, перечислимо. В самом деле, по образцу как конструктивному объекту (т. е. по спис­ку пар (аргумент, значение)) можно получить его [/-но­мер, поскольку функция 1} является главной. (Формаль­но: рассмотрим функцию (^,х) н->- (значение образца I в точке х) и применим определение главной универсальной функции.) Поэтому множество Т является перечислимым как прообраз перечислимого множества всех У-номеров всех функций из класса 0.

Леммы 1 и 2 гарантируют, что 0 = Г (Г). В самом деле, по лемме 1 любая функция из Г (Г) принадлежит классу 0, так как некоторая её часть принадлежит 0. С другой стороны, лемма 2 гарантирует, что всякая функ­ция д из 0 имеет конечную часть, принадлежащую 0 (тем самым и Г) и потому д £ Г (Г).

Осталось доказать леммы 1 и 2. Пусть, в противоре­чии с леммой 1, некоторая функция д принадлежит клас­су 0, а её продолжение К — нет. Возьмём перечислимое неразрешимое множество К и рассмотрим такую функ­цию двух аргументов:

тг/     ч     Г Нх), если п £ К, У{п,х) = <

{ дух), если п    К.

Эта функция вычислима. В самом деле, её график, как легко проверить, перечислим как объединение графика <?, умноженного на I !. и графика /г, умноженного на К. Дру­гими словами, чтобы вычислить У(п,х), мы запускаем процесс перечисления К, а также (параллельно с этим процессом) вычисления д(х) и Ь,(х). Результат выдаётся, если завершилось вычисление д(х) (в этом случае уже не­важно, лежит ли п в К, так как К есть продолжение д) или если завершилось вычисление Ь,(х) и к тому же п об­наружилось в К.

Поскольку функция II является главной, существует всюду определённая функция в с таким свойством:

• п £ К =>• [/,(„) = к =>• [/,(„) £ 0;

• п^К => [/,(„) = д => [/,(„) 6

Тем самым дополнение к К является прообразом пере­числимого множества номеров функций из 0 при вычи-

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

Лемма 2 доказывается аналогичным рассуждением. Пусть (вопреки утверждению леммы) функция д принад­лежит классу 0, но никакая её конечная часть не принад­лежит этому классу. Рассмотрим функцию

Легко видеть, что при п £ К функция Уп совпадает с д, и потому принадлежит 0, а при п £ К функция Уп является конечной частью функции д и потому не принадлежит 0. Далее рассуждаем как в лемме 1. >