Teorias

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 tesisChurch-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 denúmeros naturales A, o equivalentemente 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 llamadosA-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 usadaspara 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 pueden ser usados para definir una teoría decomplejidad computacional abstracta sobre el conjunto de funciones computables.
Según la tesis Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidos porfunciones 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 deregistros. 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á llamadocomputable si el gráfico de f es un conjunto recursivamente e numerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito o isi el número de parámetros esclaro 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...