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

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

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

11п : х н-и[п, х)

(«сечение» функции 1} при фиксированном п) является вычислимой и если все вычислимые функции (одного аргумента) встречаются среди 11п. (Напомним, что ни функция II, ни вычислимые функции одного аргумента не обязаны быть всюду определёнными.)

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

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

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

<] Запишем все программы, вычисляющие функции одного аргумента, в вычислимую последовательность ро,р\,... (например, в порядке возрастания их длины). Положим II (г, х) равным результату работы г-ой про­граммы на входе х. Тогда функция и и будет искомой вычислимой универсальной функцией. Сечение \]% бу­дет вычислимой функцией, вычисляемой программой р,-.

Алгоритм, вычисляющий саму функцию II, есть по суще­ству интерпретатор для используемого языка програм-

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

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

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

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

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

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

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

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