Свойства главных нумераций

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

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

Теорема 22. Пусть U главная универсальная функция. Тогда существует всюду определенная функция g двух аргументов с таким свойством: для любого i числа g(i,0),g(i,1),... являются различными U -номерами функции Ui.

План таков: мы построим другую систему программирования, в которой заданная функция Ui имеет бесконечно много программ. Затем, пользуясь тем, что функция U главная, будем " транслировать" эти программы и получать U -номера интересующей нас функции. Конечно, нужны специальные хитрости, чтобы гарантировать, что получится бесконечно много разных номеров: вообще говоря, разные программы после трансляции могут слиться. (Например, если в нашей системе программирования разрешены комментарии, то ничего не стоит найти сколько угодно различных программ для одной и той же функции, добавляя разные комментарии к программе но если транслятор начинает свою работу с удаления комментариев, то ничего хорошего не выйдет.)

Вот как реализуется описанный выше план. Пусть h произвольная функция. Покажем, что существует алгоритм, отыскивающий бесконечно много различных U -номеров функции h. (В теореме утверждается, что это можно сделать не только для конкретной функции h, но и для всех функций Ui, как говорят, " равномерно по i ", но временно забудем про это.)

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

$$V(n,x)= \left\{ \begin{aligned} h(x), \text{ если $n\in P$,}\\ \text{не определено, если $n\notin P$.} \end{aligned} \right.$$

Среди функций Vn встречаются всего две: если $$n \in P$$, то Vn = h ; если $$n \notin P$$, то Vn нигде не определенная функция, которую мы обозначим через $$\zeta.$$ Будем пока считать, что $$h \ne \zeta$$ (при $$h = \zeta$$ эта конструкция не работает и нам потребуется чуть более сложная).

Так как U главная универсальная функция, то существует транслятор s, переводящий V -номера в U -номера. При этом

$$n \in P \Rightarrow U_{s(n)} = V_{n} = h$$ ;

$$n \notin P \Rightarrow U_{s(n)} = V_{n} = \zeta$$.

Таким образом, если p(0),p(1),... вычислимое перечисление множества P, то все числа s(p(0)),s(p(1)),... будут U -номерами функции h. Покажем, что среди этих чисел бесконечно много различных (и потому можно вычислять их одно за другим, пока не обнаружится новый, еще не использованный, номер функции h ).

Пусть это не так, и множество $$X = \{ s(n) | n \in P\}$$ конечно. Тогда X разрешимо. Если $$n \in P$$, то $$s(n) \in X$$ по построению; если $$n \notin P$$, то s(n) номер функции $$\zeta$$ и потому не может принадлежать X (напомним, что $$h \ne \zeta$$ ). Следовательно, $$n \in P$$ равносильно $$s(n) \in X$$, и потому из разрешимости X следует разрешимость P, что противоречит предположению.

Это рассуждение, однако, не проходит, если функция h нигде не определена. Хотя числа s(p(0)),s(p(1)),... по-прежнему будут номерами h, ничто не гарантирует нам, что среди них бесконечно много различных. В этом случае поступим чуть хитрее и рассмотрим любую вычислимую функцию $$\xi,$$ отличную от $$\zeta$$ (например, тождественно нулевую). Рассмотрим два перечислимых неотделимых множества P и Q и вычислимую функцию

$$V(n,x)= \left\{ \begin{aligned} \text{$h(x)$, если $n\in P$,}\\ \text{$\xi(x)$, если $n\in Q$,}\\ \text{не определено, если $n\notin P\cup Q$.} \end{aligned} \right.$$

Пусть s транслятор, переводящий V -номера в U -номера. Тогда

$$n \in P \Rightarrow U_{s(n)} = h$$ ;

$$n \in Q \Rightarrow U_{s(n)} =\xi$$ ;

$$n \notin P \cup Q \Rightarrow U_{s(n)} = \zeta$$.

Как и раньше, числа s(p(0)),s(p(1)),... будут номерами функции h. Покажем, что если $$h \ne \xi$$, то множество X таких чисел неразрешимо (и потому бесконечно). В самом деле, если X разрешимо, то мы можем отделить P от Q разрешимым множеством. Именно, множество $$\{ n | s(n) \in X\}$$ содержит P (по построению) и не пересекается с Q (поскольку при $$n \in Q$$ число s(n) будет номером функции $$\xi$$ и потому не может лежать в X ).

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

Это позволяет нам провести рассуждение равномерно по i. Формально говоря, надо действовать так. Рассмотрим две вычислимые функции V1 и V2 двух аргументов, определенные соотношениями

$$\begin{align*} V_1([i,n],x) = \left\{ \begin{aligned} {}\text{$U(i,x)$}, \text{ если $n\in P$,}\\ {}\text{не определено}, \text{ если $n\notin P$,}\\ \end{aligned} \right.\\[1ex] V_2([i,n],x) = \left\{ \begin{aligned} {}\text{$U(i,x)$}, \text{ если $n\in P$,}\\ {}\text{$0$}, \text{ если $n\in Q$,}\\ {}\text{не определено},\text{ если $n\notin P\cup Q$}\\ \end{aligned} \right. \end{align*}$$

( P и Q фиксированные перечислимые неотделимые множества, [u,v] номер пары $$\langle u,v\rangle$$ в фиксированной вычислимой нумерации пар). Поскольку U главная универсальная функция, можно найти такие вычислимые всюду определенные функции s1 и s2, что V1([i,n],x) = U(s1([i,n]),x) и V2([i,n],x) = U(s2([i,n]),x). Пусть p всюду определенная функция одного аргумента, для которой P = {p(0),p(1),...}. Искомую функцию g можно определить так: g(i,k) есть k -ое (без учета повторений) число в последовательности

s1([i,p(0)]), s2([i,p(0)]), s1([i,p(1)]), s2([i,p(1)]), s1([i,p(2)]), s2([i,p(2)]),...

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

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

Теорема 23. Пусть U1 и U2 две главные универсальные функции для класса вычислимых функций одного аргумента. Тогда существуют две всюду определенные взаимно обратные вычислимые функции s12 и s21, для которых

U1(n,x)=U2(s12(n),x) и U2(n,x)=U1(s21(n),x)

при любых n и x.

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

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

$$a_{1} \leftrightarrow b_{1}, a_{2} \leftrightarrow b_{2}, \dots , a_{k} \leftrightarrow b_{k}$$

между двумя конечными k -элементными подмножествами натурального ряда. При этом для каждого i числа ai и bi являются номерами одной и той же функции, только в разных нумерациях ( ai относительно U1, а bi относительно U2 ).

На каждом шаге построения мы добавляем новую пару $$a_{k} \leftrightarrow b_{k}$$ с сохранением указанного свойства. При этом постепенно с обеих сторон мы включим все натуральные числа. Тем самым мы получим искомое взаимно однозначное соответствие, и оно будет вычислимым, раз наша конструкция вычислима.

Итак, как мы добавляем новую пару? На четных шагах мы берем наименьшее натуральное число u, не входящее в левую сторону соответствия (не встречающееся среди ai ). Оно является U1 -номером некоторой функции. Поскольку нумерация U2 главная, мы можем получить некоторый U2 -номер той же функции. Обозначим его v. Если v не встречается среди bi, дело сделано: мы добавляем пару $$u \leftrightarrow v$$ к нашему соответствию. Если встречается, мы пользуемся теоремой 22 и получаем другие U2 -номера той же функции до тех пор, пока среди них не окажется нового, еще не встречавшегося среди bi.

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

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

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

  33. Проведите это рассуждение подробно.

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

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

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

Будем называть образцом функцию с натуральными аргументами и значениями, имеющую конечную область определения. Другими словами, образец есть конечный список пар $$\langle\text{аргумент},\text{значение}\rangle$$ (в котором все аргументы различны). Образцы можно рассматривать как конструктивные объекты (кодировать двоичными словами, натуральными числами и т.п.). Это позволяет говорить о разрешимом множестве образцов, перечислимом множестве образцов и т.п.

Каждому образцу t соответствует свойство функции " продолжать этот образец ", то есть множество $$\Gamma (t)$$ всех (вычислимых) функций, которые являются продолжениями t. (Заметим в скобках, что множества $$\Gamma (t)$$ образуют базу топологии на множестве всех вычислимых функций.) Легко проверить, что для любого t и для любой вычислимой нумерации U множество всех номеров всех функций из $$\Gamma (t)$$ перечислимо. В самом деле, надо параллельно вычислять значения Un(x) для всех n и x ; как только накопленные данные позволяют утверждать, что $$U_{n} \in \Gamma (t)$$, надо печатать n. (Если $$U_{n} \in \Gamma (t)$$, то это обнаружится на конечном шаге, так как область определения образца t конечна.)

Пусть T произвольное множество образцов. Через $$\Gamma (T)$$ обозначим множество всех вычислимых функций, которые продолжают хотя бы один образец из T, то есть объединение множеств $$\Gamma (t)$$ по всем $$t \in T$$. Теперь мы можем сформулировать обещанный результат:

Теорема 24. (a) Пусть T произвольное перечислимое множество образцов, а U вычислимая универсальная функция для класса вычислимых функций одного аргумента. Тогда множество всех U -номеров всех функций из $$\Gamma (T)$$ перечислимо. (б) Пусть U главная универсальная функция (для класса вычислимых функций одного аргумента). Пусть G некоторое подмножество этого класса. Если множество $$\{ n | U_{n} \in G\}$$ всех U -номеров всех функций из класса G перечислимо, то $$G = \Gamma (T)$$ для некоторого перечислимого множества образцов T.

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

Часть (а) утверждения доказывается легко: надо параллельно вычислять все значения U(n,x) и перечислять все образцы из T ; как только обнаруживается, что какая-то из функций Un является продолжением какого-то образца из T, следует печатать n.

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

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

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

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

Покажем, как из этих лемм вытекает требуемое утверждение. Заметим, что множество T всех образцов, принадлежащих классу G, перечислимо. В самом деле, по образцу как конструктивному объекту (т.е. по списку пар $$\langle\text{аргумент},\text{значение}\rangle$$ ) можно получить его U -номер, поскольку функция U является главной. (Формально: рассмотрим функцию $$\langle t,x\rangle\hm\mapsto\text{(значение}$ образца~$t$ в точке~$x)$$ и применим определение главной универсальной функции.) Поэтому множество T является перечислимым как прообраз перечислимого множества всех U -номеров всех функций из класса G.

Леммы 1 и 2 гарантируют, что $$G = \Gamma (T)$$. В самом деле, по лемме 1 любая функция из $$\Gamma (T)$$ принадлежит классу G, так как некоторая ее часть принадлежит G. С другой стороны, лемма 2 гарантирует, что всякая функция g из G имеет конечную часть, принадлежащую G (тем самым и T ) и потому $$g \in \Gamma (T)$$.

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

$$V(n,x)= \left\{ \begin{aligned} \text{$h(x)$, если $n\in K$,}\\ \text{$g(x)$, если $n\notin K$.} \end{aligned} \right.$$

Эта функция вычислима. В самом деле, ее график, как легко проверить, перечислим как объединение графика g, умноженного на N, и графика h, умноженного на K. Другими словами, чтобы вычислить V(n,x), мы запускаем процесс перечисления K, а также (параллельно с этим процессом) вычисления g(x) и h(x). Результат выдается, если завершилось вычисление g(x) (в этом случае уже неважно, лежит ли n в K, так как h есть продолжение g ) или если завершилось вычисление h(x) и к тому же n обнаружилось в K.

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

$$n \in K \Rightarrow U_{s(n)}=h \Rightarrow U_{s(n)} \notin G$$ ;

$$n \notin K \Rightarrow U_{s(n)}=g \Rightarrow U_{s(n)} \in G$$.

Тем самым дополнение к K является прообразом перечислимого множества номеров функций из G при вычислимом отображении s и потому (теорема 5) перечислимо. Полученное противоречие завершает доказательство леммы 1.

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

$$V(n,x)= \left\{ \begin{aligned} \text{g(x), } \text{если после x шагов перечисления K}\\ \text{число n еще не появилось,}\\ \hbox to 0pt{\text{не определено, если появилось.}\hss} \end{aligned} \right.$$

Легко видеть, что при $$n \notin K$$ функция Vn совпадает с g, и потому принадлежит G, а при $$n \in K$$ функция Vn является конечной частью функции g и потому не принадлежит G. Далее рассуждаем как в лемме 1.