## [Función Computable](/es/node/57641) Definición 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 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 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 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 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 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 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 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 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.