Una aplicación desde entradas codificadas de manera finita (habitualmente cadenas finitas o números naturales) a salidas para la cual existe un procedimiento finito ejecutable mecánicamente que, para cada entrada válida, se detiene y produce la salida correcta.

Principio

La computabilidad es la existencia de un procedimiento efectivo y finito: una receta única que transforma cualquier entrada permitida en su salida en un número finito de pasos deterministas.

Demostración

La suma de números naturales implementada por una máquina de Turing: dada la codificación de dos números, la máquina termina con la codificación de su suma.

Aplicación incorrecta

Afirmar que una función de valores reales es computable sin especificar una codificación de los reales o un criterio de detención, o confundir rutinas de aproximación numérica con computabilidad exacta.

Consecuencia

Si una función es computable se puede mecanizar su evaluación, probar propiedades de decidibilidad de su grafo e incorporarla en reducciones formales entre problemas de decisión.

Inversión

Una función no computable: no existe un algoritmo finito que se detenga con las salidas correctas para todas las entradas válidas.

Límite

Se aplica sólo a funciones con codificaciones finitas efectivas de entradas/salidas; excluye funciones reales no representadas, modelos con oráculo o hipercomputación y afirmaciones de que aproximaciones probabilísticas implican computabilidad exacta.

Tensión semántica

A menudo se confunde con la decidibilidad de un conjunto (decisión de pertenencia) o con la aproximabilidad numérica; función computable se refiere a la generación explícita de salidas para cada entrada, no sólo a pertenencia a un conjunto o calidad de aproximación.

Síntesis

Una función computable es una correspondencia entre objetos representables finitamente para la cual un único procedimiento mecánico finito proporciona salidas exactas para cada entrada permitida.