Нумерации

Лекция № 7. Нумерации и их свойства

1. Нумерации.

2. Теорема о неподвижной точке

Определение 7.1.1. Всюду определенное отображение n: N®F область значения, которого есть все множество F, называют нумерацией (натуральной нумерацией) множества F. При этом, если n(n)=f, то n – номер объекта fÎ F.

Пример 7.1.1. Всякая универсальная функция двух аргументов для класса вычислимых функций одного аргумента задает нумерацию этого класса.

Определение 7.1.2. Нумерации, соответствующие главным универсальным функциям, называют главными или геделевыми.

Теорема 7.1.1. Пусть U – главная универсальная функция. Тогда множество тех n, при которых U_n является нигде не определенной, неразрешимо.

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

Так как U – главная универсальная функция, то существует вычислимая всюду определенная функция s(n), значениемкоторой при nÏK является U-номер нигде не определенной функции.

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

Следствие. Нигде не определенная функция в любой главной нумерации имеет бесконечно много номеров.

Следствие. Множество номеров нигде не определенной функции не только не разрешимо, но и не перечислимо.

Пример 7.1.2 ( вычислимой универсальной функции, не являющейся главной)

Пусть U(n, x) – произвольнаявычислимаяуниверсальная функция, D – множество U-номеров всех функций с непустой областью определения. Пусть d – всюду определенная вычислимая функция, перечисляющая множество D (то есть D={d(0), d(1), …}). Рассмотрим функцию V(i, x), для которой V(0, x) не определена при всех x, а V(i+1, x)=U(d(i), x). Функция V(i, x) вычислима, она универсальна по построению, и единственным V – номером нигде не определенной функции является число 0.

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

Теорема 7.1.2. (Успенского-Райса). Пусть F – класс вычислимых функций одного аргумента, AÌF (A¹Æ, A¹F). U – главная универсальная функция для F. Тогда множество {n: U_nÎA} – неразрешимо.

Доказательство. Пусть K – перечислимое неразрешимое множество. Без ограничения общности можно считать, что нигде не определенная функция zÎA. Обозначимчерез x произвольнуюфункцию, не принадлежащую A (xÏA)[8].

Положим

Вычислимая функция V(n, x) при nÎK совпадает с x . При nÏK – с функцией z. При этом предположение о разрешимости множества {n: U_nÎA} влечет за собой утверждение о том, что множество К разрешимо. Полученное противоречие доказывает теорему.

¨Теорема доказана.

Согласно иной интерпретации теоремы Успенского-Райса можно говорить о том, что по U-номеру вычислимой функции f в главной нумерации нельзя определить обладает ли эта функция некоторым нетривиальным свойством A[9].

По теореме Успенского-Райса в любой главной нумерации множество номеров любой конкретной функции неразрешимо и потому бесконечно. Справедливо и более сильное утверждение – по номеру любой функции в главной нумерации можно алгоритмически получить бесконечное число других номеров той же функции. Справедлива следующая теорема.

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

Теорема 7.1.4.(об изоморфизме главных нумераций). Пусть U₁, U₂ – главные универсальные функции для класса вычислимых функций одного аргумента. Тогда существуют две всюду определенные взаимно обратные вычислимые функции s₁₂, s₂₁ для которых

U₁(n, x)=U₂(s₁₂(n), x) и U₂(n, x)=U₁(s₂₁(n), x).

Доказательство. Укажемалгоритм построения биекции между числами a_i и b_i, считая, что для каждого i числа a_i и b_i,– номера одной и той же функции (a_i в U₁, b_i в U₂).

На каждом шаге построения к соответствиям вида a₁«b₁, a₂«b₂, …, a_k-1«b_k-1 добавляем пару a_k«b_k следующим образом.

На четном шаге выбирается наименьшее натуральное число u, не встречающееся в {a₁, a₂, …, a_k-1}. В нумерации U₁ число u – номер некоторой функции f. Так как нумерация U₂ главная, то, согласно предыдущей теореме отыщется число vÏ{b₁, b₂, …, b_k-1}, которое будет номером функции f в нумерации U₂. Тогда, полагая a_k=u, b_k=v, получимследующую парунашего соответствия.

На нечетном шаге выбирается наименьшее натуральное число vÏ{b₁, b₂, …, b_k-1}, по которому определяется функция g, имеющая в нумерации U₂ номер v. Далеепо функции g отыскивается ее номер u в нумерации U₁, не встречающийсяв {a₁, a₂, …, a_k-1}. Полагая a_k=u, b_k=v, получим следующую парунашего соответствия.

При реализации этого алгоритма с обеих сторон будут включены все натуральные числа, причем построенное соответствие будет вычислимым.

¨Теорема доказана.

Определение 7.1.3. Функция с натуральными аргументами и значениями, имеющая конечную область определения, называется образцом.

Если t – некоторый образец, то через G(t) обозначим множество всех вычислимых функций, являющихся продолжениями t. Пусть далее Т – произвольное множество образцов, G(Т) – множество всех вычислимых функций, которые продолжают хотя бы один образец из Т ().

Теорема 7.1.5. Пусть Т – произвольное перечислимое множество образцов, U – вычислимая универсальная функция для класса вычислимых функций одного аргумента. Тогда множество всех U-номеров всех функций из G(Т) перечислимо.

Теорема 7.1.6. Пусть U – главная универсальная функция для класса вычислимых функций одного аргумента. Пусть G – некоторое подмножество этого класса. Если множество {n: U_nÎ G} перечислимо, то G=G(Т) для некоторого перечислимого множества образцов Т.