2. Главные универсальные функции и множества

Определение 6.2.1. Универсальная функция U двух натуральных аргументов называется главной универсальной функцией, если для любой вычислимой функции V существует всюду определенная вычислимая функция s(m), для которой V(m, x)=U(s(m), x) при всех m и x (значения V и U либо оба не определены, либо определены и равны).

Теорема 6.2.1. Существует главная универсальная функция.

Доказательство. Зафиксируем некоторое взаимнооднозначное соответствие , обозначая номер пары (u, v) через [u, v] ((u, v)[u, v]).

Пусть далее R(x,y) – вычислимая универсальная функция для вычислимых функций одной переменной. Положим T(n, u, v)= R(n, [u, v]).

Если V(u, v) – произвольная вычислимая функция двух аргументов, то функция f([u, v])=V(u, v) – вычислимая функция одного аргумента, и поскольку R(x,y) – универсальна, то найдется число n, для которого R(n, x)=f(x) для любых x. Для этого n выполнены равенства

T(n, u, v)=R(n, [u, v])=f([u, v])=V(u, v).

Определим U([n, u], v)=T(n, u, v). Тогда согласно предыдущим рассуждениям для произвольной вычислимой функции двух аргументов V(u, v) можно найти число n, для которого V(u, v)=T(n, u, v)=U([n, u], v) для всех u и v. Полагая s(u)=[n,u], имеем V(u, v)=U(s(u), v)).

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

Теорема 6.2.2. Пусть U(u, v) – главная универсальная функция для класса вычислимых функций одного аргумента. Тогда существует всюду определенная функция c(p, q) такая, что U(c(p, q), x)=U(p, U(q, x)) для всех p, q и x.

Доказательство. Положим V([p, q], x)=U(p, U(q, x)). По определению главной универсальной функции найдется такая всюду определенная вычислимая функция одного аргумента s(m), что V(m, x)=U(s(m), x)) для всех m и x.

Тогда функция c(p, q)= s([p, q]) будет искомой.

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

Теорема 6.2.3. Пусть U(u, v) – универсальная функция для класса вычислимых функций одного аргумента. Если существует всюду определенная функция c(p, q) такая, что U(c(p, q), x)=U(p, U(q, x)) для всех p, q и x, то функция U(u, v) является главной универсальной функцией.

Определение 6.2.2. Перечислимое множество называется главным универсальным перечислимым множеством (для класса всех перечислимых подмножествN), если для любого другого перечислимого множества найдется такая всюду определенная функцияs: NN, что для всех n, x

(n, x)V  (s(n), x) W.

Теорема 6.2.3. Существует главное универсальное перечислимое множество .

Доказательство. Пусть U(u, v) – главная универсальная функция для класса вычислимых функций одного аргумента, W – ее область определения. Пусть далее – произвольное перечислимое множество. Тогда найдется вычислимая функцияG(u, v) с областью определения V. Так как функция U(u, v) – главная универсальная функция, то найдется такая всюду определенная вычислимая функция s(n): NN, что G(n,x)=U(s(n), v) для всех n, x. Это означает, что (n, x)V  (s(n), x) W.

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

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

Теорема 6.2.4. Пусть – главное универсальное перечислимое множество,W_n={x: (n, x)W}. Тогда существует такая вычислимая, всюду определенная функция s(m, n), что W_{s(m, n)}=W_mW_n.

Для доказательства теоремы необходимо определить множество V={([m, n], x): xW_mW_n, [m, n] – номер пары}, а затем воспользоваться определением главного универсального множества.

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

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

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