En teoría de la computabilidad funciones computables o funciones Turing-computables son los objetos básicos de estudio. Hacen nuestras nociones intuitivas de algoritmo presicas y según el tesis Church-Turing son exactamente las funciones que pueden ser calculados con una máquina de calculación. La noción de la computabilidad de una función puede ser relativizado a un conjunto arbitrario de números naturales A, o equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas por un oracle por A o f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable matemáticos solían usar el término informal efectivamente computable. Funciones computables son usados para discutir computabilidad sin referir a ningún modelo de computación concreto, como máquina de Turing o máquina de registros. Los axiomas de Blum puede ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables. Según el tesis Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidos por funciones recursivos, calculo de lamda, o algoritmos de Markov. Alternativamente se pueden definir como los algoritmos que pueden ser calculados por máquina de Turing, sístema de Post, o máquina de registros. En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable esta conocido como un problema de funciones.
Una función parcial
está llamado computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito o isi el número de parámetros es claro del contexto.
Una función total
está llamado computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro es normalmente escrito o . Una función computable f está llamado predicado computable si es una función con valor booleano, o sea
A veces, por razones de claridad, escribimos una función computable como
Podemos fácilmente codificar g en una nueva función
usando ana función de pares.
Propiedades • El conjunto de funciones computables contable. • Dados dos funciones computables f yg entonces f+g, fg y fog son funciones computables. • Funciones computables son definibles aritmeticamente. • Una función con valor booleano f es un predicado computable si y solo si el lenguaje es recursivo.
