Las funciones computables son los objetos básicos de estudio de 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 la 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 específico de cálculo, 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 .
Según la tesis de Church-Turing , las funciones computables son exactamente las funciones que se pueden calcular utilizando un dispositivo de cálculo mecánico (es decir, automático) con cantidades ilimitadas de tiempo y espacio de almacenamiento. Más precisamente, cada modelo de computación que alguna vez se haya imaginado puede calcular sólo funciones computables, y todas las funciones computables pueden calcularse mediante cualquiera de varios modelos de computación que son aparentemente muy diferentes, como las máquinas de Turing , las máquinas de registro , el cálculo lambda y el cálculo general. funciones recursivas .
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 ha llegado a identificarse con las funciones computables. La computabilidad efectiva de estas funciones no implica que puedan calcularse eficientemente (es decir, 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 computabilidad factible y complejidad computacional estudian funciones que se pueden calcular de manera eficiente.
Los axiomas de Blum se pueden utilizar para definir una teoría abstracta de la complejidad computacional 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 puede obtenerse mediante un procedimiento efectivo . Con más rigor, una función es computable si y sólo si existe un procedimiento efectivo que, dada cualquier k - tupla de números naturales, produzca el valor . [1] De acuerdo con esta definición, el resto de este artículo supone que las funciones computables toman un número finito de números naturales como argumentos y producen un valor que es un único número natural.
Como contrapartes de esta descripción informal, existen múltiples definiciones matemáticas formales. La clase de funciones computables se puede definir en muchos modelos de cálculo equivalentes , incluidos
Aunque estos modelos utilizan diferentes representaciones para las funciones, sus entradas y sus salidas, existen traducciones entre dos modelos cualesquiera, por lo que cada modelo describe esencialmente la misma clase de funciones, lo que da lugar a la opinión de que la computabilidad formal es natural y no demasiado. angosto. [2] Estas funciones a veces se denominan "recursivas", para contrastar con el término informal "computable", [3] una distinción que surge de una discusión de 1934 entre Kleene y Gödel. [4] pág.6
Por ejemplo, se pueden formalizar funciones computables como funciones μ-recursivas , que son funciones parciales que toman tuplas finitas de números naturales y devuelven un único número natural (como se indicó anteriormente). Son la clase más pequeña de funciones parciales que incluye las funciones constante, sucesora y de proyección, y está cerrada bajo composición , recursión primitiva y el operador μ .
De manera equivalente, las funciones computables pueden formalizarse como funciones que pueden calcularse mediante un agente informático idealizado, como una máquina de Turing o una máquina de registro . Formalmente hablando, una función parcial se puede calcular si y sólo si existe un programa de computadora con las siguientes propiedades:
La característica básica de una función computable es que debe haber un procedimiento finito (un algoritmo ) que indique cómo calcular la función. Los modelos de cálculo enumerados anteriormente dan diferentes interpretaciones de qué es un procedimiento y cómo se utiliza, pero estas interpretaciones comparten muchas propiedades. El hecho de que estos modelos proporcionen clases equivalentes de funciones computables se debe al hecho de que cada modelo es capaz de leer e imitar un procedimiento para cualquiera de los otros modelos, de la misma manera que un compilador es capaz de leer instrucciones en un lenguaje de computadora y emitir instrucciones en otro. otro idioma.
Enderton [1977] ofrece las siguientes características de un procedimiento para calcular una función computable; Turing [1936], Rogers [1967] y otros han dado caracterizaciones similares.
Enderton continúa enumerando varias aclaraciones de estos 3 requisitos del procedimiento para una función computable:
En resumen, según esta visión, una función es computable si:
El campo de los estudios de complejidad computacional funciona con límites prescritos en el tiempo y/o espacio permitido en un cálculo exitoso.
Un conjunto A de números naturales se llama computable (sinónimos: recursivo , decidible ) si existe una función total computable f tal que para cualquier número natural n , f ( n ) = 1 si n está en A y f ( n ) = 0 si n no está en A .
Un conjunto de números naturales se llama computablemente enumerable (sinónimos: enumerable recursivamente , semidecidible ) si existe una función computable f tal que para cada número n , f ( n ) se define si y sólo si n está en el conjunto. Por tanto, un conjunto es computable enumerable si y sólo si es el dominio de alguna función computable. La palabra enumerable se utiliza porque lo siguiente es equivalente para un subconjunto B no vacío de los números naturales:
Si un conjunto B es el rango de una función f entonces la función puede verse como una enumeración de B , porque la lista f (0), f (1), ... incluirá todos los elementos de B .
Debido a que cada relación finita de los números naturales puede identificarse con un conjunto correspondiente de secuencias finitas de números naturales, las nociones de relación computable y relación computable enumerable pueden definirse a partir de sus análogos para conjuntos.
En la teoría de la computabilidad en informática , es común considerar lenguajes formales . Un alfabeto es un conjunto arbitrario. Una palabra de un alfabeto es una secuencia finita de símbolos del alfabeto; el mismo símbolo puede usarse más de una vez. Por ejemplo, las cadenas binarias son exactamente las palabras del alfabeto {0, 1} . Un idioma es un subconjunto de la colección de todas las palabras de un alfabeto fijo. Por ejemplo, la colección de todas las cadenas binarias que contienen exactamente 3 unos es un lenguaje sobre el alfabeto binario.
Una propiedad clave de un lenguaje formal es el nivel de dificultad requerido para decidir si una palabra determinada está en el idioma. Se debe desarrollar algún sistema de codificación que permita que una función computable tome como entrada una palabra arbitraria del idioma; Esto generalmente se considera rutinario. Un idioma se llama computable (sinónimos: recursivo , decidible ) si existe una función computable f tal que para cada palabra w sobre el alfabeto, f ( w ) = 1 si la palabra está en el idioma y f ( w ) = 0 si la palabra no está en el idioma. Por lo tanto, un idioma es computable en caso de que exista un procedimiento que pueda determinar correctamente si hay palabras arbitrarias en el idioma.
Un lenguaje es computablemente enumerable (sinónimos: recursivamente enumerable , semidecidible ) si existe una función computable f tal que f ( w ) se define si y solo si la palabra w está en el lenguaje. El término enumerable tiene la misma etimología que en conjuntos de números naturales computablemente enumerables.
Son computables las siguientes funciones:
Si f y g son computables, entonces también lo son: f + g , f * g , si f es unario , max( f , g ), min( f , g ), arg max { y ≤ f ( x )} y muchos más combinaciones.
Los siguientes ejemplos ilustran que una función puede ser computable aunque no se sepa qué algoritmo la calcula.
La tesis de Church-Turing establece que cualquier función computable a partir de un procedimiento que posea las tres propiedades enumeradas anteriormente es una función computable. Como estas tres propiedades no se declaran formalmente, la tesis de Church-Turing no se puede probar. Los siguientes hechos a menudo se toman como evidencia de la tesis:
La tesis de Church-Turing se utiliza a veces en pruebas para justificar que una función particular es computable dando una descripción concreta de un procedimiento para el cálculo. Esto está permitido porque se cree que todos esos usos de la tesis pueden eliminarse mediante el tedioso proceso de escribir un procedimiento formal para la función en algún modelo de cálculo.
Dada una función (o, de manera similar, un conjunto), uno puede estar interesado no solo si es computable, sino también si esto puede demostrarse en un sistema de prueba particular (generalmente aritmética de Peano de primer orden ). Una función que se puede demostrar que es computable se llama demostrablemente total .
El conjunto de funciones demostrablemente totales es recursivamente enumerable : se pueden enumerar todas las funciones demostrablemente totales enumerando todas sus pruebas correspondientes, que prueban su computabilidad. Esto se puede hacer enumerando todas las pruebas del sistema de prueba e ignorando las irrelevantes.
En una función definida por una definición recursiva , cada valor se define mediante una fórmula fija de primer orden de otros valores previamente definidos de la misma función u otras funciones, que podrían ser simplemente constantes. Un subconjunto de éstas son las funciones recursivas primitivas . Cada una de estas funciones es demostrablemente total: para tal función k-aria f , cada valor se puede calcular siguiendo la definición hacia atrás, de forma iterativa, y después de un número finito de iteraciones (como se puede probar fácilmente), se alcanza una constante.
Lo contrario no es cierto, ya que no toda función demostrablemente total es recursiva primitiva. De hecho, se pueden enumerar todas las funciones recursivas primitivas y definir una función en tal que para todo n , m : en ( n , m ) = f n ( m ), donde f n es la enésima función recursiva primitiva (para k -funciones arias , esto se establecerá en f n ( m , m ... m )). Ahora, g ( n ) = en ( n , n )+1 es demostrablemente total pero no recursivo primitivo, mediante un argumento de diagonalización : si hubiera habido un j tal que g = f j , habríamos obtenido g ( j ) = en ( j , j )+1 = f j ( j )+1= g ( j )+1, una contradicción. (Los números de Gödel de todas las funciones recursivas primitivas pueden enumerarse mediante una función recursiva primitiva, aunque los valores de las funciones recursivas primitivas no pueden enumerarse).
Una de esas funciones, que se puede demostrar como recursiva total pero no como recursiva primitiva, es la función de Ackermann : dado que está definida de forma recursiva, es fácil demostrar su computabilidad (sin embargo, también se puede construir un argumento de diagonalización similar para todas las funciones definidas por definición recursiva). ; por lo tanto, existen funciones totales demostrables que no se pueden definir de forma recursiva [ cita necesaria ] ).
En un sistema de prueba sólido , toda función demostrablemente total es de hecho total, pero lo contrario no es cierto: en todo sistema de prueba de primer orden que sea lo suficientemente sólido y sólido (incluida la aritmética de Peano), se puede probar (en otro sistema de prueba) la existencia de funciones totales que no pueden ser probadas como totales en el sistema de prueba.
Si el total de funciones computables se enumeran a través de las máquinas de Turing que las producen, entonces la afirmación anterior se puede demostrar, si el sistema de prueba es sólido, mediante un argumento de diagonalización similar al usado anteriormente, utilizando la enumeración de funciones demostrablemente totales dada anteriormente. Se utiliza una máquina de Turing que enumera las pruebas relevantes, y para cada entrada n llama a f n ( n ) (donde f n es la n -ésima función según esta enumeración) invocando la máquina de Turing que la calcula de acuerdo con la n -ésima prueba . Se garantiza que una máquina de Turing de este tipo se detendrá si el sistema de prueba es sólido.
Cada función computable tiene un procedimiento finito que proporciona instrucciones explícitas e inequívocas sobre cómo calcularla. Además, este procedimiento debe codificarse en el alfabeto finito utilizado por el modelo computacional, por lo que solo hay un número contable de funciones computables. Por ejemplo, las funciones pueden codificarse utilizando una cadena de bits (el alfabeto Σ = {0, 1 }).
Los números reales son incontables, por lo que la mayoría de los números reales no son computables. Ver número computable . El conjunto de funciones finitas de los números naturales es incontable, por lo que la mayoría no son computables. Ejemplos concretos de tales funciones son Castor ocupado , Complejidad de Kolmogorov o cualquier función que genere los dígitos de un número no computable, como la constante de Chaitin .
De manera similar, la mayoría de los subconjuntos de números naturales no son computables. El problema de detención fue el primero de este tipo que se construyó. El Entscheidungsproblem , propuesto por David Hilbert , preguntaba si existe un procedimiento eficaz para determinar qué enunciados matemáticos (codificados como números naturales) son verdaderos. Turing y Church demostraron de forma independiente en la década de 1930 que este conjunto de números naturales no es computable. Según la tesis de Church-Turing, no existe ningún procedimiento eficaz (con algoritmo) que pueda realizar estos cálculos.
La noción de computabilidad de una función puede relativizarse a un conjunto arbitrario de números naturales A. Una función f se define como computable en A (equivalentemente A -comutable o computable en relación con A ) cuando satisface la definición de función computable con modificaciones que permiten el acceso a A como un oráculo . Al igual que con el concepto de función computable, a la computabilidad relativa se le pueden dar definiciones equivalentes en muchos modelos diferentes de cálculo. Esto comúnmente se logra complementando el modelo de cálculo con una operación primitiva adicional que pregunta si un número entero dado es miembro de A. También podemos hablar de que f es computable en g identificando g con su gráfica.
La teoría hiperaritmética estudia aquellos conjuntos que pueden calcularse a partir de un número ordinal computable de iteraciones del salto de Turing del conjunto vacío. Esto equivale a conjuntos definidos por una fórmula tanto universal como existencial en el lenguaje de la aritmética de segundo orden y a algunos modelos de Hipercomputación . Se han estudiado incluso teorías de recursividad más generales, como la teoría de recursividad E, en la que cualquier conjunto puede utilizarse como argumento para una función recursiva E.
Aunque la tesis de Church-Turing establece que las funciones computables incluyen todas las funciones con algoritmos, es posible considerar clases más amplias de funciones que relajan los requisitos que deben poseer los algoritmos. El campo de la Hipercomputación estudia modelos de computación que van más allá de la computación normal de Turing.
