Действието на примитивна рекурсия - studopediya

Ние се каже, че (п + 1) - точкова функция F се получава от N - местно функция и г (п + 2) - местно функция часа от операция примитивен рекурсията, ако за всяка стойности x1. x2, ..., хп на равенства:

Тези уравнения се наричат ​​схемата на примитивна рекурсия. А фактът, че функцията F се получава от функция G, Н С чрез операцията примитивен рекурсия се записва, както следва: F = R (G, Н).

Определение 1. функция е се нарича примитивна рекурсивна функция, ако е получен от първоначалните функции чрез наслагване и примитивен рекурсия, комбинирани определен брой пъти в произволен ред.

От тази дефиниция следва, че който и да е примитивно рекурсивни функция е числова функция.

Наборът от примитивни рекурсивни функции е обозначен с Pn.p.

Пример 5 За да се докаже, че F функция (х, у) = х + у примитивен рекурсивно.

В действителност. Следващият самоличността

От това следва, че х + у = R (г (х) = х, Н (х, Y, Z) = Z + 1). Тъй като г функции, з - елементарни функции, тогава х + у Pn.p.

Пример 6 За да се докаже, че функцията е (х, у) = х # 8729 на у примитивен рекурсивния.

В действителност. Следващите самоличността:

е (х, у + 1) = х (у + 1) = XY + х = F (х, у) + х

От това следва, че

Разглеждане функция х у =

Тази функция се нарича пресечена разлика.

Пример 7 показва, че функцията е (х, у) = х у примитивен рекурсивно.

В началото, ние отбелязваме, че функция х 1 е примитивно рекурсивни. наистина:

Следователно, х = 1, R (г (х) = 0, Н (х, у) = х). Така х 1 Pn.p.

Освен това, не е трудно да се покаже, въз основа на разликата в дефиниция скъсен, че тези функции отговарят равенство:

х (у + 1) = (х у) 1 = Н (х, у, х у)

за х и у. Тези идентичности показват, че

х у = R (г (х) = 0, Н (х, Y, Z) = Z # 945).

Тъй като функция H (X, Y, Z) = Z # 945; Pn.p. , След х у Pn.p.

Тъй като всеки примитив рекурсивна функция е цифрова функция, е очевидно, че х - у Pn.p.

Пример 8 ще покаже, че - примитивното рекурсивна функция.

В действителност. Лесно е да се покаже, че = (х у) + (у х). Сега, резултатът следва от пример 5 и Пример 7.

Операция минимизиране. Ние казваме, че п-място функция грама на (х1, х2, ..., хп), получен от (п + 1) - местен функция F (х1, х2, ..., хп, у) с помощта на операцията минимизиране оператор или най-малък брой, ако за всеки x1. x2, ..., хп. Y равенство г (х1, х2, ..., хп) = у е вярно, ако и само ако:

Ако някое от условията 1) и 2) ще бъде неизпълнени, функция г (х1, х2, ..., хп) не е определена на набор x1. x2, ..., хп .. С две думи, стойността на г (x1, x2, ..., Xn), равна на най-малката стойност на аргумент у, което се извършва най-накрая равенство.

Използвайте следната нотация:

За функция г се казва, че да се получи от функцията е използване операция на минимизиране.

Определяне 2 Функция е е частично рекурсивна функция, ако може да бъде получена от първоначалните функции от операцията наслагване, примитивен рекурсията и минимизиране взети определен брой пъти в произволен ред.

Класът на частични рекурсивни функции е означен PRP.

Pp --- означава един клас на рекурсивни функции, т.е. всички числови функции на PRP.

Пример 9. За да се докаже, че частично цифров рекурсивен функция частично.

Първо, имайте предвид, че тази функция се получава от функцията чрез свеждане до минимум на операцията, т.е. = Ми.

Съгласно примери 2 и 4 примитивен рекурсивна функция. Това означава, че - частично рекурсивна функция.

Този пример показва, че класът на PRP значително по-широк от Pp клас. Може да се каже, че този клас Pp значително по-широк от този клас PNP, т.е.