A művelet a primitív rekurzió - studopediya

Azt mondjuk, hogy a (n + 1) - helyszíni f függvény nyert N - helyi funkció és a g (n + 2) - a helyi h függvény által a művelet primitív rekurzió ha bármely értékek x1. x2, ..., xn az egyenletet:

Ezek az egyenletek nevezzük a rendszer primitív rekurzió. És az a tény, hogy az f függvény nyert függvény g, h c a művelet primitív rekurzió kerül rögzítésre a következő: F = R (g, h).

Definíció 1. A f függvényt primitív rekurzív függvény, ha kapjuk a kezdeti funkciókat útján szuperpozíció és primitív rekurzió, kombinált véges számú alkalommal bármilyen sorrendben.

Ebből a meghatározásból következik, hogy bármilyen primitív rekurzív függvény egy numerikus funkciót.

A szett a primitív rekurzív függvények jelöljük Pn.p.

5. példa Annak bizonyítására, hogy az f (x, y) = x + y primitív rekurzív.

Valóban. A következő azonosság

Ebből következik, hogy x + y = R (g (x) = x, h (x, y, z) = z + 1). Mivel a funkciók g, h - elemi függvények, akkor x + y Pn.p.

6. példa Annak bizonyítására, hogy az f (x, y) = x # 8729; y primitív rekurzív.

Valóban. A következő azonosságokat:

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

Ebből következik, hogy

Tekintsük az x y =

Ez a funkció az úgynevezett csonka különbség.

7. példa azt mutatja, hogy az f (x, y) = x y primitív rekurzív.

Az elején, tudomásul vesszük, hogy az x 1 primitív rekurzív. valóban:

Ezért, x 1 = R (g (x) = 0, h (x, y) = x). Ennek megfelelően az X 1 Pn.p.

Továbbá, nem nehéz belátni, meghatározása alapján a csonka különbséggel, hogy ezek a funkciók megfelelnek a egyenlőség:

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

minden x és y. Ezek azt mutatják, hogy identitások

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

Mivel a függvény h (x, y, z) = z # 945; Pn.p. Akkor X y Pn.p.

Mivel minden primitív rekurzív függvény egy numerikus függvény, akkor nyilvánvaló, hogy x - y Pn.p.

8. példa azt mutatja, hogy - a primitív rekurzív függvény.

Valóban. Könnyen azt mutatják, hogy = (x y) + (y x). Most, az eredmény következik 5. példa és a 7. példa.

Működés minimalizálás. Azt mondjuk, hogy egy N-hely függvény g (x1, x2, ..., xn) nyert (n + 1) - egy helyi f (x1, x2, ..., xn, y) segítségével a művelet minimalizálása üzemeltető vagy a legkisebb számú, ha bármely x1. x2, ..., xn. y egyenlőség g (x1, x2, ..., xn) = y igaz akkor és csak akkor, ha:

Ha bármely feltétel 1) és 2) lesz beteljesületlen, a g (x1, x2, ..., xn) nincs definiálva a beállított x1. x2, ..., xn .. Röviden, a g (x1, x2, ..., xn) egyenlő a legkisebb érték az érvelés y, amely végre végre egyenlőséget.

A következő jelölést:

Körülbelül a g azt mondják, hogy nyert f függvény segítségével a minimalizálási működését.

Definíció 2 f függvényt egy részlegesen rekurzív függvény, ha lehet beszerezni a kezdeti funkciókat a szuperpozíció művelet, primitív rekurzió és minimálisra venni véges számú alkalommal bármilyen sorrendben.

Az osztály részleges rekurzív függvények jelöljük PRP-értéket.

Pp --- jelölésére egy osztály a rekurzív függvények, azaz a minden numerikus funkciókat PRP.

9. példa Annak bizonyítására, hogy a részlegesen numerikus funkciója részben rekurzív.

Először azt látjuk, hogy ez a funkció nyert funkció minimalizálásával a műveletet, azaz = A.

Szerint a 2. és 4. példa primitív rekurzív függvény. Ez azt jelenti, hogy - a részleges rekurzív függvény.

Ez a példa azt demonstrálja, hogy az osztály PRP lényegesen szélesebb, mint a PP osztály. Azt lehet mondani, hogy az osztály Pp lényegesen szélesebb, mint az osztály PNP, azaz