7.3. Релятивизация

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

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

Пусть Е — произвольное множество пар вида где х — число, — образец. Пусть а — некоторая всю­ду определённая функция. Отберём в множестве Е те па­ры, у которых вторые члены являются частью а; первые члены таких пар образуют множество, которое мы обо­значим -ЕЦа].

Теорема 46. Множество X является а-перечислимым тогда и только тогда, когда X = Е[а\ для некоторого пе­речислимого множества Е. (Заметим, что в этом случае не требуется никакого специального условия типа кор­ректности.)

<] Пусть X есть область определения вычислимой от­носительно а функции /. Тогда / = М[а] для некоторого перечислимого корректного множества М. Оставим от всех троек в М только первый и третий члены; получится некоторое перечислимое множество Е. Легко проверить, что Е[а\ будет областью определения функции М[а] = f, так что Е[а\ = X.

Напротив, пусть X = Е[а\ для некоторого а. Тогда рассмотрим множество М, которое получится, если в се­редину каждой пары из Е добавить число 0. Ясно, что множество М будет корректным и что М[а] будет функ­цией, определённой на X = Е[а\ и принимающей только нулевые значения. >

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

Теорема 47. Пусть а — всюду определённая функция. Существует вычислимая относительно а функция двухаргументов, являющаяся универсальной для класса вы­числимых относительно а функций одного аргумента.

<] Как и в других случаях, можно почти без изменений воспроизвести доказательство соответствующей нереля-тивизованной теоремы. Фиксируем какой-то язык про­граммирования (предусматривающий на этот раз вызо­вы внешних процедур) и перенумеруем все программы, которые включают в себя вызовы внешней процедуры а. Теперь в качестве универсальной можно взять функцию

иа(г,х) = (результат применения г-ой программы к х).

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

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

Рассмотрим универсальное перечислимое множест­во Е четвёрок вида (п, х, у, 2), где п, х и у — числа, a,t — образец. Говоря об универсальности, мы имеем в виду, что при различных п среди сечений Еп содержатся все перечислимые множества троек.

Среди этих перечислимых множеств троек могут быть и корректные, и некорректные. Мы хотим прину­дительно корректировать некорректные сечения, не ме­няя корректных. Другими словами, мы хотим построить новое перечислимое множество с такими свойствами: во-первых, все сечения корректны; во-вторых, если сечение Еп при некотором п было корректно, то оно не изменилось (Е'п = Zn).

Это делается просто: нужно перечислять отбрасы­вая (не пропуская в Е') элементы, добавление которых делает некоторое сечение некорректным. Итак, мы по­строили перечислимое множество , универсальное для класса корректных перечислимых множеств.

Теперь легко указать корректное множество IV, за­дающее универсальную а-вычислимую функцию. Имен­но, тройка ((п, х), у,£) (теперь её первым членом являет­ся пара, так как универсальная функция зависит от двух аргументов) принадлежит IV, если (п,х,у,£) £ . Легко понять, что множество IV корректно. При данной функ­ции а это корректное множество задаёт некоторую «-вы­числимую функцию IIа двух аргументов; её п-ое сечение есть Е'п[а], где Е'п — п-ое сечение множества . Поэтому среди сечений функции IIа встречаются все «-вычисли­мые функции, что и требовалось доказать. >

В релятивизованной теории алгоритмов имеется, ко­нечно, и аналог понятия главной универсальной функ­ции: а-вычислимую функцию двух аргументов называют главной универсальной функцией для класса а-вычисли-мых функций одного аргумента, если она а-вычислима, универсальна для класса а-вычислимых функций одного аргумента и для всякой а-вычислимой функции V двух аргументов существует всюду определённая «-вычисли­мая функция в одного аргумента («транслятор»), для ко­торой У(п,х) = 1}($(п), х) при всех п И X.

Обычное доказательство (с. 25, теорема 15) показы­вает, что главные универсальные функции для класса а-вычислимых функций существуют. Более того, можно заметить, что построенная при доказательстве (см. вы­ше) функция в будет не только а-вычислимой, но и про­сто вычислимой (в одном из вариантов доказательства функция в имела вид х н->- [п,ж], где квадратные скоб­ки обозначают фиксированную вычислимую нумерацию пар, а п — некоторое фиксированное число).

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

Говоря о релятивизованной теории алгоритмов, ино­гда употребляют такую метафору. Пусть А — какое-то неразрешимое множество. Может оказаться, что есть та­кая внеземная цивилизация, которой множество А кажет­ся разрешимым; глядя на число х, они сразу понимают, лежит ли оно в множестве А или нет, и эта проверка — такое же элементарное действие в их программах, как унас сравнение двух чисел. Тогда вся их теория алгорит­мов будет автоматически релятивизованной относитель­но А, но они этого замечать не будут и потому прочтут наши рассуждения вплоть до этого раздела (не включая его) и согласятся со всеми теоремами. Более того, они могут прочесть и этот раздел о релятивизации — но то, что для них будет В-вычислимым, для нас будет Л-В-вы­числимым (вычислимым с двумя оракулами А ж В).

Впрочем, к этой метафоре не стоит относиться слиш­ком серьёзно.