Función computable
Las funciones computables son los objetos básicos de estudio en la teoría de la computabilidad . Las funciones computables son el análogo formalizado de la noción intuitiva de algoritmos , en el sentido de que una función es computable si existe un algoritmo que puede hacer el trabajo de la función, es decir, dada una entrada del dominio de función, puede devolver la salida correspondiente. Las funciones computables se utilizan para discutir la computabilidad sin hacer referencia a ningún modelo concreto de computación , como las máquinas de Turing o las máquinas de registro.. Sin embargo, cualquier definición debe hacer referencia a algún modelo de cálculo específico, 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 Turing y las funciones recursivas generales .
Antes de la definición precisa de función computable, los matemáticos solían utilizar el término informal efectivamente calculable . Desde entonces, este término se ha identificado con las funciones computables. Tenga en cuenta que la computabilidad efectiva de estas funciones no implica que puedan calcularse de manera eficiente (es decir, calcularse dentro de un período de tiempo razonable). De hecho, para algunas funciones efectivamente calculables, se puede demostrar que cualquier algoritmo que las calcule 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 la computabilidad factible yFunciones de estudio de complejidad computacional que se pueden calcular de manera eficiente.
De acuerdo con la tesis de Church-Turing , las funciones computables son exactamente las funciones que se pueden calcular usando un dispositivo de cálculo mecánico con cantidades ilimitadas de tiempo y espacio de almacenamiento. De manera equivalente, esta tesis establece que una función es computable si y solo si tiene un algoritmo. Nótese que un algoritmo en este sentido se entiende como una secuencia de pasos que podría seguir una persona con tiempo ilimitado y un suministro ilimitado de lápiz y papel.
Los axiomas de Blum se pueden utilizar 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 .
La computabilidad de una función es una noción informal. Una forma de describirlo es decir que una función es computable si su valor se puede obtener mediante un procedimiento eficaz . Con más rigor, una función es computable si y solo si existe un procedimiento efectivo que, dado cualquier k - tupla de números naturales, producirá el valor . [1] De acuerdo con esta definición, el resto de este artículo supone que las funciones computables toman como argumentos una cantidad finita de números naturales y producen un valor que es un solo número natural.
Como contrapartida de esta descripción informal, existen múltiples definiciones matemáticas formales. La clase de funciones computables se puede definir en muchos modelos equivalentes de computación , incluyendo