Funció computable

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 | modifica el codi]

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 | modifica el codi]

Una funció parcial

 F:\subseteq\mathbb{N}\to\mathbb{N}

es diu computable si la gràfica de  f és un conjunt recursivament enumerable. El conjunt de funcions parcialment computables amb un paràmetre és normalment escrit \mathbf{P}^{(1)} o \mathbf{P} si el nombre de paràmetres és clar del context.

Una funció total

 F:\mathbb{N}\to\mathbb{N}

es diu computable si el gràfic de  f és un conjunt recursiu. El conjunt de funcions totalment computables amb un paràmetre normalment s'escriu \mathbf{R}^{(1)} o \mathbf{R}.

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

 F:\subseteq\mathbb{N}\to\{0,1\}

Comentaris[modifica | modifica el codi]

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

 G:\subseteq\mathbb{N}^k\to\mathbb{N}

Podem fàcilment codificar g en una nova funció

 F:\subseteq\mathbb{N}\to\mathbb{N}

utilitzant una funció de parells.

Exemples[modifica | modifica el codi]

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

Propietats[modifica | modifica el codi]

  • Donats dos 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 \{x\in\Sigma^{*}: f (x) = 1\} és recursiu.