11 - Рекурсивные функции. Примитивно рекурсивные функции. Предикаты, простые числа и возвратная рекурсия. Частично рекурсивные функции (Конспект лекций), страница 6
Описание файла
Файл "11 - Рекурсивные функции. Примитивно рекурсивные функции. Предикаты, простые числа и возвратная рекурсия. Частично рекурсивные функции" внутри архива находится в папке "Конспект лекций". PDF-файл из архива "Конспект лекций", который расположен в категории "". Всё это находится в предмете "математическая логика и теория алгоритмов" из 4 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "математическая логика и теория алгоритмов" в общих файлах.
Просмотр PDF-файла онлайн
Текст 6 страницы из PDF
Действительно, если для каждого 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ÌÃÒÓ.