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

Пусть F — некоторый класс функций от K переменных. Функцию U(N, X1, …, XK) от K + 1 переменных называют универсальной для класса F, если выполнимы условия:

А) для всякого N ΠN0 выполняется

FN(X1, …, XK) = U(N, X1, …, XK) Î F;

Б) для всякой F(X1, …, XK) Î F существует N ΠN0 такое, что F(X1, …, XK) = U(N, X1, …, XK).

Теорема 15.4. Для класса Ч1 — одноместных частично рекурсивных функций существует универсальная частично рекурсивная функция U(N, X).

Доказательство. Определим U(N, X) =, точнее

U(N, X) =  (15.1)

Данное соотношение определяет частичную функцию. Функция U(N, X) является частично рекурсивной. Действительно, для произвольных (N, X) нужно найти программу PN (эффективная процедура) и применить PN к начальной конфигурации (X, 0, …, 0, …). Если PN ¯, то положить U(N, X) = R1, где R1 — содержимое регистра R1 в заключительной конфигурации. Если PN ­, то считать значение U(N, X) неопределенным. По тезису Черча функция U(N, X) частично рекурсивна. Покажем, что функция U(N, X) универсальна. Поскольку U(N, X) частично рекурсивна, то и FN = U(N, X) для всякого N ΠN0 частично рекурсивна, так как FN получена подстановкой константы вместо первого аргумента. Пусть теперь F(X) — произвольная одноместная частично рекурсивная функция. Тогда по доказанному она может быть вычислена некоторой МПД-программой Р. Пусть N = g(P). Следовательно, F = и значит F = U(N, X), что и требовалось доказать.

Следствие 15.5. Для всякого K ³ 1 существует частично рекурсивная функция UK(N, X1, …, XK) универсальная для всех K-местных частично рекурсивных функций.

Это делается с использованием нумерационных функций. Полагаем

И так далее.

Покажем, например, что функция удовлетворяет нужным условиям. Во-первых, функция U2 — частично рекурсивна, так как является суперпозицией частично рекурсивных функций. Во-вторых, функция частично рекурсивна, так как получается из частично рекурсивной подстановкой константы. Пусть теперь F(X1, X2) — произвольная частично рекурсивная функция. Образуем функцию G(X) = F(L(X), R(X)), где L, R — нумерационные функции. Так как G(X) — частично рекурсивна, то существует N такое, что G(X) = U(N, X). Теперь положим X = P(X1, X2), и тогда имеем

F(X1, X2) = G(P(X1, X2)) = U(N, P(X1, X2)) = ,

Что и требовалось доказать.

Представляет интерес вопрос о существовании универсальной функции для других рассмотренных выше классов Ч0 и ЧПр — общерекурсивных и примитивно рекурсивных функций соответственно.

Теорема 15.6. Не существует общерекурсивной функции UK(N, X1, …, XK), универсальной для класса ЧK0 — K-местных общерекурсивных функций при любом K ³ 1.

Доказательство. Пусть, наоборот, существует такая функция UK(N, X1, …, XK) для некоторого K. Образуем функцию F(X1, …, XK) = = UK(X1, X1, …, XK) + 1. Согласно свойству универсальности существует N0 такое, что

UK(N0, X1, …, XK) = F(X1, …, XK) = UK(X1, X1, …, XK) + 1.

Поскольку данные функции всюду определены, то они определены и при X1, X1 = … = XK = N0. Тогда получаем противоречивое равенство UK(N0, N0, …, N0) = UK(N0, N0, …, N0) + 1. Значит, предположение о существовании универсальной функции ложно, что и требовалось доказать.

В то же время справедлива следующая теорема.

Теорема 15.7. Для каждого K ΠN класс всех K-местных примитивно рекурсивных функций имеет общерекурсивную универсальную функцию.

Доказательство данной теоремы приведено в [11, § 5].

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

Дадим еще одно применение универсальной функции. Пусть F:N0 à N0 — частичная функция. Функцию F0 будем называть Доопределением F, если F0 всюду определена и совпадает с F в ее области определения. Покажем, что рассмотрение частичных вычислимых функций вызвано существом дела, а именно — существуют частичные вычислимые функции, любое доопределение которых делает их невычислимыми.

Теорема 15.8. Существует частично рекурсивная функция F(X), которая не может быть доопределена до общерекурсивной.

Доказательство. Рассмотрим функцию F(X) = , где U — универсальная функция. Данная фунция частично рекурсивна, так как она получается суперпозицией частично рекурсивных функций. Предположим, что существует общерекурсивная функция F0(X), которая является доопределением для F(X). По свойству универсальности U существует N такое, что F0(X) = U(N, X). Поскольку F0(X) всюду определена, то она определена при X = N, и тогда значение U(N, N) определено, и, следовательно, определено значение . Поскольку F0(X) есть доопределение F(X), то в области определения их значения должны совпадать. Поэтому имеем  U(N, N) = F0(X). Однако последнее равенство дает противоречие, так как, если U(N, N) = 0, то , если U(N, N) ¹ 0, то . Значит, допущение о существовании рекурсивного доопределения для функции F(X) приводит к противоречию, что и требовалось доказать.

< Предыдущая		Следующая >