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 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 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 Turing y las funciones recursivas generales .

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 (es decir, automático) dado un tiempo y un espacio de almacenamiento ilimitados. Más precisamente, todos los modelos de computación que se hayan imaginado pueden calcular únicamente funciones computables, y todas las funciones computables pueden calcularse mediante cualquiera de varios modelos de computación que aparentemente son muy diferentes, como las máquinas de Turing , las máquinas de registros , el cálculo lambda 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. La computabilidad efectiva de estas funciones no implica que puedan calcularse de manera eficiente (es decir, en un 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 las funciones que pueden calcularse 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 describirla es decir que una función es computable si su valor puede obtenerse mediante un procedimiento eficaz . Con más rigor, una función es computable si y solo si existe un procedimiento eficaz que, dada cualquier k - tupla de números naturales, producirá el valor . ^[1] De acuerdo con esta definición, el resto de este artículo presupone 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.${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ ${\displaystyle \mathbf {x}}$${\displaystyle f(\mathbf {x} )}$

Como contraparte de esta descripción informal, existen múltiples definiciones matemáticas formales. La clase de funciones computables se puede definir en muchos modelos de computación equivalentes , incluidos

• Máquinas de Turing
• Funciones μ-recursivas
• Cálculo lambda
• Máquinas de correos ( máquinas Post-Turing y máquinas de etiquetas ).
• Registrar máquinas

Aunque estos modelos utilizan diferentes representaciones para las funciones, sus entradas y sus salidas, existen traducciones entre dos modelos cualesquiera, y por lo tanto 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 estrecha. ^[2] A estas funciones a veces se las denomina "recursivas", para contrastar con el término informal "computables", ^[3] una distinción que surge de una discusión de 1934 entre Kleene y Gödel. ^{[4] p.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 (tal 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 la composición , la recursión primitiva y el operador μ .

De manera equivalente, las funciones computables pueden formalizarse como funciones que pueden calcularse mediante un agente computacional idealizado, como una máquina de Turing o una máquina de registros . Formalmente hablando, una función parcial puede calcularse si y solo si existe un programa de computadora con las siguientes propiedades:${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$

1. Si se define, entonces el programa terminará en la entrada con el valor almacenado en la memoria de la computadora.${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x}}$${\displaystyle f(\mathbf {x} )}$
2. Si no está definido, entonces el programa nunca termina en la entrada .${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x}}$

La característica básica de una función computable es que debe existir un procedimiento finito (un algoritmo ) que indique cómo calcular la función. Los modelos de cálculo enumerados anteriormente ofrecen diferentes interpretaciones de lo que 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 forma similar a como un compilador puede leer instrucciones en un lenguaje de programación y emitir instrucciones en otro lenguaje.

Enderton [1977] da las siguientes características de un procedimiento para calcular una función computable; Turing [1936], Rogers [1967] y otros han dado caracterizaciones similares.

• "Debe haber instrucciones exactas (es decir, un programa), de longitud finita, para el procedimiento". Por lo tanto, cada función computable debe tener un programa finito que describa completamente cómo se calculará la función. Es posible calcular la función simplemente siguiendo las instrucciones; no se requiere adivinar ni tener conocimientos especiales.
• "Si se le da al procedimiento una k -tupla x en el dominio de f , entonces, después de un número finito de pasos discretos, el procedimiento debe terminar y producir f ( x )." Intuitivamente, el procedimiento avanza paso a paso, con una regla específica que cubre lo que se debe hacer en cada paso del cálculo. Solo se pueden llevar a cabo un número finito de pasos antes de que se devuelva el valor de la función.
• "Si se le da al procedimiento una k -tupla x que no está en el dominio de f , entonces el procedimiento podría continuar indefinidamente, sin detenerse nunca. O podría quedarse atascado en algún punto (es decir, una de sus instrucciones no puede ejecutarse), pero no debe pretender producir un valor para f en x ". Por lo tanto, si alguna vez se encuentra un valor para f ( x ), debe ser el valor correcto. No es necesario que el agente computacional distinga los resultados correctos de los incorrectos porque el procedimiento se define como correcto si y solo si produce un resultado.

Enderton continúa enumerando varias aclaraciones de estos tres requisitos del procedimiento para una función computable:

1. En teoría, el procedimiento debe funcionar con argumentos de un tamaño arbitrario. No se supone que los argumentos sean menores que el número de átomos de la Tierra, por ejemplo.
2. El procedimiento debe detenerse después de un número finito de pasos para producir un resultado, pero puede requerir un número arbitrario de pasos antes de detenerse. No se supone ninguna limitación de tiempo.
3. Aunque el procedimiento puede utilizar solo una cantidad finita de espacio de almacenamiento durante un cálculo exitoso, no hay límite en la cantidad de espacio que se utiliza. Se supone que se puede otorgar espacio de almacenamiento adicional al procedimiento siempre que este lo solicite.

En resumen, según este punto de vista, una función es computable si:

El campo de estudios de complejidad computacional funciona con límites prescritos en el tiempo y/o espacio permitidos para 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 denomina computablemente enumerable (sinónimos: recursivamente enumerable , semidecidible ) si existe una función computable f tal que para cada número n , f ( n ) está definida si y solo si n está en el conjunto. Por lo tanto, un conjunto es computablemente enumerable si y solo si es el dominio de alguna función computable. La palabra enumerable se utiliza porque los siguientes son equivalentes para un subconjunto no vacío B de los números naturales:

• B es el dominio de una función computable.
• B es el rango de una función computable total. Si B es infinito, se puede suponer que la función es inyectiva .

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á cada elemento de B.

Dado 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 computablemente enumerable pueden definirse a partir de sus análogos para conjuntos.

En la teoría de la computabilidad en la ciencia de la computación , es común considerar los lenguajes formales . Un alfabeto es un conjunto arbitrario. Una palabra en 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 lenguaje 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 dada está en el lenguaje. Se debe desarrollar algún sistema de codificación que permita que una función computable tome una palabra arbitraria en el lenguaje como entrada; esto generalmente se considera rutinario. Un lenguaje se llama computable (sinónimos: recursivo , decidible ) si hay una función computable f tal que para cada palabra w en el alfabeto, f ( w ) = 1 si la palabra está en el lenguaje y f ( w ) = 0 si la palabra no está en el lenguaje. Por lo tanto, un lenguaje es computable solo en caso de que haya un procedimiento que sea capaz de decir correctamente si hay palabras arbitrarias en el lenguaje.

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 computablemente enumerables de números naturales.

Las siguientes funciones son computables:

• Cada función con un dominio finito ; por ejemplo, cualquier secuencia finita de números naturales.
• Cada función constante f  : N ^k → N , f ( n ₁ ,... n _k ) := n .
• Suma f  : N ² → N , f ( n ₁ , n ₂ ) := n ₁ + n ₂
• El máximo común divisor de dos números
• Un coeficiente de Bézout de dos números
• El factor primo más pequeño de un número.

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 muchas más combinaciones.${\displaystyle \color {Azul}f\circ g}$

Los siguientes ejemplos ilustran que una función puede ser computable aunque no se sepa qué algoritmo la calcula.

• La función f tal que f ( n ) = 1 si hay una secuencia de al menos n cincos consecutivos en la expansión decimal de π , y f ( n ) = 0 en caso contrario, es computable. (La función f es o bien la función constante 1, que es computable, o bien hay una k tal que f ( n ) = 1 si n < k y f ( n ) = 0 si n ≥ k . Toda función de este tipo es computable. No se sabe si hay series arbitrariamente largas de cincos en la expansión decimal de π , por lo que no sabemos cuál de esas funciones es f . Sin embargo, sabemos que la función f debe ser computable.)
• Cada segmento finito de una secuencia no computable de números naturales (como la función Σ de Busy Beaver ) es computable. Por ejemplo, para cada número natural n , existe un algoritmo que calcula la secuencia finita Σ(0), Σ(1), Σ(2), ..., Σ( n ) —en contraste con el hecho de que no existe ningún algoritmo que calcule la secuencia Σ completa , es decir, Σ( n ) para todo n . Por lo tanto, "Imprimir 0, 1, 4, 6, 13" es un algoritmo trivial para calcular Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); de manera similar, para cualquier valor dado de n , existe un algoritmo trivial de este tipo (aunque tal vez nadie lo conozca o lo produzca) para calcular Σ(0), Σ(1), Σ(2), ..., Σ( n ).

La tesis de Church-Turing establece que cualquier función computable a partir de un procedimiento que posea las tres propiedades mencionadas anteriormente es una función computable. Como estas tres propiedades no están enunciadas formalmente, la tesis de Church-Turing no puede demostrarse. Los siguientes hechos se suelen tomar como prueba de la tesis:

• Se conocen muchos modelos de cálculo equivalentes y todos ellos dan la misma definición de función computable (o una versión más débil, en algunos casos).
• No se ha propuesto ningún modelo de cálculo más sólido que, en general, se considere efectivamente calculable .

La tesis de Church-Turing se utiliza a veces en demostraciones para justificar que una función particular es computable mediante una descripción concreta de un procedimiento para el cálculo. Esto se permite 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), puede interesarnos no solo si es computable, sino también si esto se puede demostrar en un sistema de prueba particular (generalmente la 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 demuestran su computabilidad. Esto se puede hacer enumerando todas las pruebas del sistema de pruebas e ignorando las irrelevantes.

En una función definida por una definición recursiva , cada valor se define por una fórmula fija de primer orden de otros valores previamente definidos de la misma función u otras funciones, que pueden ser simplemente constantes. Un subconjunto de estos son las funciones recursivas primitivas . Otro ejemplo es la función de Ackermann , que está definida recursivamente pero no es recursiva primitiva. ^[5]

Para que las definiciones de este tipo eviten la circularidad o la regresión infinita, es necesario que las llamadas recursivas a la misma función dentro de una definición sean a argumentos que sean más pequeños en algún orden parcial correcto en el dominio de la función. Por ejemplo, para la función de Ackermann , siempre que la definición de se refiera a , entonces se refiera al orden lexicográfico en pares de números naturales . En este caso, y en el caso de las funciones recursivas primitivas, el buen orden es obvio, pero algunas relaciones "se refiere a" no son triviales de demostrar como buenos ordenamientos. Cualquier función definida recursivamente de una manera bien ordenada es computable: cada valor se puede calcular expandiendo un árbol de llamadas recursivas a la función, y esta expansión debe terminar después de un número finito de llamadas, porque de lo contrario el lema de König conduciría a una secuencia infinita descendente de llamadas, violando el supuesto de buen orden.${\estilo de visualización A}$${\displaystyle A(x,y)}$${\displaystyle A(p,q)}$${\displaystyle (p,q)<(x,y)}$

En un sistema de prueba sólido , toda función demostrablemente total es de hecho total, pero lo inverso no es cierto: en todo sistema de prueba de primer orden que sea 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 se pueden probar como totales en el sistema de prueba.

Si se enumeran las funciones computables totales mediante las máquinas de Turing que las producen, entonces la afirmación anterior se puede demostrar, si el sistema de pruebas es sólido, mediante un argumento de diagonalización similar al utilizado 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, se 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 pruebas es sólido.

Toda función computable tiene un procedimiento finito que proporciona instrucciones explícitas e inequívocas sobre cómo calcularla. Además, este procedimiento debe estar codificado 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. Véase número computable . El conjunto de funciones finitas sobre los números naturales es incontable, por lo que la mayoría no son computables. Ejemplos concretos de tales funciones son Busy beaver , Kolmogorov complex o cualquier función que dé como resultado los dígitos de un número no computable, como la constante de Chaitin .

De manera similar, la mayoría de los subconjuntos de los números naturales no son computables. El problema de la parada fue el primer conjunto de este tipo que se construyó. El Entscheidungsproblem , propuesto por David Hilbert , preguntaba si existe un procedimiento efectivo 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 un procedimiento efectivo (con un 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 -computable o computable en relación con A ) cuando satisface la definición de una función computable con modificaciones que permiten el acceso a A como un oráculo . Al igual que con el concepto de una función computable, la computabilidad relativa puede recibir definiciones equivalentes en muchos modelos diferentes de computación. Esto se logra comúnmente complementando el modelo de computación con una operación primitiva adicional que pregunta si un entero dado es un miembro de A . También podemos hablar de que f es computable en g identificando g con su gráfico.

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 es equivalente a los conjuntos definidos tanto por una fórmula universal como existencial en el lenguaje de la aritmética de segundo orden y a algunos modelos de Hipercomputación . Incluso se han estudiado teorías de recursión más generales, como la teoría de la E-recursión en la que cualquier conjunto puede usarse como argumento de una función E-recursiva.

Aunque la tesis de Church-Turing plantea que las funciones computables incluyen todas las funciones con algoritmos, es posible considerar clases más amplias de funciones que flexibilicen los requisitos que deben poseer los algoritmos. El campo de la Hipercomputación estudia modelos de computación que van más allá del cómputo de Turing normal.

• Número computable
• Método eficaz
• Teoría de la computación
• Teoría de la recursión
• Grado de Turing
• Jerarquía aritmética
• Hipercomputación
• Algoritmo superrecursivo
• Función semicomputable

• Cutland, Nigel. Computabilidad . Cambridge University Press, 1980.
• Enderton, HB Elementos de la teoría de la recursión. Handbook of Mathematical Logic (Holanda del Norte 1977) págs. 527–566.
• Rogers, H. Teoría de funciones recursivas y computación efectiva (McGraw–Hill 1967).
• Turing, A. (1937), On Computable Numbers, With an Application to the Entscheidungsproblem. Actas de la London Mathematical Society , Serie 2, Volumen 42 (1937), págs. 230-265. Reimpreso en M. Davis (ed.), The Undecidable , Raven Press, Hewlett, NY, 1965.