Funció recursiva

En lògica matemàtica i computació, les funcions recursives o també conegudes com a funcions recursives-μ són una classe de funcions dels nombres naturals en els nombres naturals que són "computables" en un sentit intuïtiu. De fet, en teoria de la computabilitat es demostra que les funcions recursives són precisament les funcions que poden ser calculades amb el formalisme de còmput més general conegut com són les màquines de Turing. Les funcions recursives estan relacionades amb les funcions primitives recursives i la seva definició inductiva es construeix basant-se en les funcions primitives recursives. No tota funció recursiva és primitiva recursiva. L'exemple més conegut és la funció d'Ackermann.

Existeixen altres sistemes formals equivalents quant a poder d'expressió, per exemple, el càlcul lambda i les cadenes de Markov.

Definició

Per definir les funcions recursives es pren la definició de les funcions primitives recursives, per permetre funcions parcials, agregant l'operador de cerca o minimització no acotada com segueix:

Si $f(x,z_{1},z_{2},...,z_{n})$ és una funció parcial sobre els naturals amb $n+1$ arguments $x,z_{1},z_{2},...z_{n}$, la funció μx f és la funció parcial amb arguments $z_{1},...,z_{n}$ que retorna el més petit $x$ tal que $f(0,z_{1},z_{2},...,z_{n}),f(1,z_{1},z_{2},...,z_{n}),...,f(x,z_{1},z_{2},...,z_{n})$ estan totes definidies i $f(x,z_{1},z_{2},...,z_{n})=0$, si un tal $x$ existeix, en cas contrari μx f no està definida pels valors particulars dels arguments $z_{1},z_{2},...,z_{n}$.

Es pot verificar que l'especificació del mínim valor de x, junt amb la resta de la definició idèntica a les funcions primitives recursives, impliquen l'axioma de cerca acotada de les funcions primitives recursives.

El conjunt de les funcions recursives parcials està definit com el més petit conjunt de funcions parcials amb qualsevol nombre d'arguments dels naturals en els naturals que contenen el zero, el successor i les funcions de projecció, tals que la composició, la recursió primitiva i la cerca no acotada són operacions tancades d'aquest conjunt.

El conjunt de les funcions recursives totals és el subconjunt de les funcions recursives parcials que a més són funcions totals.

En la tesi de Church-Turing s'estableix el paral·lelisme entre màquina de Turing que no s'atura per certes entrades i el resultat indefinit d'una funció recursiva parcial. L'operador de cerca no acotada no pot ser definit usant les regles de definició de les funcions primitives recursives, ja que no es disposa en elles d'un mecanisme d'iteració no acotada pel qual podria no trobar-se el resultat d'una funció.