Vés al contingut

Funció computable

De la Viquipèdia, l'enciclopèdia lliure

Les funcions computables són l'objecte bàsic d'estudi de la teoria de la computabilitat i consisteixen en les funcions que poden ser calculades per una màquina de Turing.

Introducció

[modifica]

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ó

[modifica]

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

[modifica]

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

[modifica]
  • Afegir f : N 2 ? N , f ( n 1 , n 2 ): = n 1 + n 2

Propietats

[modifica]
  • 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.