Funci?? recursiva
De Viquip??dia
En l??gica matem??tica i computaci??, les funcions recursives' o tamb?? conegudes com funcions recursives-?? s??n una classe de funcions dels nombres naturals en els nombres naturals que son ???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 en quant a poder d'expressi??, per exemple, el c??lcul lambda i les cadenes de Markov.
[edita] 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,z1,z2,...,zn) ??s una funci?? parcial sobre els naturals amb n + 1 arguments x,z1,z2,...zn, la funci?? ??x f ??s la funci?? parcial amb arguments z1,...,zn que retorna el m??s petit x tal que f(0,z1,z2,...,zn),f(1,z1,z2,...,zn),...,f(x,z1,z2,...,zn) estan totes definidies i f(x,z1,z2,...,zn) = 0, si un tal x existeix, en cas contrari ??x f no est?? definida pels valors particulars dels arguments z1,z2,...,zn.
Es pot verificar que l'especificaci?? del m??nim valor d'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 son 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??.
