22. Универсальные функции

Сечением (n1)-местной функции f по (первой) переменной x называется n-местная функция f_x, xN, такая, что для всех t₁,…,t_nN

f_x(t₁,…,t_n)f(x,t₁,…,t_n).

Существует ли программа, которая вычисляла бы все функции? В некотором смысле такие программы существуют.

(n1)-местная функция u называется универсальной для класса C, состоящего из некоторых вычислимых n-местных функций, если:

1) xN u_xC;

2) fC xN fu_x.

Иначе говоря, класс C будет задано перечислением функций вида u_x:

Cu₀,u₁,…,u_i,….

Существует вычислимая универсальная функция для класса всех вычислимых n-местных функций.

Теорема Клини о нормальной форме (без доказательства). Для каждого n0 существует нумерация без пробелов для всех n-местных вычислимых функций _i(x₁,…,x_n), iN, такая, что:

1) (n1)-местная функция u, определенная равенством

u(i,x₁,…,x_n)_i(x₁,…,x_n)

для всех i,x₁,…,x_nN, будет частично рекурсивной;

2) для каждого iN функция _i(x₁,…,x_n) будет частично рекурсивной;

3) каждая частично рекурсивная функция совпадает с функцией _i для некоторого индекса iN.

Теорема 1. Не существует примитивно рекурсивной (общерекурсивной) универсальной функции для класса всех n-местных примитивно рекурсивных (общерекурсивных) функций.

Доказательство. Допустим, что существует примитивно рекурсивная универсальная функции u(x,t₁,…,t_n) для класса всех n-местных примитивно рекурсивных функций. Тогда определим новую n-местную функцию следующим образом: для всех x,t₁,…,t_nN

g(t₁,…,t_n)u(t₁,t₁,…,t_n)1.

Функция g примитивно рекурсивна, но отлична от каждой n-местной всех n-местных примитивно рекурсивных функций.

Отсюда и из теоремы 1 следует, что существует n-местная общерекурсивная, но не примитивно рекурсивная, функция.

23. Теорема о параметризации

Каждое из сечений f_x, xN, вычислимой двухместной функции f является также вычислимой (одноместной) функцией. Значит, существует номер iN, такой, что f_x_i. Следующая теорема показывает, что номер i можно эффективно вычислить по x. Эта теорема называется теоремой о параметризации (или простой формой s-m-n-теоремы).

Теорема 1. Пусть f(x,t) – вычислимая функция. Тогда существует всюду определенная вычислимая функция k(x), такая, что f_x_k(x).

(Неформальное) доказательство. Пусть МНР T_a с программой F вычисляет функцию f. Определим МНР с новой программой:

команды		конфигурации
		t000
I1	T(1,2)	tt00
I2	Z(1)	0t00
I3	S(1)	1t00
I4	S(1)	2t00
…	…	…
Ix2	S(1)	xt00
	F	f(x,t)…

Пусть y – номер этой программы в эффективной нумерации программ МНР, т.е. построили МНР T_y. Определим: yk(x). Эта функция по построению эффективно вычислима. f(x,t)_y(t)_k(x)(t). 

Теорема 1 может быть обобщена следующим образом (в так называемую s-m-n-теорему):

Теорема 2. Пусть f(x₁,…,x_m,t₁,…,t_n) – вычислимая функция. Тогда существует всюду определенная вычислимая функция , такая, что .