11 - Рекурсивные функции. Примитивно рекурсивные функции. Предикаты, простые числа и возвратная рекурсия. Частично рекурсивные функции (1075777), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Действительно, если для каждого n мы можемпроверить, принадлежит оно множеству или нет, то ясен алгоритм и перечисления таких чисел: последовательно просматривая натуральный ряд, мы присваиваем функции значение 1,если число принадлежит множеству, или зацикливаем алгоритм в противном случае. Докажемэтот факт строго.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ИУ-9, МЛТА, 2009-10уч.г.ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ126ÌÃÒÓТеорема 11.18. Существуют рекурсивно перечислимые множества, не являющиеся разрешимыми.

Существуют рекурсивно перечислимые множества, дополнения к которым не являются рекурсивно перечислимыми.J Область определения A предиката f из следствия 11.1 — рекурсивно перечислимое множество. Рассмотрим функцию h(x) = 1(f ((x)), равную 1 на множестве A и не определенную внеA. Если бы множество A было разрешимо, существовал бы предикат χA , равный 1 на A и 0вне A, т.е. функция h имела бы общерекурсивное доопределение. Но тогда и функция f имеетобщерекурсивное доопределение:(f (x), χA (x);f˜(x) =0,¬χA (x).Теорема 11.19 (теорема Поста).

Если множество A и его дополнение рекурсивноперечислимы, то множество A разрешимо.ÌÃÒÓÔÍ-12J Можно выделить случай, когда либо A, либо его дополнение пусто. В этом случае утверждение тривиально. Будем считать, что A 6= ∅, A 6= ∅. Существуют примитивно рекурсивнаяфункция f1 , множество значений которой есть A, и примитивно рекурсивная функция f2 , множество значений которой есть A. Рассмотрим функцию f (x) = µy((f1 (y) = x) ∨ (f2 (y) = x)).Покажем, что она общерекурсивна. Это значит, что для любого x существует такое y, чтолибо f1 (y) = x, либо f2 (y) = x.

Пусть x произвольно. Если x ∈ A, то ∃y(f1 (y) = x) (т.е. x естьзначение f1 ), а если x ∈ A, то y — значение f2 , т.е. ∃y(f2 (y) = x).Таким образом, функция f является общерекурсивной. Рассмотрим общерекурсивный предикат v(x) = (f1 (f (x)) = x). Если x ∈ A, то ∃y(f1 (y) = x) и 6 ∃y(f2 (y) = x). Значит, значениемf (x) является первое же y, для которого f1 (y) = x.

Но тогда f1 (f (x)) = x и v(x) = 1. Пустьx∈/ A. Тогда 6 ∃y(f1 (y) = x) и ∃y(f2 (y) = x). Следовательно, значение f1 (f (x) 6= x, каково бы нибыло значение y. Поэтому v(x) = 0. Мы доказали, что общерекурсивный предикат v являетсяхарактеристической функцией множества A. Следовательно, A разрешимо. IÔÍ-12Поскольку в силу следствия 11.1 функция f не имеет общерекурсивного доопределения, то ипредикат χA не существует, а множество не является разрешимым.Пусть D3 — предикат из нормальной формы Клини для n = 1. Рассмотрим функциюϕ(x) = µyD3 (x, x, y).

Поскольку ϕ образована из примитивно рекурсивного предиката оператором минимизации, она частично рекурсивна. Ее область определения B = {x ∈ N: ∃yD(x, x, y)}.Пусть X — произвольное рекурсивно перечислимое множество. Согласно теореме о нормальной форме его можно определить как область определения функции µyD3 (l, x, y) при некоторомзначении l. Выясняется, что если l ∈ B, т.е. ∃yD(l, l, y), то l ∈ X, а если l ∈/ B, то l ∈/ X.Значит, произвольно взятое рекурсивно перечислимое множество не может быть дополнениемк B и дополнение к B не является рекурсивно перечислимым. IÌÃÒÓÔÍ-12ÌÃÒÓКак показано выше класс рекурсивно перечислимых множеств включает в себя класс разрешимых множеств.

Уточним связь между двумя классами множеств.ÔÍ-12ÔÍ-12Множеством значений этой функции является A ∪ B. IÌÃÒÓÌÃÒÓJ Пусть A и B — области определения функций fA и fB . Тогда область определения, например,функции fA (x)fB (x) есть A ∩ B.Отметим, что при A = ∅ или B = ∅ множество A ∪ B совпадает с B или A, а потомурекурсивно перечислимо. Предположим, что A И B не пусты. Тогда существуют примитивнорекурсивные функции gA и gB , множества значений которых совпадают с A и B. Рассмотримфункцию(gA ([x/2]), x mod 2 = 0;h(x) =gB ((x/2]), x mod 2 6= 0.ÌÃÒÓÔÍ-12ÌÃÒÓ127ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1211. Рекурсивные функцииÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ОГЛАВЛЕНИЕ. . .

. . .рекурсия. . . . . .. . . . . .. . . . . ...........................................................................................112112115119123125ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-1211. Рекурсивные функции11.1. Примитивно рекурсивные функции . . .11.2. Предикаты, простые числа и возвратная11.3. Частично рекурсивные функции .

. . . .11.4. Универсальные рекурсивные функции .11.5. Разрешимые и перечислимые множестваÌÃÒÓÔÍ-12128ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ.

Характеристики

Список файлов лекций