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

Определение 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] – номер пары}, а затем воспользоваться определением главного универсального множества.