Operația recursivitatii primitiv - studopediya

Noi spunem că (n + 1) - la fața locului Funcția f se obține din n - funcția locală și g (n + 2) - funcția h locală prin recurență primitiv operație, dacă pentru orice valori x1. x2, ..., xn egalitati:

Aceste ecuații sunt numite schema recursivitatii primitive. Iar faptul că funcția f este obținută din funcția g, h c prin operația de recursie primitivă se înregistrează după cum urmează: f = R (g, h).

Definiție 1 O funcție f este numită funcția recursivă primitivă, în cazul în care se obține din funcțiile inițiale prin intermediul superpoziție și recursie primitiv, combinat număr finit de ori în orice ordine.

Din această definiție, rezultă că orice funcție recursivă primitiv este o funcție numerică.

Setul de funcții recursive primitive este notat cu Pn.p.

Exemplul 5 Pentru a dovedi că funcția f (x, y) = x + y recursivă primitive.

Într-adevăr. Următoarea identitate

Rezultă că x + y = R (g (x) = x, h (x, y, z) = z + 1). Deoarece funcțiile g, h - funcțiile elementare, apoi x + y Pn.p.

Exemplul 6. Pentru a dovedi că funcția f (x, y) = x # 8729; recursivă primitive y.

Într-adevăr. Următoarele identitățile:

f (x, y + 1) = x (y + 1) = xy + x = f (x, y) + x

Rezultă că

Să considerăm funcția x y =

Această funcție se numește o diferență trunchiată.

Exemplul 7 arată că funcția f (x, y) = x y recursivă primitive.

La început, observăm că funcția x 1 este recursiv primitiv. într-adevăr:

De aceea, x 1 = R (g (x) = 0, h (x, y) = x). Astfel, x 1 Pn.p.

Mai mult, nu este dificil să se arate, pe baza definiției trunchiat diferența că aceste funcții satisfac egalitatea:

x (y + 1) = (x y) 1 = h (x, y, x y)

pentru toate x și y. Aceste identități arată că

x y = R (g (x) = 0, h (x, y, z) = z # 945;).

Deoarece functia h (x, y, z) = z # 945; Pn.p. , Apoi x y Pn.p.

Deoarece fiecare funcție recursivă primitivă este o funcție numerică, este evident că x - y Pn.p.

Exemplul 8 va arăta că - funcția recursivă primitive.

Într-adevăr. Este ușor de a arăta că = (x y) + (y x). Acum, rezultatul rezultă din Exemplul 5 și Exemplul 7.

minimizarea Funcționare. Spunem că o funcție n-locul g (x1, x2, ..., xn) obținut din (n + 1) - o funcție f locală (x1, x2, ..., xn, y) prin utilizarea operațiunii minimizarea operatorului sau cel mai mic număr, în cazul în care pentru orice x1. x2, ..., xn. egalitatea y g (x1, x2, ..., xn) = y este adevărat dacă și numai dacă:

Dacă oricare dintre condițiile 1) și 2) vor fi îndeplinite, funcția g (x1, x2, ..., xn) nu este definit la un x1 set. x2, ..., xn .. Pe scurt, valoarea g (x1, x2, ..., xn) egală cu cea mai mică valoare a argumentului y, care se efectuează la ultima egalitate.

Utilizați următoarea notație:

Despre funcția g este declarat a fi obținut din funcția f folosind operația de minimizare.

Definiție 2 Funcția f este o funcție parțial recursivă dacă poate fi obținut din funcțiile inițiale prin operația superpoziție, recursivitatea primitive și reducerii la minimum luate număr finit de ori în orice ordine.

Clasa de funcții recursive parțiale este notată Prp.

Pp --- reprezintă o clasă de funcții recursive, adică toate funcțiile numerice PRP.

Exemplul 9. Pentru a dovedi că funcția parțial numerică parțial recursivă.

Mai întâi observăm că această funcție este obținută din funcția prin minimizarea operațiunii, și anume = Meu.

În conformitate cu exemplele 2 și 4 funcții recursive primitive. Acest lucru înseamnă că - o funcție recursive parțială.

Acest exemplu demonstrează că clasa PRP substanțial mai largi decât cele din clasa Pp. Se poate spune că clasa Pp substanțial mai largă decât clasa pnp, adică