Знайте, Intuit, лекции алгоритми частични рекурсивни функции
Лема на рекурсивни функции
В този раздел ще се установят примитивен (частично) recursiveness някои важни класове функции - маси и номерация, както и капацитета на определени функции с помощта на сумиране, продукт, анализ на случаи и взаимна рекурсия.
Лема 8.1. Recursiveness таблични функции. Нека навсякъде дефинирана функция е (х) на всички аргументи, но краен брой, равен на константа в (таблица извикване на функция). След това е примитивно рекурсивни.
Доказателство: Нека функцията F на лема. Доказателство за това е чрез индукция на NF.
Ако NF = 0, функция F е константа и следователно примитивен рекурсивно (Пример 8.1).
Да предположим, че всички на масата със стойността на гр нг <= k примитивно рекурсивны и пусть nf = k +1 и f(0)=a. Определим табличную функцию f ' (x) = f(x+1). Ясно, что nf' = k. и по предположению индукции f ' примитивно рекурсивна. Легко проверить, что тогда f задается следующей схемой:
и следователно и примитивно рекурсивни.
Ще покажем, затворен кръг PRF (P.r.f.) по отношение на операциите на сумиране и продукта.
Лема 8.2. Сумиране и продукт. Да предположим, че функцията F (х1. Xn. Y) е частично (примитивни) рекурсивно. Тогава функция F п + 1 и G N + 1. определена от следните уравнения
Това е частично (примитивни) рекурсивно.
Доказателство В действителност, тези функции се определят от следните примитивни рекурсивни схеми:
Примери за използване на Лема 8.2.
Пример 8.10. max_deg_div (х, у) = максимална степен на х. който се дели на база.
Нека ехр (х, у) - експоненциална функция. Exp (х, у) = х у. Нейната примитивен recursiveness лесен за инсталиране, като използвате функцията за умножение (вж. Задачата 8.1 (а)). След това е лесно да се провери, че желаната функция се изчислява по формулата
и поради това, че е примитивно рекурсивни.
Пример 8.11. Limited минимизиране. Нека примитивна рекурсивна функция г (х, у), така че за всеки х съществува у <= x. для которого g(x,y) =0. Положим F(x) = mu y [g(x,y) = 0] .
След това, по дефиниция, F (х) е частично рекурсивна функция. Ние показваме, че в действителност, това е примитивно рекурсивни. В действителност, ние определяме. Чрез Лема 8.2, тази функция е примитивен рекурсивно. Да предположим, че за даден х. Тогава за аз
Лема 8.3. По части задача или анализ на случаите. Нека h1 (x1. Xn). HK (x1 х н.) - произволна PRF и навсякъде определено PRF f1 (х1. хп). FK (х1. хп), така че на всеки набор от аргументи (а1. и), един и само един от тези функции е равен на 0. След това функция г (х1. хп). определена от отношенията:
Това е частично рекурсивно.
Доказателство Всъщност г п може да бъде представена като сума от к Работи:
На следващия клас от функции, които ни интересуват - тя функционира за уникална идентификация на двойки и на М-кортежи от числа и да ги върне. Определяне на всяка двойка числа (х, у) неговия номер с2 (х, у) = 2 х (2y + 1) - 1. Например, с2 (0,0) = 0, с2 (1,0) = 1, с2 (0,1) = 2, с2 (1,1) = 5, с2 (2,1) = 19. Поради уникалността на номера разлагане в основните фактори функция с2. N 2 -> N биективен цели числа двойки. Лесно е да се разбере, че ако с2 (х, у) = Z. тогава двоичен номер (Z + 1) е следната: (двоично нотация Y) 10 х. От тази гледна точка, вие еднозначно да извлечете стойността на х и у. Тези стойности се определят от следните обратни функции:
От тези определения следва непосредствено, че за всеки Z с2 равенство (с21 (Z), С22 (Z)) = Z.
Сега се определи чрез индукция функция CN номериране п-кортежи на числа с п> 2, и техни обратни функции CNI координират (1 <= i <= n) :
От тези определения също директно следва, че за всяко Z имат уравнение КН (Cn1 (Z), CN2 (Z). CNN (Z)) = Z. (Вижте това чрез индукция на п собственост.)
Лема 8.4. Recursiveness номериране функции. За всеки п> = 2, и 1 <= i <= n все определенные выше функции cn и cni являются примитивно рекурсивными.
Доказателство примитивен рекурсивен с2 (х, у) е разположен директно (вж. Проблем 8.1 (а)). с21 (Z) се дава от C21 функция (Z) = max_deg_div (2, Z + 1) е рекурсивен примитивен (показано в Пример 8.10). За С22 функция (Z) притежава определение с22 (Z) = DIV (2, DIV (2 C21 (Z)>, Z + 1) - 1) (тук ние използваме примитивен recursivity число разделяне функция DIV (х, у) на проблема 8.1 (д)). Примитивните функции recursivity останалата номерация следва по индукция от техните определения (вж. Задачата 8.10).
В следващата лема обобщава операторът на примитивна рекурсия.
Лема 8.5. (Co-рекурсия) приемем, че fynktsii и fynktsii примитивното pekypsivny. След fynktsii f1 п + 1 (х1. Xn. Y). FK п + 1 (х1. хп. у). която се определя от съвместното sledyyuschey pekypsiey
(1 <= i <= k) также являются пpимитивно pекypсивными.
Доказателство Нека chepez nabop променливи са x1. хп. Ще дефинираме sledyyuschey примитивното pekypsivnye fynktsii :, и сложи
Fynktsiya F N + 1 polychilos pekypsiey примитивното от примитивни pekypsivnyh fynktsy и следователно pekypsivna самата примитивни. Sppavedlivost Лема tepep sledyet от факта, че за всеки.
Задача 8.1. Покажете, че следните функции са част от (примитивна) рекурсивно.
- Exp (х, у) = х у;
- факт (х) = х. ;
- мин (х, у) = минимум на х и у;
- макс (х, у) = по-голяма от х и у;
- DIV (х, у) = коефициент на база на х (нека DIV (0, у) = у).
предикати равенство и неравенство:
Задача 8.3. смяна на оператора. Нека г (x1 х н.) - част (примитивна) рекурсивни функции. а и б> 0 - броят на N. Тогава функцията
Това е частично (примитивни) рекурсивно.
Задача 8.4. Покажете, че следните функции са част от (примитивна) рекурсивно.
- - та корен на п степен на х (число част).
- (Дори при 0 или х = дневник (I, X) = 0).
- р (х) = 1. ако X - просто число, и р (х) = 0. ако х е съставна.
- PN (к) - к тата просто число във възходящ ред (PN (0) = 0, р (1) = 2, р (2) = 3, р (3) = 5.).
- т (х) = х брой postseismic брой делители (т (0) = 0).
- г (п, m, I) - и -та марка в разлагането на m -ary п. т.е. ако, където 0 <= ai <= m-1. то d(n,m,i)=ai .
- кимане (х, у) = най-голям общ делител на числата х и у (нека кимане (0, у) = кимане (х, 0) = 0).
Задача 8.5. Нека F (X), определена от отношения F на (0) = 1, F (1) = 1, F (х + 2) = F (X) + F (х + 1) (елементи последователност F (х), наречена Фибоначи номера) , Покажете, че функцията F (х) е примитивно рекурсивни.
(Забележка:. Показват първо, че функцията г (х) = 2 F (х) 3 F (х + 1) примитивен рекурсивни)
Задача 8.6. Докаже, че ако стойността на промяна обща рекурсивна функция е (х) в последната, след това получената функция F '(х) е рекурсивно.
Задача 8.7. Докаже, че функцията о (х) = 0, и от избора на функция Im п (х1. Xn) = х чрез наслагване и примитивен рекурсия не може да получава функцията и (х) = х + 1 и г функция (х) = 2 * х.
Задача 8.8. Нека г (х1 хп, у.) - е примитивен рекурсивно. Докажете, че функцията