Función computábel

As **funcións computábeis** son o obxecto básico de estudo da teoría da computabilidade e son, especificamente, as funcións que poden ser calculadas por unha máquina de Turing.

A computabilidade dunha función é unha noción informal. Un xeito de describila é dicir que unha función é computábel se os seus valores se poden obter por un método efectivo. Máis rigorosamente, unha función f:\mathbb N^k\rightarrow\mathbb N é computábel se e só se existe un procedemento que, dada calquera *k*-tupla \mathbf x de números naturais, producirá o valor f(\mathbf x).

## Introdución 
As funcións computábeis son unha formalización da noción intuitiva de algoritmo e segundo a tese de Church-Turing son exactamente as funcións que poden ser calculadas cunha máquina de cálculo. A noción da computabilidade dunha función pode ser relativizada a un conxunto arbitrario de números naturais *A*, ou equivalentemente a unha función arbitraria *f* dos naturais nos naturais, por medio de máquinas de Turing estendidas cun oráculo por *A* ou *f*. Tales funcións poden ser chamadas *A*-computábeis ou *f*-computábeis respectivamente. Antes da definición precisa dunha función computable os matemáticos empregaban o vocábulo informal *efectivamente computábel*.

As funcións computábeis son usadas para discutir sobre computabilidade sen referirse a ningún modelo de computación concreto, como o da máquina de Turing ou o da máquina de rexistros. Os axiomas de Blum poden ser usados para definir unha teoría de complexidade computacional abstracta sobre o conxunto de funcións computábeis.

Segundo a tese de Church-Turing, a clase de funcións computábeis é equivalente á clase de funcións definidas por funcións recursivas, cálculo lambda, ou algoritmos de Markov .

Alternativamente pódense definir como os algoritmos que poden ser calculados por unha máquina de Turing, unha máquina de Post, ou unha máquina de rexistros.

En teoría da complexidade computacional, o problema de determinar a complexidade dunha función computábel coñécese como un problema de funcións.

## Definicións 
Unha función parcial
: f:D \subseteq \mathbb{N} \to \mathbb{N}
chámase parcialmente computábel se o algoritmo de f é un conxunto recursivamente numerábel. O conxunto de funcións parcialmente computábeis cun parámetro escríbese normalmente \mathbf{P}^{(1)} ou \mathbf{P} se o número de parámetros pode deducirse do contexto.

Unha función total
: f:\mathbb{N} \to \mathbb{N} 
chámase computábel se o algoritmo de f é un conxunto recursivo. O conxunto de funcións totalmente computables cun parámetro normalmente escríbese
\mathbf{R}^{(1)} ou \mathbf{R}.

Unha función computable f chámase predicado computable se é unha función con valor booleano, é dicir:
: f:D \subseteq \mathbb{N} \to \{0,1\}

## Comentarios 
Ás veces, por razóns de claridade, escríbese unha función computable como
: g:D_k \subseteq \mathbb{N}^k \to \mathbb{N}

Pódese facilmente codificar *g* nunha nova función 
: f:D \subseteq \mathbb{N} \to \mathbb{N}
usando unha función de pares.

## Exemplos 
* Función constante *f* : **N***k*→ **N**, *f*(*n*1,...*n**k*) := *n*
* Adición *f* : **N**2→ **N**, *f*(*n*1,*n**2*) := *n*1 + *n*2
* Máximo común divisor
* Identidade de Bézout, unha ecuación diofantiana linear.

## Propiedades 
* O conxunto das funcións computábeis é numerábel. 
* Se f e g son funcións computábeis entón f+g, f \cdot g e f \circ g son funcións computábeis.
* As funcións computábeis son definíbeis aritméticamente.
* Unha función con valor booleano f é un predicado computábel se e só se a linguaxe \{x \in \Sigma^{*} : f(x)=1\} é recursiva.

## Notas 
## Véxase tamén 
### Bibliografía 
* Cutland, Nigel. *Computability*. Cambridge University Press, 1980.
* Enderton, H.B. Elements of recursion theory.  *Handbook of Mathematical Logic* (North-Holland 1977) pp.&nbsp;527–566.
* Rogers, H. *Theory of recursive functions and effective computation* (McGraw–Hill 1967).
* Turing, A. (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. *Proceedings of the London Mathematical Society*, Serie 2, Volume 42 (1936). Reimpreso en M. Davis (ed.), *The Undecidable*, Raven Press, Hewlett, NY, 1965.
### Outros artigos 
* Algoritmo