Funcții recursive
Vom lua în considerare doar funcțiile numerice, adică funcțiile ale căror argumente și valori aparțin setului de numere naturale N (N = 0,1,2, ...).
Dacă domeniul de definire a unei funcții coincide cu un set, atunci funcția este numită peste tot definită, altfel este definită parțial.
f (x, y) = x + y este o funcție definită peste tot,
f (x, y) = x-y este o funcție parțial definită, deoarece este definită doar pentru.
O definiție recursivă a unei funcții este o definiție în care valoarea unei funcții pentru aceste argumente este determinată de valorile aceleiași funcții pentru argumentele mai simple sau de valorile funcțiilor mai simple.
1. Numerele Fibonacci (1, 1, 2, 3, 5, 8, ...) este o secvență de numere f (n), unde f (0) = 1, f (1) = 1, f (n + 2) = f (n) + f (n + 1).
2. Factorial (n! = 1 * 2 * 3 * ... * n) f (0) = 1, f (n + 1) = f (n) * (n + 1).
Funcțiile recursive sunt construite pe baza a trei funcții primitive (evident clar înțelese și realizabile). Ele sunt numite și protozoare.
1. S (x) = x + 1 este funcția succesor.
Exemple. S (0) = 1, S (1) = 2, S (-5) nu este definită.
2. O (x) = 0 este o funcție zero;
Exemple: O (0) = 0, O (1) = 0, O (-5) nu este definită.
3. Im (x1, x2, ..., xn) = xm, (m = 1,2, ... n) este funcția de proiectare (alegerea argumentului).
Cu funcții primitive, pot fi efectuate diverse manipulări folosind trei operatori: suprapunere, recursiune primitivă și minimizare.
1. Operatorul de suprapunere (substituție).
Fie f - funcția m-loc, g1, ... GM - operațiuni n-locală pe platoul de filmare N. operatorul superpoziție S atribuie operațiunile f și g1, ... GM-n locale funcție h.
1) Folosind operatorul suprapus, puteți obține orice constanță.
S (S ... (O (x)) ...) = 0 + n, unde numărul de încorporări ale funcțiilor de secvență n.
2) Folosind operatorul suprapus, putem trece la constanta n.
2. Operatorul primitiv de recursiune
Fiecare operator R (n + 2) Operațiunile de -place Operațiuni f și n-locale atribuie g (n + 1) = h operațiune locuri R (f, g), satisface următoarea schemă:
Pentru n = 0, schema primitivă de recursiune arată ca:
, unde a este o constantă,
Exemplu: Calculul factorialului folosind operatorul primitiv de recursiune va arăta astfel.
Schema de forme primitive proces recursie pentru construirea unei funcții h, în care într-o etapă de zero utilizează o funcție g, iar la fiecare pas succesiv din valoarea funcției f argumentele numerelor y pasul anterior și valoarea funcției h, calculată în etapa anterioară.
O funcție se numește recursiv primitiv (PRP) dacă poate fi obținută din cele mai simple funcții folosind operatorul suprapus sau operatorul primitiv de recursiune.
1) este o funcție primitivă recursivă.
Schema de recursiune primitivă:
2) este o funcție primitivă recursivă.
3. Operatorul de minimizare (-operator)
, unde y este variabila selectată.
Activitatea operatorului poate fi descrisă după cum urmează. Variabila y este alocată, apoi variabilele rămase sunt fixe. Valoarea lui y crește consecutiv, începând de la 0. Valoarea operatorului va fi valoarea lui y la care funcția a fost prima dată transformată la 0.
Dacă funcția nu revine la 0 sau are o valoare negativă, valoarea -operator este considerată nedefinită.
Fixați x = 1 și schimbați y.
Funcția f (x1, x2, ..., xn) este parțial recursiv (CHRF) în cazul în care se poate obține din funcțiile inițiale folosind un număr finit de utilizări superpoziției, recurențe primitiv și minimizare.
f (x, y) = x-y este parțială, deoarece nu este definită dacă x Proprietățile diferenței trunchiate. Funcția este primitiv recursivă, deoarece prin schema de recursiune primitivă: Astfel. poate fi obținut din cele mai simple funcții O (x) și Im (x1, ... xn) cu ajutorul celui mai simplu operator R de recursiune R. În cadrul schemei de recursiune primitivă Astfel. funcția poate fi obținută cu ajutorul recursivității primitive din funcții și h (x, y, z) =. Prin urmare, funcția f (x, y) = x-y este o funcție parțial recursivă. Acolo unde o anumită funcție parțial recursivă este general recursivă (RUF). Pentru problemele algoritmice, situația este tipică când este necesar să găsim un algoritm pentru calculul funcției numerice f (x1, ... xn). Functiile numerice ale caror valori pot fi calculate folosind un algoritm sunt numite functii computerizate. Acest concept este intuitiv, deoarece conceptul algoritmului este intuitiv. Funcția f (x1, ... xn) este efectiv calculată dacă există un algoritm prin care putem găsi f (k1, ... kn) dacă k1, ... kn sunt cunoscuți. Teza de doctorat. Orice funcție efectiv computabilă este o funcție parțial recursivă. Formularea tezei bisericești include conceptul de computabilitate eficientă. Prin urmare, nu poate fi nici dovedită, nici înlăturată în sensul matematic. Recursivitatea parțială este o rafinare a conceptului unei funcții computerizate. Cu ajutorul acestuia, puteți rafina sau respinge calculul. Orice funcție parțial recursivă poate fi calculată de Turing și invers.
Articole similare
Trimiteți-le prietenilor: