4.2. Новые номера старых функций

Теорема Успенского - Раиса показывает, что в глав­ной нумерации множество номеров любой конкретной функции неразрешимо и потому бесконечно. Сейчас мы докажем более сильный факт: по номеру любой функции в главной нумерации можно алгоритмически получить сколько угодно других номеров той же функции. Фор­мально это можно выразить, например, так:

Теорема 22. Пусть [/ — главная универсальная функ­ция. Тогда существует всюду определённая функция д двух аргументов с таким свойством: для любого і чи­сла д(і, 0),д(г, 1),... являются различными [/-номерами функции [/,-.

<] План таков: мы построим другую систему програм­мирования, в которой заданная функция [/,• имеет беско­нечно много программ. Затем, пользуясь тем, что функ­ция II — главная, будем «транслировать» эти программы и получать [/-номера интересующей нас функции. При этом мы примем специальные меры, чтобы гарантиро­вать, что получится бесконечно много разных номеров (вообще говоря, разные программы после трансляции мо­гут слиться). Объясним это более подробно. Пусть К — произвольная функция. Покажем, что существует алго­ритм, отыскивающий бесконечно много различных [^-но­меров функции К. (В теореме утверждается, что это мож­но сделать не только для конкретной функции /г, но и для всех функций [/,-, как говорят, «равномерно по г», но вре­менно забудем про это.)

Пусть Р — перечислимое неразрешимое множество. Рассмотрим вычислимую функцию

тг/     ч     Г Мж)> если п Є Р, V {п, х) = <

[ не определено, если П (£ Р'.

Среди функций Уп встречаются всего две: если п Є Р, то ^ = /г; если п ^ Р, то Уп — нигде не определённая функция, которую мы обозначим через С. Будем пока считать, что К ф £ (при К = £ эта конструкция не рабо­тает и нам потребуется чуть более сложная).

Новые номера старых функций

Так как II — главная универсальная функция, то су­ществует транслятор в, переводящий ^-номера в [/-но­мера. При этом

• п £ Р => и5(п) = Уп = /г;

• » € I' => иг(п) = Уп = (.

Таким образом, если р(0), р(1),... — вычислимое пе­речисление множества Р, то все числа в(р(0)), в(р(1)),... будут [/-номерами функции /г. Покажем, что среди этих чисел бесконечно много различных (и потому можно вы­числять их одно за другим, пока не обнаружится новый, ещё не использованный, номер функции К).

Пусть это не так, и множество X = {в(п) | п £ Р} конечно. Тогда X разрешимо. Если п £ Р, то в(п) £ X по построению; если п ^ Р, то в(п) — номер функции С и потому не может принадлежать X (напомним, что К ф ф £)• Следовательно, п £ Р равносильно в(п) £ X, и потому из разрешимости X следует разрешимость Р, что противоречит предположению.

Это рассуждение, однако, не проходит, если функ­ция К нигде не определена. Хотя числа в(р(0)), в(р(1)),... по-прежнему будут номерами /г, ничто не гарантирует нам, что среди них бесконечно много различных. В этом случае поступим чуть хитрее и рассмотрим любую вы­числимую функцию £, отличную от С (например, тожде­ственно нулевую). Рассмотрим два перечислимых неот­делимых множества Р и <5 и вычислимую функцию

У(п,х)

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

Пусть в — транслятор, переводящий ^-номера в [^-номе­ра. Тогда

• п £ Р =>• [/,(„) = /г;

• П £ д => [/,(„) = £;

• п^РиО^ [/8(п) = С-

Как и раньше, числа в(р(0)), в(р(1)),... будут номера­ми функции К. Покажем, что если К ф £, то множест­во X таких чисел неразрешимо (и потому бесконечно). В самом деле, если X разрешимо, то мы можем отде­лить Р от разрешимым множеством. Именно, множест­во {п | в(п) £ X} содержит Р (по построению) и не пе­ресекается с (поскольку при п £ число в(п) будет номером функции £ и потому не может лежать в X).

Таким образом, у нас есть две конструкции, позволя­ющие получать другие номера заданной функции К. Пер­вая из них заведомо годится (даёт бесконечно много но­вых номеров), если К хотя бы где-то определена; вторая заведомо действует для нигде не определённой К. Пусть нам теперь дана функция К и заранее не известно, явля­ется ли она нигде не определённой или нет. Что тогда? Тогда можно применять параллельно обе конструкции, пока одна из них не даст нам требуемый новый номер — мы знаем, что по крайней мере одна из конструкций обя­зана сработать, хотя и не знаем, какая.

Это позволяет нам провести рассуждение равномерно по г. Формально говоря, надо действовать так. Рассмо­трим две вычислимые функции У\ и V*! двух аргументов, определённые соотношениями

Г 1}(г, х), если п £ Р, У  г> ],х )= \    {'  " '

[ не определено, если П (£ Г,

II(г, х), если п £ Р, О, если п £ <5,

не определено, если п    Р и

(Р т — фиксированные перечислимые неотделимые множества, [и, г>] — номер пары (и, г>) в фиксированной вычислимой нумерации пар). Поскольку и — главная универсальная функция, можно найти такие вычислимые всюду определённые функции в! и «2, что У\(\},п\,х) = = 1}(в\ ([г, п]), х) и ^([г, п], х) = и^([г, п\), х). Пусть р — всюду определённая функция одного аргумента, для ко­торой Р = {р(0),р(1),...}. Искомую функцию д можно

У2{[г, п],х)= <

Изоморфизм главных нумераций

определить так: д(г, к) есть к-ое (без учёта повторений) число в последовательности

^([«•,Р(0)]),«2([*-,Р(0)]),«1([*',Р(1)]),