Определение 5.2.1. График функции y=f(x) – множество
F(x,y)={(x,y): y=f(x), x, yÎN}
перечислим, если существует алгоритм, перечисляющий входящие в него пары, то есть существуют такие общерекурсивные функции s(s), t(s), что: F(x,y)={(x,y): x=s(s), y=t(s), sÎN}.
Теорема 5.2.1. Функция y=f(x) с непустойобластьюопределения вычислима тогда и только тогда, когда ее график F(x,y)={(x,y): y=f(x), x, yÎN} является перечислимым множеством.
Доказательство. Пусть график F(x,y) некоторой функции y=f(x) является перечислимым множеством. Тогда перечислимым множеством является P – область определения функции y=f(x): P={x: x=s(s), sÎN}.
Для вычисления f(n) в данной точке nÎP необходимо.
1. Вычисляя последовательно s(0), s(1) … , найти первое по порядку число sÎN такое, что s(s)=n. Так как nÎP, то такое число s обязательно найдется и будет равно
2. Вычислить значение m=t(s) и положить f(n)=m.
Таким образом, если график F(x,y) – перечислимое множество, то y=f(x) – вычислимая функция, которая определяется так:
Заметим, что вычисление значения функции в точке, не принадлежащей области определения, приводит к бесконечным вычислениям последовательности s(0), s(1) … .
Предположим теперь, что функция y=f(x) – вычислима. В этом случае найдется машина Тьюринга T, такая что T(x)= f(x). Тогда в точках, принадлежащих области определения функции, она будет останавливаться и давать точки, принадлежащие графику F(x,y). В точках, не принадлежащих области определения функции, эта машина Тьюринга будет работать бесконечно. Так что график будет перечислимым множеством.
¨Теорема доказана.
1. Универсальные функции и множества
2. Главные универсальные функции и множества
Определение 6.1.1. Функция U двух натуральных аргументов называется универсальной для класса вычислимых функций[6] одного аргумента, если для каждого n функция:
,
является вычислимой функцией, и каждая вычислимая функция одного аргумента встречается среди .
Теорема 6.1.1. Существует вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента.
Доказательство. Пусть p0, p1, …pi,...– последовательность программ[7], вычисляющих функции одного аргумента. Положим U(i, x) равным результату работы i-ой программы на входе x. Тогда U(i, x) – универсальнаяфункция.
¨Теорема доказана.
Определение 6.1.2. Множество называют универсальным для некоторого класса множеств натуральных чисел, если все множества
Wn={x: (n, x)ÎW}
принадлежат этому классу, и других множеств в этом классе нет.
Теорема 6.1.2. Существует перечислимое множество пар натуральных чисел, универсальное для класса всех перечислимых множеств натуральных чисел.
Доказательство. Область определения универсальной функции – универсальное перечислимое множество, так как каждое перечислимое множество есть область определения некоторой вычислимой функции.
¨Теорема доказана.
Теорема 6.1.3. Не существует вычислимой всюду определенной функции двух аргументов, универсальной для класса всех вычислимых всюду определенных функций одного аргумента.
Доказательство. Пусть U – произвольная вычислимая всюду определенная функция двух аргументов. Положим u(n)=U(n, n), d(n)=u(n)+1. Всюду определенная функция d(n) отличается от всех , а потому U – не является универсальной.
¨Теорема доказана.
Теорема 6.1.4. Существует вычислимая функция d(n), от которой никакая функция не может отличаться всюду (для любой вычислимой функции найдется nÎN такое, что f(n)=d(n) (равенство понимается в том смысле, либо оба значения f(n) и d(n) не определены, либо оба определены и равны)).
Доказательство. d(n)=U(n, n), где U(n, х) универсальнаяфункция двух аргументов для класса вычислимых функций одного аргумента.
¨Теорема доказана.
Теорема 6.1.5. Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.
Доказательство. Пусть d(n)=U(n, n), где U(n, х) универсальнаяфункция двух аргументов для класса вычислимых функций одного аргумента. Положим g(n)=d(n)+1. Тогда при тех значениях n, гдефункция d(n) определена g(n)¹ d(n) и любое ее продолжение отличается от d. В этом случае предположение о вычислимости всюду определенного продолжения g(n) придет в противоречие с предыдущей теоремой, гласящей об отсутствии вычислимой функции, всюду отличающейся от d(n).
Доказательство. Область определения F вычислимой функции f(x), не имеющей всюду определенного вычислимого продолжения – перечислимое неразрешимое множество. С одной стороны F – перечислимо.С другой стороны, если бы множество F было бы разрешимо, то функция
,
.
называют универсальным для некоторого класса множеств натуральных чисел, если все множества