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  é computábel se e só se existe un procedemento que, dada calquera k-tupla  de números naturais, producirá o valor .

 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

chámase parcialmente computábel se o algoritmo de  é un conxunto recursivamente numerábel. O conxunto de funcións parcialmente computábeis cun parámetro escríbese normalmente  ou  se o número de parámetros pode deducirse do contexto.

Unha función total

chámase computábel se o algoritmo de  é un conxunto recursivo. O conxunto de funcións totalmente computables cun parámetro normalmente escríbese
 ou .

Unha función computable  chámase predicado computable se é unha función con valor booleano, é dicir:


 Comentarios 
Ás veces, por razóns de claridade, escríbese unha función computable como


Pódese facilmente codificar g nunha nova función 

usando unha función de pares.

 Exemplos 
 Función constante f : Nk→ N, f(n1,...nk) := n
 Adición f : N2→ N, f(n1,n2) := n1 + n2
 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  e  son funcións computábeis entón ,  e  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  é 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. 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

Categoría:Análise matemática
Categoría:Funcións
Categoría:Lóxica