Función computable
De Wikipedia, la enciclopedia encyclopedia
Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing.
Las funciones computables se utilizan para hablar de computabilidad sin hacer referencia a ningún modelo de computación concreto, como las máquinas de Turing o las máquinas de registro. Cualquier definición, sin embargo, debe hacer referencia a algún modelo específico de computación, pero todas las definiciones válidas producen la misma clase de funciones. Los modelos particulares de computabilidad que dan lugar al conjunto de funciones computables son las funciones computables de Turings y las funciones recursivas generales.
Antes de la definición precisa de función computable, los matemáticos utilizaban a menudo el término informal efectivamente calculable. Desde entonces, este término se identifica con las funciones computables. Nótese que la computabilidad efectiva de estas funciones no implica que puedan ser eficientemente calculadas (es decir, calculadas en un tiempo razonable). De hecho, para algunas funciones efectivamente calculables se puede demostrar que cualquier algoritmo que las compute será muy ineficiente en el sentido de que el tiempo de ejecución del algoritmo aumenta exponencialmente (o incluso superexponencialmente) con la longitud de la entrada. Los campos de computabilidad factible y complejidad computacional estudian funciones que pueden ser computadas eficientemente.
Según la tesis de Church-Turing, las funciones computables son exactamente las funciones que pueden calcularse utilizando un dispositivo de cálculo mecánico dadas cantidades ilimitadas de tiempo y espacio de almacenamiento. Equivalentemente, esta tesis afirma que una función es computable si y sólo si tiene un algoritmo. Nótese que un algoritmo en este sentido se entiende como una secuencia de pasos que una persona con tiempo ilimitado y un suministro ilimitado de lápiz y papel podría seguir.
Los axiomas de Blum pueden utilizarse para definir una teoría de la complejidad computacional abstracta sobre el conjunto de funciones computables. En la teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable se conoce como problema de función.