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

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

Говорят, что функция U двух натуральных аргументов является универсальной для класса вычислимых функций одного аргумента, если для каждого n функция

("сечение" функции U при фиксированном n) является вычислимой и если все вычислимые функции (одного аргумента) встречаются среди U_n. (Напомним, что ни функция U, ни вычислимые функции одного аргумента не обязаны быть всюду определенными.)

Аналогичное определение можно дать и для других классов функций (одного аргумента): например, функция U двух аргументов будет универсальной для класса всех всюду определенных вычислимых функций одного аргумента, если ее сечения U_n являются всюду определенными вычислимыми функциями одного аргумента и исчерпывают все такие функции. Очевидно, универсальные функции существуют для любых счетных классов (и только для них).

Ключевую роль в этом разделе играет такой факт:

Теорема 6. Существует вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента.

Запишем все программы, вычисляющие функции одного аргумента, в вычислимую последовательность p₀, p₁,... (например, в порядке возрастания их длины). Положим U(i,x) равным результату работы i-ой программы на входе x. Тогда функция U и будет искомой вычислимой универсальной функцией. Сечение U_i будет вычислимой функцией, вычисляемой программой p_i. Алгоритм, вычисляющий саму функцию U, есть по существу интерпретатор для используемого языка программирования (он применяет первый аргумент ко второму, если отождествить программу и ее номер).

15. Все сечения U_n некоторой функции U двух аргументов вычислимы. Следует ли отсюда, что функция U вычислима?

16. Дайте (естественное) определение понятия вычислимой функции трех аргументов, универсальной для класса вычислимых функций двух аргументов, и докажите ее существование.

Для множеств используется аналогичная терминология: множество W ⊂ N x N называют универсальны для некоторого класса множеств натуральных чисел, если все сечения

множества W принадлежат этому классу и других множеств в классе нет.

Теорема 7. Существует перечислимое множество пар натуральных чисел, универсальное для класса всех перечислимых множеств натуральных чисел.

Рассмотрим область определения универсальной функции U. Она будет универсальным перечислимым множеством, поскольку всякое перечислимое множество является областью определения некоторой вычислимой функции U_n.

17. Как построить универсальное множество, исходя из того, что всякое перечислимое множество есть множество значений некоторой функции U_n?

18. Существует ли разрешимое множество пар натуральных чисел, универсальное для класса всех разрешимых множеств натуральных чисел?

Дата добавления: 2015-10-24