Recursió primitiva

De Viquipèdia
Dreceres ràpides: navegació, cerca

Les funcions recursives primitives es defineixen usant com a operacions principals la recursió i la composició i formen un subconjunt estricte de les funcions recursives, que són les funcions computables. El terme el va proposar originalment en Rózsa Péter.

En Teoria de la computabilitat, les funcions recursives primitives són una classe de funcions que formen un bloc important per la formalització completa de la computabilitat. Aquestes funcions també són importants en Teoria de la demostració.

Moltes de les funcions estudiades a Teoria de nombres i les aproximacions a les funcions de valor real són recursives primitives. Per exemple, la suma, divisió, factorial, exponencial i l'n-èsim primer són funcions recursives primitives. De fet, és difícil definir una funció que sigui recursiva però que no es pugui definir amb recursió primitiva. El conjunt de funcions recursives primitives es coneix com PR en Complexitat computacional.

Tota funció recursiva primitiva és una funció recursiva general.

Definició[modifica | modifica el codi]

Les funcions recursives primitives estan definides sobre el conjunt dels Nombres Naturals, poden tenir un o una n-tupla (n-aria) com arguments i el resultat és un nombre natural.

Aquestes funcions es defineixen amb els següents axiomes:

  1. Funció constant: La funció funció constant 0 (0-aria) és recursiva primitiva.
  2. Funció successor”: La funció 1-aria successora s, que retorna el successor del seu argument (veieu Peano), és recursiva primitiva. És a dir, S(k) = k + 1.
  3. Funció projecció: Per a tot n≥1i per a tot i on 1≤in, la funció projecció n-aria Pin, que retorna el seu iè argument, es recursiva primitiva.

Es poden obtenir funcions recursives primitives més complexes aplicant les operacions donades pels següents axiomes:

  1. Composició: Donat f, una funció recursiva primitiva k-aria, i k m-aria funcions recursives primitives g1,...,gk, la funció composició de f amb g1,...,gk, és a dir, la funció m-aria h(x_1,\ldots,x_m) = f(g_1(x_1,\ldots,x_m),\ldots,g_k(x_1,\ldots,x_m)) \, és una funció recursiva primitiva.
  1. Recursió primitiva: Donat f, una funció recursiva primitiva k-aria, i g, una funció recursiva primitiva (k+2)-aria, la funció (k+1)-aria h es defineix com la recursió primitiva de f i g, és a dir, la funció h és recursiva primitiva quan
    h (0, x_1, \ldots, x_k) = f (x_1, \ldots, x_k) \, i a més
    h (S(y), x_1, \ldots, x_k) = g (y, h (y, x_1, \ldots, x_k), x_1, \ldots, x_k) \,.

Les funcions recursives primitives són les funcions bàsiques i totes aquelles obtingudes de les bàsiques aplicant les operacions anteriors un nombre finit de vegades.

Paper de les funcions de projecció[modifica | modifica el codi]

Les funcions projecció es poden usar per evitar la rigidesa en terms de la aritat de les funcions anteriors; usant composició amb diverses funcions de projecció, és possible passar un subconjunt d'arguments d'una funció a una altra. Per exemple, si g i h són funcions recursives primitives 2-aries llavors

f(a,b,c) = g(h(c,a),h(a,b)) \!

és també una funció recursiva primitiva. Una definició formal usant projeccions seria

f(a,b,c) = g(h(P^3_3(a,b,c),P^3_1(a,b,c)),h(P^3_1(a,b,c),P^3_2(a,b,c))).

Convertint predicats a funcions numèriques[modifica | modifica el codi]

En alguns àmbits és natural considerar les funcions recursives primitives que tenen com arguments tuples on es barregen nombres amb valors veritables (V = Veritat, F= Fals), o que produeixen valors veritables per sortides. Això es pot aconseguir identificant els valors veritables amb nombres d'una manera fixa. Per exemple, és habitual identificar el valor veritable V amb el nombre 1 i el valor veritable F amb el nombre 0. Un cop feta aquesta identificació, la Funció característica del conjunt A, que retorna 1 o 0 es pot veure com un predicat que diu si un nombre és al conjunt A. Aquesta identificació de predicats amb funcions numèriques s'assumeix per la resta de l'article.

Definició de Llenguatge de Computació[modifica | modifica el codi]

Un llenguatge de programació recursiu primitiu és aquell que conté els operadors d'aritmètica bàsica (+ i -), comparacions condicionals (SI-LLAVORS, IGUAL, MENOR-QUE), i bucles delimitats, com el bàsic Bucle For, on hi ha un límit superior conegut o calculable per tots els bucles (PER i DES DE 1 FINS n). No s'admeten estructures de control més generals com Bucle While o SI-LLAVORS més GOTO. Douglas Hofstadter's Bloop introduït a Gödel, Escher, Bach és d'aquest tipus. Afegint bucles no delimitats (WHILE, GOTO) fa el llenguatge parcialment recursiu o Turing-complet; Floop és d'aquests últims, com la majoria de llenguatges de programació existents.

Un programa d'ordinador qualsevol, o una màquina de Turing, en general no pot ser analitzat per saber si s'aturarà o no (el Problema de la parada). Tot i això, totes les funcions recursives primitives s'aturen. Això no és una contradicció: les funcions recursives primitives són un subconjunt no arbitrari de tots els programes possibles, construït expressament per ser analitzable.


Exemples[modifica | modifica el codi]

Moltes funcions de teoria de nombres definides usant recursivitat sobre una sola variable son funcions recursives primitives. Exemples bàsics en són la suma i la resta limitada.

Suma[modifica | modifica el codi]

Intuïtivament, la suma es pot definir recursivament amb les regles:

suma(0,x)=x,
suma(n+1,x)=suma(n,x)+1.

Per definir aquesta definició a una definició més estricte tenim:

suma(0,x)=P11(x) ,
suma(S(n),x)=S(P23(n,suma(n,x),x)).

On P23 és la funció projecció que pren 3 arguments i retorna el segon.

P11 és la funció identitat; La seva inclusió es requereix per la definició de l'operador de recursió primitiva vist abans; fa el paper de f. La composició de S i P23, la qual és recursiva primitiva, fa el paper de g. El terme S(n) es refereix a el successor de n .

Resta[modifica | modifica el codi]

Com que les funcions recursives primitives usen nombres naturals en lloc de nombres enters, i els nombres naturals no estan tancats respecte a la resta, una funció resta limitada és la que s'estudia en aquest context. La funció resta limitada resta(a, b) retorna b – a si és un nombre no negatiu i 0 en altre cas.

La funció predecessor actua com l'oposada a la funció successor, i es defineix recursivament per les regles següents:

pred(0)=0,
pred(n+1)=n.

Aquestes regles es poden convertir a una definició més formal per recursió primitiva:

pred(0)=0,
pred(S(n))=P12(n, pred(n)).

Llavors la funció resta limitada queda difinida fent servir la funció predecessor d'una manera anàloga a com s'ha definit la suma:

resta(0,x)=P11(x),
resta(S(n),x)=pred(P23(n,resta(n,x),x)).

Aquí resta(a,b) es correspon a b-a; per mantenir la simplicitat, l'ordre dels arguments s'ha intercanviat per ajustar-se als requeriments de la recursió primitia. Això es pot corregir fàcilment fent servir composició amb les projeccions adequades.

Altres funcions recursives primitives inclouen Potenciació i Test de primalitat. Donades unes funcions recursives primitives e, f, g, i h, una funció que retorna el valor de g quan ef i el valor d'h en altre cas és recursiva primitiva.