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

Доказанное только что утверждение о получении но­вых номеров используется при доказательства теоремы Роджерса об изоморфизме главных (гёделевых) нумера­ций. Вот её формулировка:

Теорема 23. Пусть II\ и I '•> — две главные универсаль­ные функции для класса вычислимых функций одного аргумента. Тогда существуют две всюду определённые взаимно обратные вычислимые функции в!2 и Для которых

и\{п,х) = £/2(«12(п), ж)     И     и2{п,х) = и\(82\{п),х)

при любых п И X.

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

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

си <->• Ь\, а2 <->• Ь2,..., а* <->• Ьимежду двумя конечными ^-элементными подмножества­ми натурального ряда. При этом для каждого і числа щ и 6,- являются номерами одной и той же функции, толь­ко в разных нумерациях (щ — относительно II\, а 6,- — относительно II2).

На каждом шаге построения мы добавляем новую па­ру <->• с сохранением указанного свойства. При этом постепенно с обеих сторон мы включим все натуральные числа. Тем самым мы получим искомое взаимно одно­значное соответствие, и оно будет вычислимым, раз наша конструкция вычислима.

Итак, как мы добавляем новую пару? На чётных ша­гах мы берём наименьшее натуральное число и, не вхо­дящее в левую сторону соответствия (не встречающееся среди щ). Оно является [/ц-номером некоторой функции. Поскольку нумерация ІІ2 главная, мы можем получить некоторый ^2-номер той же функции. Обозначим его V. Если V не встречается среди 6,-, дело сделано: мы добавля­ем пару и <->• V к нашему соответствию. Если встречается, мы пользуемся теоремой 22 и получаем другие [^-номера той же функции до тех пор, пока среди них не окажется нового, ещё не встречавшегося среди 6,-.

На нечётных шагах мы действуем аналогичным обра­зом, но начинаем с наименьшего числа, не встречающе­гося среди 6,-. >

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

Аналогичная теорема верна и для главных нумера­ций перечислимых множеств: любые две такие нумера­ции изоморфны (отличаются вычислимой перестановкой номеров). Доказательство также проводится аналогич­но; сначала нужно показать, что в главной нумерации полюбому номеру можно алгоритмически получить сколько угодно номеров того же множества. При этом применя­ются два способа — один годится для всех множеств, кроме пустого, другой для пустого.