2. Перечислимость и вычислимость

Определение 5.2.1. График функции y=f(x) – множество

F(x,y)={(x,y): y=f(x), x, yN}

перечислим, если существует алгоритм, перечисляющий входящие в него пары, то есть существуют такие общерекурсивные функции (s), (s), что: F(x,y)={(x,y): x=(s), y=(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N}.

Для вычисления f(n) в данной точке nP необходимо.

1. Вычисляя последовательно (0), (1) … , найти первое по порядку число sN такое, что (s)=n. Так как nP, то такое число s обязательно найдется и будет равно

2. Вычислить значение m=(s) и положить f(n)=m.

Таким образом, если график F(x,y) – перечислимое множество, то y=f(x) – вычислимая функция, которая определяется так:

Заметим, что вычисление значения функции в точке, не принадлежащей области определения, приводит к бесконечным вычислениям последовательности (0), (1) … .

Предположим теперь, что функция y=f(x) – вычислима. В этом случае найдется машина Тьюринга T, такая что T(x)= f(x). Тогда в точках, принадлежащих области определения функции, она будет останавливаться и давать точки, принадлежащие графику F(x,y). В точках, не принадлежащих области определения функции, эта машина Тьюринга будет работать бесконечно. Так что график будет перечислимым множеством.

Теорема доказана.

Лекция № 6. Универсальные функции и множества

1. Универсальные функции и множества

2. Главные универсальные функции и множества

1. Универсальные функции и множества

Определение 6.1.1. Функция U двух натуральных аргументов называется универсальной для класса вычислимых функций¹ одного аргумента, если для каждого n функция:

,

является вычислимой функцией, и каждая вычислимая функция одного аргумента встречается среди .

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

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

Теорема доказана.

Определение 6.1.2. Множество называют универсальным для некоторого класса множеств натуральных чисел, если все множества

W_n={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).

Теорема доказана.

Теорема 6.1.6. Существует перечислимое неразрешимое множество.

Доказательство. Область определения F вычислимой функции f(x), не имеющей всюду определенного вычислимого продолжения – перечислимое неразрешимое множество. С одной стороны F – перечислимо. С другой стороны, если бы множество F было бы разрешимо, то функция

была бы всюду определенным продолжением f(x).

Теорема доказана.