Funció computable

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ó

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

$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 ${𝐏}^{(1)}$ o $𝐏$ 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 ${𝐑}^{(1)}$ o $𝐑$.

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

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

• Funció constant f : N ^k ? N , f ( n ₁ ,... n _k ): = n

• Afegir f : N ² ? N , f ( n ₁ , n ₂ ): = n ₁ + n ₂

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