Funcions recursives primitives

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 a PR en Complexitat computacional.

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

Definició

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ó constant 0 (0-aria) és recursiva primitiva.
2. Funció successor”: La funció 1-aria successora s, que retorna el successor del seu argument (vegeu 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≤i≤n, la funció projecció n-aria P_iⁿ, que retorna el seu iè argument, és 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 g₁,...,g_k, la funció composició de f amb g₁,...,g_k, é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ó

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_{1}^{3}(a,b,c)),h(P_{1}^{3}(a,b,c),P_{2}^{3}(a,b,c))).$

Convertint predicats a funcions numèriques

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ó

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

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

Suma

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 estricta tenim:

suma(0,x)=P₁¹(x) ,

suma(S(n),x)=S(P₂³(n,suma(n,x),x)).

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

P₁¹ é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 P₂³, la qual és recursiva primitiva, fa el paper de g. El terme S(n) es refereix a el successor de n .

Resta

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))=P₁²(n, pred(n)).

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

resta(0,x)=P₁¹(x),

resta(S(n),x)=pred(P₂³(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 e≤f i el valor d'h en altre cas és recursiva primitiva.