Funcția Primitive recursive, matematică, fandomului alimentat de Wikia
anumite drepturi
Definirea funcțiilor recursive primitive este inductiv. Se compune din specificarea unei clase de funcții recursive primitive inițiale și doi operatori (substituție și recursie primitiv), care permite de a construi noi functii recursive primitive pe baza celor existente.
Printre funcțiile recursive primitive inițiale sunt funcții ale următoarelor trei tipuri:
- Funcția zero a unei variabile, atribuie orice număr natural 0.
- funcția succesor al unei singure variabile, care asociază fiecare număr natural imediat după un număr natural pentru el.
- Funcția, în cazul în care n variabile de a asocia orice set ordonat de numere întregi numere pozitive ale acestui set.
Operatorii de substituție și recursie primitive sunt definite după cum urmează:
- Fie f - o functie recursiva primitiv de m variabile, și g1. GM - un set ordonat de funcții recursive primitive de n variabile fiecare. Apoi, rezultatul înlocuirea funcțiilor la funcția gk f este o funcție h de n variabile, asignează orice set ordonat de numere întregi
- Fie f - o funcție recursivă primitivă a n variabile, și g - o funcție recursivă primitivă a n + 2 variabile. Apoi, rezultatul aplicării operatorului unei perechi de recursie primitiv de f și g este funcția h n + 1 de tipul variabil
exemple Editare
Să subliniem o serie de funcții aritmetice bine-cunoscute, care pot fi considerate ca un recursiv primitiv.
- Adăugarea a două numere întregi poate fi privit ca o funcție recursivă primitivă a două variabile care sunt obținute prin aplicarea operatorului recursie primitive funcții și f, dintre care a doua este obținută prin substituirea funcțiilor de bază în funcția de bază:
- Înmulțirea a două numere întregi poate fi privit ca o funcție recursivă primitivă a două variabile care sunt obținute prin aplicarea operatorului recursie primitive funcții și f, dintre care a doua este obținută prin substituirea funcțiilor de bază și adăugarea funcției:
- Diferența simetrică (valoarea absolută a diferenței) a două numere întregi poate fi privit ca o funcție recursivă primitivă a două variabile care sunt obținute prin aplicarea următoarelor substituții și recursivițătilor primitive:
Limitele conceptului de drept
Orice funcție recursivă primitivă este recursiv. t. e. Gazdă o valoare care corespunde la orice număr de argumente pentru funcția set de numere naturale. Prin urmare, funcția recursivă. recursiv general, nu sunt cunoscute a fi legate de numărul de funcții recursive primitive. Cunoscut, de asemenea, functii recursive care nu sunt recursiv primitive. Un exemplu standard este funcția Ackermann.
Trebuie remarcat, totuși, că o funcție recursivă arbitrară a n variabile pot fi derivate dintr-o funcție recursivă primitivă a n + 1 variabile folosind minimizarea operatorului.