Les funcions computables són els objectes bàsics d'estudi de la teoria de la computabilitat. Informalment, una funció és computable si existeix un algorisme que en calcula el valor per a cada valor del seu argument. Com que el concepte d'algorisme no té una definició precisa informal, qualsevol definició formal de computabilitat s'ha de referir a un model de computació específic.

S'han proposat molts models de computació; entre els principals hi ha les màquines de Turing, les màquines de registres, el càlcul lambda i les funcions recursives generals. Tot i que aquests quatre models tenen una naturalesa molt diferent, defineixen exactament la mateixa classe de funcions computables. De fet, tots els models de computació generalment acceptats que s'han proposat fins ara es poden simular mitjançant aquests models.

La tesi de Church-Turing és l'afirmació, no demostrable, que tota noció intuïtiva d'algorisme o de procediment efectiu només pot calcular funcions computables en aquest sentit.

Abans de disposar d'una definició precisa de funció computable, els matemàtics sovint utilitzaven el terme informal calculable efectivament. Posteriorment, aquest terme s'ha identificat amb les funcions computables. Tanmateix, que una funció sigui efectivament calculable no implica que es pugui calcular eficientment, és a dir, en un temps raonable. De fet, per a algunes funcions efectivament calculables es pot demostrar que qualsevol algorisme que les calculi és molt ineficient, en el sentit que el seu temps d'execució creix exponencialment —o fins i tot superexponencialment— amb la longitud de l'entrada. Els camps de la computabilitat factible i de la teoria de la complexitat computacional estudien les funcions que es poden calcular eficientment.

Els axiomes de Blum permeten definir una teoria de la complexitat computacional abstracta sobre el conjunt de les funcions computables. En teoria de la complexitat computacional, el problema de calcular el valor d'una funció s'anomena problema de funció, en contrast amb els problemes de decisió, els resultats dels quals només poden ser «sí» o «no».

Introducció Les funcions computables són una formalització de la noció intuïtiva d'algorisme i segons la Tesi de Church-Turing són exactament les funcions que poden ser calculades amb una màquina de càlcul. La noció de la computabilitat d'una funció pot ser relativitzada a un conjunt arbitrari de nombres naturals A , o equivalent a una funció arbitrària f dels naturals als naturals, per mitjà de màquines de Turing esteses per un oracle per A o f . Aquestes funcions pot ser anomenats A-computable o f-computable respectivament. Abans la definició precís d'una funció computable els matemàtics usaven el terme informal efectivament computable .

Les funcions computables són usades per discutir computabilitat sense referir-se a cap model de computació concret, com màquina de Turing o màquina de registres. Els axiomes de Blum poden ser usats per a definir una teoria de complexitat computacional abstracta sobre el conjunt de funcions computables.

Segons la Tesi de Church-Turing, la classe de funcions computables és equivalent a la classe de funcions definides per funcions recursives, càlcul lambda, o algorismes de Markov.

Alternativament es poden definir com els algoritmes que poden ser calculats per una màquina de Turing, una màquina de Post, o una màquina de registres.

A teoria de la complexitat computacional, el problema de determinar la complexitat d'una funció computable aquesta conegut com un problema de funcions.

Definició Una funció parcial

es diu computable si la gràfica de és un conjunt recursivament enumerable. El conjunt de funcions parcialment computables amb un paràmetre és normalment escrit o si el nombre de paràmetres és clar del context.

Una funció total

es diu computable si el gràfic de és un conjunt recursiu. El conjunt de funcions totalment computables amb un paràmetre normalment s'escriu o .

Una funció computable s'anomena predicat computable si és una funció amb valor booleà, és a dir

Comentaris De vegades, per raons de claredat, s'escriu una funció computable com a

Podem fàcilment codificar g en una nova funció

utilitzant una funció de parells.

Exemples Funció constant f : N k ? N , f ( n 1 ,... n k ): = n

Afegir f : N 2 ? N , f ( n 1 , n 2 ): = n 1 + n 2

Màxim comú divisor Identitat de Bézout, una equació diofàntica linear

Propietats El conjunt de les funcions computables és numerable.

Donats dues funcions computables f i g llavors f + g , fg i f o g són funcions computables.

Les funcions computables són definibles aritmèticament.

Una funció amb valor booleà f és un predicat computable si i només si el llenguatge és recursiu.

Demostrabilitat Donada una funció —o, de manera semblant, un conjunt— pot interessar no només si és computable, sinó també si aquest fet es pot demostrar dins d'un sistema de demostració concret, habitualment una teoria de primer ordre com l'aritmètica de Peano. Una funció computable parcial per a la qual es pot demostrar la totalitat s'anomena demostrablement total o demostrablement recursiva.

Si el sistema de demostració és efectivament axiomatitzable, el conjunt de les funcions demostrablement totals és recursivament enumerables: se'n poden enumerar les funcions enumerant totes les demostracions corresponents de la seva totalitat. Això es pot fer enumerant totes les demostracions del sistema i ignorant les que no siguin pertinents.

Relació amb les funcions definides recursivament En una funció definida per una definició recursiva, cada valor es defineix mitjançant una fórmula fixa de primer ordre a partir d'altres valors, ja definits prèviament, de la mateixa funció o d'altres funcions; aquests altres valors poden ser simplement constants. Un subconjunt d'aquestes funcions són les funcions recursives primitives. Un altre exemple és la funció d'Ackermann, que es defineix recursivament però no és recursiva primitiva.

Perquè les definicions d'aquest tipus evitin la circularitat o una regressió infinita, cal que les crides recursives a la mateixa funció es facin amb arguments més petits segons algun ordre parcial ben fonamentat sobre el domini de la funció. Per exemple, per a la funció d'Ackermann , sempre que la definició de es refereix a , es compleix que respecte de l'ordre lexicogràfic sobre parells de nombres naturals. En aquest cas, i en el de les funcions recursives primitives, el bon fonament de l'ordre és evident; tanmateix, algunes relacions de «referència a» no són trivials de demostrar com a ordres ben fonamentats.

Qualsevol funció definida recursivament de manera efectiva sobre un ordre ben fonamentat és computable: cada valor es pot calcular expandint un arbre de crides recursives, i aquesta expansió ha d'acabar després d'un nombre finit de crides. Si no fos així, el lema de Kőnig produiria una seqüència descendent infinita de crides, en contradicció amb la hipòtesi de bon fonament.

Funcions totals que no són demostrablement totals En un sistema de demostració sòlid, tota funció demostrablement total és efectivament total, però el recíproc no és cert. En qualsevol teoria de primer ordre efectivament axiomatitzable, sòlida i prou potent —inclosa l'aritmètica de Peano— es pot demostrar, des d'un sistema metateòric adequat, l'existència de funcions totals que no es poden demostrar totals dins de la teoria considerada.

Si les funcions computables totals s'enumeren mitjançant les màquines de Turing que les produeixen, l'afirmació anterior es pot demostrar —si el sistema de demostració és sòlid— amb un argument de diagonalització semblant a l'utilitzat anteriorment, emprant l'enumeració de funcions demostrablement totals. S'utilitza una màquina de Turing que enumera les demostracions pertinents i que, per a cada entrada n, retorna fn(n) + 1, on fn és la n-èsima funció de l'enumeració, invocant la màquina de Turing que la calcula d'acord amb la n-èsima demostració. Aquesta màquina de Turing té garantit que s'atura si el sistema de demostració és sòlid, però la funció total que calcula no pot coincidir amb cap de les funcions que el sistema demostra totals: altrament, existiria algun n per al qual fn(n) + 1 = fn(n), cosa impossible.

Funcions no computables i problemes irresolubles Tota funció computable disposa d'un procediment finit que proporciona instruccions explícites i no ambigües sobre com calcular-la. A més, aquest procediment s'ha de codificar mitjançant l'alfabet finit emprat pel model de computació; per tant, només hi ha numerablement moltes funcions computables. Per exemple, les funcions es poden codificar mitjançant una cadena de bits, amb l'alfabet }.

Els nombres reals són no numerables i, per tant, la majoria dels nombres reals no són computables. El conjunt de les funcions finitàries sobre els nombres naturals és no numerable, de manera que la majoria no són computables. Exemples concrets d'aquestes funcions són la funció del castor ocupat, la complexitat de Kolmogórov o qualsevol funció que produeixi les xifres d'un nombre no computable, com la constant de Chaitin.

De manera semblant, la majoria dels subconjunts dels nombres naturals no són computables. El problema de l'aturada va ser un dels primers exemples construïts d'un conjunt d'aquest tipus. L’Entscheidungsproblem, proposat per David Hilbert i Wilhelm Ackermann, preguntava si existia un procediment efectiu per determinar quins enunciats matemàtics —codificats com a nombres naturals— són veritables. Church i Turing van demostrar independentment, durant la dècada de 1930, que aquest conjunt de nombres naturals no és computable. Segons la tesi de Church-Turing, no existeix cap procediment efectiu, és a dir, cap algorisme, que pugui efectuar aquests càlculs.

Extensions de la computabilitat Computabilitat relativa La noció de computabilitat d'una funció es pot relativitzar respecte d'un conjunt arbitrari A de nombres naturals. Una funció f es defineix com a computable en A, o equivalentment, A-computable o computable relativa a A, si satisfà la definició de funció computable amb modificacions que permetin accedir a A com a oracle. Com passa amb el concepte de funció computable, la computabilitat relativa pot rebre definicions equivalents en molts models de computació diferents. Habitualment, això s'aconsegueix complementant el model de computació amb una operació primitiva addicional que pregunta si un enter determinat pertany a A. També es pot dir que f és computable en g identificant g amb el seu graf.

Teoria de la recursió superior La teoria hiperaritmètica estudia els conjunts que es poden calcular a partir d'un nombre ordinal computable d'iteracions del salt de Turing del conjunt buit. Això equival als conjunts definibles tant per una fórmula universal com per una d'existencial en el llenguatge de l'aritmètica de segon ordre; és a dir, als conjunts \(\Delta^1_1\). Alguns models proposats d'hipercomputació poden calcular conjunts hiperaritmètics o classes encara més àmplies de funcions. També s'han estudiat teories de la recursió més generals, com la teoria de la E-recursió, en què qualsevol conjunt pot servir d'argument d'una funció E-recursiva.

Hipercomputació Tot i que la tesi de Church-Turing estableix que les funcions computables inclouen totes les funcions que poden ser calculades mitjançant algorismes efectius, és possible considerar classes més àmplies de funcions que relaxen els requisits que han de complir aquests algorismes. El camp de la hipercomputació estudia models de computació que van més enllà de la computació ordinària de Turing.

Referències

Bibliografia

Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.