Teoría de la computabilidad

La teoría de la computabilidad , también conocida como teoría de la recursión , es una rama de la lógica matemática , la informática y la teoría de la computación que se originó en la década de 1930 con el estudio de las funciones computables y los grados de Turing . Desde entonces, el campo se ha expandido para incluir el estudio de la computabilidad generalizada y la definibilidad . En estas áreas, la teoría de la computabilidad se superpone con la teoría de la prueba y la teoría de conjuntos descriptivos efectivos .

Las preguntas básicas que aborda la teoría de la computabilidad incluyen:

• ¿Qué significa que una función sobre números naturales sea computable?
• ¿Cómo se pueden clasificar las funciones no computables en una jerarquía según su nivel de no computabilidad?

Aunque existe una superposición considerable en términos de conocimiento y métodos, los teóricos de la computabilidad matemática estudian la teoría de la computabilidad relativa, las nociones de reducibilidad y las estructuras de grados; los del campo de la informática se centran en la teoría de las jerarquías subrecursivas , los métodos formales y los lenguajes formales . El estudio de qué construcciones matemáticas se pueden realizar de manera efectiva a veces se denomina matemáticas recursivas . ^[a]

La teoría de la computabilidad se originó en la década de 1930, con el trabajo de Kurt Gödel , Alonzo Church , Rózsa Péter , Alan Turing , Stephen Kleene y Emil Post . ^{[3] [b]}

Los resultados fundamentales que obtuvieron los investigadores establecieron la computabilidad de Turing como la formalización correcta de la idea informal del cálculo efectivo. En 1952, estos resultados llevaron a Kleene a acuñar los dos nombres de "tesis de Church" ^{[4] : 300} y "tesis de Turing". ^{[4] : 376} Hoy en día, estas se consideran a menudo como una única hipótesis, la tesis de Church-Turing , que afirma que cualquier función que sea computable por un algoritmo es una función computable . Aunque inicialmente era escéptico, en 1946 Gödel argumentó a favor de esta tesis: ^{[5] : 84}

" Tarski ha subrayado en su conferencia (y creo que con razón) la gran importancia del concepto de recursividad general (o computabilidad de Turing). Me parece que esta importancia se debe en gran medida al hecho de que con este concepto se ha conseguido por primera vez dar una noción absoluta a una noción epistemológica interesante, es decir, que no depende del formalismo elegido." ^{[5] : 84  [6]}

Con la definición de cálculo efectivo se obtuvieron las primeras pruebas de que existen problemas matemáticos que no pueden resolverse de manera efectiva . En 1936, Church ^{[7] [8]} y Turing ^[9] se inspiraron en las técnicas utilizadas por Gödel para demostrar sus teoremas de incompletitud; en 1931, Gödel demostró de manera independiente que el problema de Entscheidung no es decidible de manera efectiva. Este resultado mostró que no existe ningún procedimiento algorítmico que pueda decidir correctamente si proposiciones matemáticas arbitrarias son verdaderas o falsas.

Muchos problemas en matemáticas han demostrado ser indecidibles después de que se establecieron estos ejemplos iniciales. ^[c] En 1947, Markov y Post publicaron artículos independientes que mostraban que el problema de palabras para semigrupos no se puede resolver de manera efectiva. Extendiendo este resultado, Pyotr Novikov y William Boone demostraron independientemente en la década de 1950 que el problema de palabras para grupos no es efectivamente solucionable: no hay un procedimiento efectivo que, dada una palabra en un grupo finitamente presentado , decida si el elemento representado por la palabra es el elemento identidad del grupo. En 1970, Yuri Matiyasevich demostró (usando los resultados de Julia Robinson ) el teorema de Matiyasevich , que implica que el décimo problema de Hilbert no tiene una solución efectiva; este problema preguntaba si hay un procedimiento efectivo para decidir si una ecuación diofántica sobre los números enteros tiene una solución en los números enteros.

La principal forma de computabilidad estudiada en el campo fue introducida por Turing en 1936. ^[9] Se dice que un conjunto de números naturales es un conjunto computable (también llamado decidible , recursivo o conjunto computable de Turing ) si hay una máquina de Turing que, dado un número n , se detiene con salida 1 si n está en el conjunto y se detiene con salida 0 si n no está en el conjunto. Una función f de números naturales a números naturales es una función computable (de Turing) o recursiva si hay una máquina de Turing que , en la entrada n , se detiene y devuelve la salida f ( n ). El uso de máquinas de Turing aquí no es necesario; hay muchos otros modelos de computación que tienen la misma potencia de cálculo que las máquinas de Turing; por ejemplo, las funciones μ-recursivas obtenidas a partir de la recursión primitiva y el operador μ.

La terminología para funciones y conjuntos computables no está completamente estandarizada. La definición en términos de funciones μ-recursivas así como una definición diferente de funciones rekursiv por Gödel condujeron al nombre tradicional recursivo para conjuntos y funciones computables por una máquina de Turing. La palabra decidible proviene de la palabra alemana Entscheidungsproblem que se utilizó en los artículos originales de Turing y otros. En el uso contemporáneo, el término "función computable" tiene varias definiciones: según Nigel J. Cutland , ^[10] es una función recursiva parcial (que puede no estar definida para algunas entradas), mientras que según Robert I. Soare ^[11] es una función recursiva total (equivalentemente, recursiva general). Este artículo sigue la segunda de estas convenciones. En 1996, Soare ^[12] dio comentarios adicionales sobre la terminología.

No todos los conjuntos de números naturales son computables. El problema de la detención , que es el conjunto de (descripciones de) máquinas de Turing que se detienen en la entrada 0, es un ejemplo bien conocido de un conjunto no computable. La existencia de muchos conjuntos no computables se desprende del hecho de que solo hay un número contable de máquinas de Turing y, por lo tanto, solo un número contable de conjuntos computables, pero según el teorema de Cantor , hay un número incontable de conjuntos de números naturales.

Aunque el problema de la detención no es computable, es posible simular la ejecución de un programa y producir una lista infinita de los programas que se detienen. Por lo tanto, el problema de la detención es un ejemplo de un conjunto computablemente enumerable (ce) , que es un conjunto que puede enumerarse mediante una máquina de Turing (otros términos para computablemente enumerable incluyen recursivamente enumerable y semidecidible ). De manera equivalente, un conjunto es ce si y solo si es el rango de alguna función computable. Los conjuntos ce, aunque no son decidibles en general, se han estudiado en detalle en la teoría de la computabilidad.

A partir de la teoría de conjuntos y funciones computables descrita anteriormente, el campo de la teoría de la computabilidad ha crecido hasta incluir el estudio de muchos temas estrechamente relacionados. No se trata de áreas de investigación independientes: cada una de estas áreas extrae ideas y resultados de las otras, y la mayoría de los teóricos de la computabilidad están familiarizados con la mayoría de ellas.

La teoría de la computabilidad en lógica matemática se ha centrado tradicionalmente en la computabilidad relativa , una generalización de la computabilidad de Turing definida mediante las máquinas de Turing oráculo , introducidas por Turing en 1939. ^[13] Una máquina de Turing oráculo es un dispositivo hipotético que, además de realizar las acciones de una máquina de Turing normal, es capaz de hacer preguntas a un oráculo , que es un conjunto particular de números naturales. La máquina oráculo solo puede hacer preguntas de la forma "¿Está n en el conjunto del oráculo?". Cada pregunta será respondida inmediatamente correctamente, incluso si el conjunto del oráculo no es computable. Por lo tanto, una máquina oráculo con un oráculo no computable podrá calcular conjuntos que una máquina de Turing sin un oráculo no puede.

De manera informal, un conjunto de números naturales A es reducible por Turing a un conjunto B si hay una máquina oráculo que dice correctamente si los números están en A cuando se ejecuta con B como el conjunto oráculo (en este caso, también se dice que el conjunto A es ( relativamente ) computable a partir de B y recursivo en B ). Si un conjunto A es reducible por Turing a un conjunto B y B es reducible por Turing a A , entonces se dice que los conjuntos tienen el mismo grado de Turing (también llamado grado de insolubilidad ). El grado de Turing de un conjunto da una medida precisa de cuán incomputable es el conjunto.

Los ejemplos naturales de conjuntos que no son computables, incluidos muchos conjuntos diferentes que codifican variantes del problema de detención , tienen dos propiedades en común:

1. Son computablemente enumerables y
2. Cada uno puede traducirse en cualquier otro mediante una reducción de muchos-uno . Es decir, dados los conjuntos A y B , existe una función computable total f tal que A = { x  : f ( x ) ∈ B }. Se dice que estos conjuntos son equivalentes de muchos-uno (o m-equivalentes ).

Las reducciones de muchos-uno son "más fuertes" que las reducciones de Turing: si un conjunto A es reducible de muchos-uno a un conjunto B , entonces A es reducible de Turing a B , pero la recíproca no siempre se cumple. Aunque los ejemplos naturales de conjuntos no computables son todos equivalentes de muchos-uno, es posible construir conjuntos A y B computablemente enumerables tales que A sea reducible de Turing a B pero no reducible de muchos-uno a B . Se puede demostrar que cada conjunto computablemente enumerable es reducible de muchos-uno al problema de la detención, y por lo tanto el problema de la detención es el conjunto computablemente enumerable más complicado con respecto a la reducibilidad de muchos-uno y con respecto a la reducibilidad de Turing. En 1944, Post ^[14] preguntó si cada conjunto computablemente enumerable es computable o equivalente de Turing al problema de la detención, es decir, si no hay ningún conjunto computablemente enumerable con un grado de Turing intermedio entre esos dos.

Como resultados intermedios, Post definió tipos naturales de conjuntos computablemente enumerables como los conjuntos simples , hipersimples e hiperhipersimples. Post demostró que estos conjuntos están estrictamente entre los conjuntos computables y el problema de la detención con respecto a la reducibilidad de muchos a uno. Post también demostró que algunos de ellos son estrictamente intermedios bajo otras nociones de reducibilidad más fuertes que la reducibilidad de Turing. Pero Post dejó abierto el problema principal de la existencia de conjuntos computablemente enumerables de grado de Turing intermedio; este problema se conoció como el problema de Post . Después de diez años, Kleene y Post demostraron en 1954 que existen grados de Turing intermedios entre los de los conjuntos computables y el problema de la detención, pero no pudieron demostrar que ninguno de estos grados contenga un conjunto computablemente enumerable. Muy poco después de esto, Friedberg y Muchnik resolvieron independientemente el problema de Post al establecer la existencia de conjuntos computablemente enumerables de grado intermedio. Este resultado innovador abrió un amplio estudio de los grados de Turing de los conjuntos computablemente enumerables que resultaron poseer una estructura muy complicada y no trivial.

Hay una cantidad incontable de conjuntos que no son computablemente enumerables, y la investigación de los grados de Turing de todos los conjuntos es tan central en la teoría de la computabilidad como la investigación de los grados de Turing computablemente enumerables. Se construyeron muchos grados con propiedades especiales: grados libres de hiperinmunidad donde cada función computable relativa a ese grado está mayorizada por una función computable (no relativizada); grados altos relativos a los cuales se puede calcular una función f que domina cada función computable g en el sentido de que hay una constante c que depende de g tal que g(x) < f(x) para todo x > c ; grados aleatorios que contienen conjuntos algorítmicamente aleatorios ; grados 1-genéricos de conjuntos 1-genéricos; y los grados por debajo del problema de detención de conjuntos computables al límite .

El estudio de grados de Turing arbitrarios (no necesariamente computablemente enumerables) implica el estudio del salto de Turing. Dado un conjunto A , el salto de Turing de A es un conjunto de números naturales que codifican una solución al problema de detención para las máquinas de Turing de oráculo que funcionan con el oráculo A . El salto de Turing de cualquier conjunto es siempre de grado de Turing más alto que el conjunto original, y un teorema de Friedburg muestra que cualquier conjunto que calcule el problema de detención puede obtenerse como el salto de Turing de otro conjunto. El teorema de Post establece una relación estrecha entre la operación de salto de Turing y la jerarquía aritmética , que es una clasificación de ciertos subconjuntos de los números naturales basada en su definibilidad en aritmética.

Gran parte de la investigación reciente sobre los grados de Turing se ha centrado en la estructura general del conjunto de grados de Turing y en el conjunto de grados de Turing que contiene conjuntos computablemente enumerables. Un teorema profundo de Shore y Slaman ^[15] establece que la función que asigna un grado x al grado de su salto de Turing es definible en el orden parcial de los grados de Turing. Un estudio realizado por Ambos-Spies y Fejer ^[16] ofrece una visión general de esta investigación y su evolución histórica.

Un área de investigación en curso en la teoría de la computabilidad estudia las relaciones de reducibilidad distintas de la reducibilidad de Turing. Post ^[14] introdujo varias reducibilidades fuertes , llamadas así porque implican reducibilidad de tabla de verdad. Una máquina de Turing que implemente una reducibilidad fuerte calculará una función total independientemente del oráculo que se le presente. Las reducibilidades débiles son aquellas en las que un proceso de reducción puede no terminar para todos los oráculos; la reducibilidad de Turing es un ejemplo.

Las reducibilidades fuertes incluyen:

Reducibilidad uno a uno : A es reducible uno a uno (o 1-reducible ) a B si existe una función inyectiva computable total f tal que cada n está en A si y solo si f ( n ) está en B .

Reducibilidad de muchos a uno : se trata esencialmente de una reducibilidad de uno a uno sin la restricción de que f sea inyectiva. A es reducible de muchos a uno (o m-reducible ) a B si existe una función computable total f tal que cada n está en A si y solo si f ( n ) está en B .

Reducibilidad de tabla de verdad : A es reducible de tabla de verdad a B si A es reducible de Turing a B mediante una máquina de Turing de oráculo que calcula una función total independientemente del oráculo que se le dé. Debido a la compacidad del espacio de Cantor , esto es equivalente a decir que la reducción presenta una única lista de preguntas (que dependen solo de la entrada) al oráculo simultáneamente, y luego, habiendo visto sus respuestas, es capaz de producir una salida sin hacer preguntas adicionales independientemente de la respuesta del oráculo a las consultas iniciales. También se han estudiado muchas variantes de reducibilidad de tabla de verdad.

En el artículo Reducción (teoría de la computabilidad) se analizan otras reducibilidades (positiva, disyuntiva, conjuntiva, lineal y sus versiones débiles y acotadas) .

La principal investigación sobre las reducibilidades fuertes ha consistido en comparar sus teorías, tanto para la clase de todos los conjuntos computablemente enumerables como para la clase de todos los subconjuntos de los números naturales. Además, se han estudiado las relaciones entre las reducibilidades. Por ejemplo, se sabe que cada grado de Turing es un grado de tabla de verdad o es la unión de infinitos grados de tabla de verdad.

También se han estudiado reducibilidades más débiles que la reducibilidad de Turing (es decir, reducibilidades que están implícitas en la reducibilidad de Turing). Las más conocidas son la reducibilidad aritmética y la reducibilidad hiperaritmética . Estas reducibilidades están estrechamente relacionadas con la definibilidad sobre el modelo estándar de la aritmética.

Rice demostró que para cada clase no trivial C (que contiene algunos conjuntos ce pero no todos) el conjunto índice E = { e : el e ésimo conjunto ce W _e está en C } tiene la propiedad de que el problema de detención o su complemento es reducible a muchos-uno a E , es decir, se puede mapear usando una reducción a muchos-uno a E (ver el teorema de Rice para más detalles). Pero, muchos de estos conjuntos índice son incluso más complicados que el problema de detención. Este tipo de conjuntos se pueden clasificar usando la jerarquía aritmética . Por ejemplo, el conjunto índice FIN de la clase de todos los conjuntos finitos está en el nivel Σ ₂ , el conjunto índice REC de la clase de todos los conjuntos recursivos está en el nivel Σ ₃ , el conjunto índice COFIN de todos los conjuntos cofinitos también está en el nivel Σ ₃ y el conjunto índice COMP de la clase de todos los conjuntos Turing-completos Σ ₄ . Estos niveles de jerarquía se definen de manera inductiva, Σ _{n +1} contiene solo todos los conjuntos que son computablemente enumerables en relación con Σ _n ; Σ ₁ contiene los conjuntos computablemente enumerables. Los conjuntos de índices que se dan aquí son incluso completos para sus niveles, es decir, todos los conjuntos en estos niveles pueden reducirse mediante muchos-uno a los conjuntos de índices dados.

El programa de matemáticas inversas pregunta qué axiomas de existencia de conjuntos son necesarios para demostrar teoremas particulares de las matemáticas en subsistemas de aritmética de segundo orden . Este estudio fue iniciado por Harvey Friedman y fue estudiado en detalle por Stephen Simpson y otros; en 1999, Simpson ^[17] dio una discusión detallada del programa. Los axiomas de existencia de conjuntos en cuestión corresponden informalmente a axiomas que dicen que el conjunto potencia de los números naturales es cerrado bajo varias nociones de reducibilidad. El axioma más débil de este tipo estudiado en matemáticas inversas es la comprensión recursiva , que establece que el conjunto potencia de los naturales es cerrado bajo la reducibilidad de Turing.

Una numeración es una enumeración de funciones; tiene dos parámetros, e y x y da como salida el valor de la función e -ésima en la numeración en la entrada x . Las numeraciones pueden ser parcialmente computables aunque algunos de sus miembros sean funciones computables totales. Las numeraciones admisibles son aquellas en las que se pueden traducir todas las demás. Una numeración de Friedberg (nombrada en honor a su descubridor) es una numeración uno a uno de todas las funciones parcialmente computables; no es necesariamente una numeración admisible. Investigaciones posteriores también trataron con numeraciones de otras clases como clases de conjuntos computablemente enumerables. Goncharov descubrió, por ejemplo, una clase de conjuntos computablemente enumerables para los cuales las numeraciones caen exactamente en dos clases con respecto a los isomorfismos computables.

El problema de Post se resolvió con un método llamado método de prioridad ; una prueba que utiliza este método se llama argumento de prioridad . Este método se utiliza principalmente para construir conjuntos computablemente enumerables con propiedades particulares. Para utilizar este método, las propiedades deseadas del conjunto que se va a construir se dividen en una lista infinita de objetivos, conocidos como requisitos , de modo que satisfacer todos los requisitos hará que el conjunto construido tenga las propiedades deseadas. Cada requisito se asigna a un número natural que representa la prioridad del requisito; por lo que 0 se asigna a la prioridad más importante, 1 a la segunda más importante, y así sucesivamente. Luego, el conjunto se construye en etapas, cada etapa intenta satisfacer uno o más de los requisitos agregando números al conjunto o prohibiendo números del conjunto para que el conjunto final satisfaga el requisito. Puede suceder que satisfacer un requisito haga que otro quede insatisfecho; el orden de prioridad se utiliza para decidir qué hacer en tal caso.

Los argumentos de prioridad se han empleado para resolver muchos problemas en la teoría de la computabilidad y se han clasificado en una jerarquía basada en su complejidad. ^[11] Debido a que los argumentos de prioridad complejos pueden ser técnicos y difíciles de seguir, tradicionalmente se ha considerado deseable probar resultados sin argumentos de prioridad, o ver si los resultados probados con argumentos de prioridad también pueden probarse sin ellos. Por ejemplo, Kummer publicó un artículo sobre una prueba de la existencia de numeraciones de Friedberg sin utilizar el método de prioridad.

Cuando Post definió la noción de un conjunto simple como un conjunto ce con un complemento infinito que no contiene ningún conjunto ce infinito, comenzó a estudiar la estructura de los conjuntos computablemente enumerables bajo inclusión. Esta red se convirtió en una estructura bien estudiada. Los conjuntos computables pueden definirse en esta estructura por el resultado básico de que un conjunto es computable si y solo si el conjunto y su complemento son ambos computablemente enumerables. Los conjuntos ce infinitos siempre tienen subconjuntos computables infinitos; pero, por otro lado, existen conjuntos simples pero no siempre tienen un superconjunto computable coinfinito. Post ^[14] introdujo ya conjuntos hipersimples e hiperhipersimples; más tarde se construyeron conjuntos maximos que son conjuntos ce tales que cada superconjunto ce es una variante finita del conjunto maximo dado o es co-finito. La motivación original de Post en el estudio de esta red fue encontrar una noción estructural tal que cada conjunto que satisface esta propiedad no está ni en el grado de Turing de los conjuntos computables ni en el grado de Turing del problema de detención. Post no encontró tal propiedad y la solución a su problema aplicó métodos de prioridad; en 1991, Harrington y Soare ^[18] finalmente encontraron tal propiedad.

Otra cuestión importante es la existencia de automorfismos en las estructuras de la teoría de la computabilidad. Una de estas estructuras es la de los conjuntos computablemente enumerables bajo inclusión módulo diferencia finita; en esta estructura, A está por debajo de B si y sólo si la diferencia de conjuntos B  −  A es finita. Los conjuntos maximales (tal como se definen en el párrafo anterior) tienen la propiedad de que no pueden ser automórficos respecto de conjuntos no maximales, es decir, si hay un automorfismo de los conjuntos computablemente enumerables bajo la estructura que acabamos de mencionar, entonces cada conjunto maximal se mapea a otro conjunto maximal. En 1974, Soare ^[19] demostró que también se cumple lo inverso, es decir, cada dos conjuntos maximales son automórficos. Por lo tanto, los conjuntos maximales forman una órbita, es decir, cada automorfismo preserva la maximalidad y cualesquiera dos conjuntos maximales se transforman entre sí por algún automorfismo. Harrington dio otro ejemplo de una propiedad automórfica: la de los conjuntos creativos, los conjuntos que son muchos-uno equivalentes al problema de la detención.

Además de la red de conjuntos computablemente enumerables, también se estudian los automorfismos para la estructura de los grados de Turing de todos los conjuntos, así como para la estructura de los grados de Turing de ciertos conjuntos. En ambos casos, Cooper afirma haber construido automorfismos no triviales que asignan unos grados a otros; sin embargo, esta construcción no ha sido verificada y algunos colegas creen que la construcción contiene errores y que la cuestión de si existe un automorfismo no trivial de los grados de Turing sigue siendo una de las principales cuestiones sin resolver en esta área. ^{[20] [16]}

El campo de la complejidad de Kolmogorov y la aleatoriedad algorítmica fue desarrollado durante los años 1960 y 1970 por Chaitin, Kolmogorov, Levin, Martin-Löf y Solomonoff (los nombres se dan aquí en orden alfabético; gran parte de la investigación fue independiente, y la unidad del concepto de aleatoriedad no se entendía en ese momento). La idea principal es considerar una máquina de Turing universal U y medir la complejidad de un número (o cadena) x como la longitud de la entrada más corta p tal que U ( p ) dé como resultado x . Este enfoque revolucionó las formas anteriores de determinar cuándo una secuencia infinita (equivalentemente, función característica de un subconjunto de los números naturales) es aleatoria o no invocando una noción de aleatoriedad para objetos finitos. La complejidad de Kolmogorov se convirtió no solo en un tema de estudio independiente, sino que también se aplica a otros temas como una herramienta para obtener pruebas. Todavía hay muchos problemas abiertos en esta área. ^[d]

Esta rama de la teoría de la computabilidad analizó la siguiente cuestión: Para m y n fijos con 0 <  m  <  n , ¿para qué funciones A es posible calcular para cualesquiera n entradas diferentes x ₁ ,  x ₂ , ...,  x _n una tupla de n números y ₁ , y ₂ , ..., y _n tales que al menos m de las ecuaciones A ( x _k ) = y _k sean verdaderas? Tales conjuntos se conocen como conjuntos ( m ,  n )-recursivos. El primer resultado importante en esta rama de la teoría de la computabilidad es el resultado de Trakhtenbrot de que un conjunto es computable si es ( m ,  n )-recursivo para algún m ,  n con 2 m  >  n . Por otra parte, los conjuntos semirrecursivos de Jockusch (que ya se conocían informalmente antes de que Jockusch los introdujera en 1968) son ejemplos de un conjunto que es ( m ,  n )-recursivo si y sólo si 2 m  <  n  + 1. Hay una cantidad incontable de estos conjuntos y también algunos conjuntos de este tipo que se pueden enumerar computacionalmente pero que no se pueden calcular. Más tarde, Degtev estableció una jerarquía de conjuntos que se pueden enumerar computacionalmente y que son (1,  n  + 1)-recursivos pero no (1,  n )-recursivos. Después de una larga fase de investigación por parte de científicos rusos, este tema se volvió a popularizar en Occidente gracias a la tesis de Beigel sobre las consultas acotadas, que vinculaba el cálculo de frecuencias con las reducibilidades acotadas mencionadas anteriormente y otras nociones relacionadas. Uno de los principales resultados fue la teoría de cardinalidad de Kummer, que establece que un conjunto A es computable si y sólo si existe un n tal que algún algoritmo enumera para cada tupla de n números diferentes hasta n muchas opciones posibles de la cardinalidad de este conjunto de n números intersectados con A ; estas opciones deben contener la cardinalidad verdadera pero dejar afuera al menos una falsa.

Esta es la rama de la teoría del aprendizaje que se basa en la teoría de la computabilidad. Se basa en el modelo de aprendizaje en el límite de E. Mark Gold de 1967 y desde entonces ha desarrollado cada vez más modelos de aprendizaje. El escenario general es el siguiente: dada una clase S de funciones computables, ¿existe un aprendiz (es decir, funcional computable) que genera para cualquier entrada de la forma ( f (0),  f (1), ...,  f ( n )) una hipótesis? Un aprendiz M aprende una función f si casi todas las hipótesis son el mismo índice e de f con respecto a una numeración aceptable previamente acordada de todas las funciones computables; M aprende S si M aprende cada f en S . Los resultados básicos son que todas las clases de funciones computablemente enumerables son aprendibles mientras que la clase REC de todas las funciones computables no es aprendible. Se han considerado muchos modelos relacionados y también el aprendizaje de clases de conjuntos computablemente enumerables a partir de datos positivos es un tema estudiado desde el artículo pionero de Gold en 1967 en adelante.

La teoría de la computabilidad incluye el estudio de nociones generalizadas de este campo, como la reducibilidad aritmética , la reducibilidad hiperaritmética y la teoría de la α-recursión , como la describió Sacks en 1990. ^[21] Estas nociones generalizadas incluyen reducibilidades que no pueden ser ejecutadas por máquinas de Turing pero que, sin embargo, son generalizaciones naturales de la reducibilidad de Turing. Estos estudios incluyen enfoques para investigar la jerarquía analítica que difiere de la jerarquía aritmética al permitir la cuantificación sobre conjuntos de números naturales además de la cuantificación sobre números individuales. Estas áreas están vinculadas a las teorías de los buenos ordenamientos y los árboles; por ejemplo, el conjunto de todos los índices de árboles computables (no binarios) sin ramas infinitas está completo para el nivel de la jerarquía analítica. Tanto la reducibilidad de Turing como la reducibilidad hiperaritmética son importantes en el campo de la teoría de conjuntos descriptiva efectiva . La noción aún más general de grados de constructibilidad se estudia en la teoría de conjuntos .$Estilo de visualización: Pi _{1}^{1}}$

La teoría de computabilidad para la computación digital está bien desarrollada. La teoría de computabilidad está menos desarrollada para la computación analógica que ocurre en computadoras analógicas , procesamiento de señales analógicas , electrónica analógica , redes neuronales artificiales y teoría de control de tiempo continuo , modelada por ecuaciones diferenciales y sistemas dinámicos continuos . ^{[22] [23]} Por ejemplo, los modelos de computación como el modelo de máquina Blum-Shub-Smale han formalizado la computación en los números reales.

Existen relaciones estrechas entre el grado de Turing de un conjunto de números naturales y la dificultad (en términos de la jerarquía aritmética ) de definir ese conjunto utilizando una fórmula de primer orden . Una de esas relaciones se precisa mediante el teorema de Post . Una relación más débil fue demostrada por Kurt Gödel en las pruebas de su teorema de completitud y teoremas de incompletitud . Las pruebas de Gödel muestran que el conjunto de consecuencias lógicas de una teoría de primer orden efectiva es un conjunto computablemente enumerable , y que si la teoría es lo suficientemente fuerte este conjunto será incomputable. De manera similar, el teorema de indefinibilidad de Tarski puede interpretarse tanto en términos de definibilidad como en términos de computabilidad.

La teoría de la computabilidad también está vinculada a la aritmética de segundo orden , una teoría formal de los números naturales y de los conjuntos de números naturales. El hecho de que ciertos conjuntos sean computables o relativamente computables a menudo implica que estos conjuntos pueden definirse en subsistemas débiles de la aritmética de segundo orden. El programa de matemáticas inversas utiliza estos subsistemas para medir la no computabilidad inherente a teoremas matemáticos bien conocidos. En 1999, Simpson ^[17] analizó muchos aspectos de la aritmética de segundo orden y de las matemáticas inversas.

El campo de la teoría de la prueba incluye el estudio de la aritmética de segundo orden y la aritmética de Peano , así como las teorías formales de los números naturales más débiles que la aritmética de Peano. Un método para clasificar la fuerza de estos sistemas débiles es caracterizar qué funciones computables puede demostrar el sistema como totales . ^[24] Por ejemplo, en la aritmética recursiva primitiva cualquier función computable que sea demostrablemente total es en realidad recursiva primitiva , mientras que la aritmética de Peano demuestra que funciones como la función de Ackermann , que no son recursivas primitivas, son totales. Sin embargo, no todas las funciones computables totales son demostrablemente totales en la aritmética de Peano; un ejemplo de tal función lo proporciona el teorema de Goodstein .

El campo de la lógica matemática que trata de la computabilidad y sus generalizaciones ha sido llamado "teoría de la recursión" desde sus inicios. Robert I. Soare , un destacado investigador en el campo, ha propuesto ^[12] que el campo debería llamarse en su lugar "teoría de la computabilidad". Soare sostiene que la terminología de Turing que utiliza la palabra "computable" es más natural y más ampliamente entendida que la terminología que utiliza la palabra "recursivo" introducida por Kleene. Muchos investigadores contemporáneos han comenzado a utilizar esta terminología alternativa. ^[e] Estos investigadores también utilizan terminología como función computable parcial y conjunto computablemente enumerable ( ce ) en lugar de función recursiva parcial y conjunto recursivamente enumerable ( re ) . Sin embargo, no todos los investigadores han quedado convencidos, como lo explican Fortnow ^[25] y Simpson. ^[26] Algunos comentaristas sostienen que tanto los nombres teoría de la recursión como teoría de la computabilidad no transmiten el hecho de que la mayoría de los objetos estudiados en la teoría de la computabilidad no son computables. ^[27]

En 1967, Rogers ^[28] sugirió que una propiedad clave de la teoría de la computabilidad es que sus resultados y estructuras deberían ser invariantes bajo biyecciones computables sobre los números naturales (esta sugerencia se basa en las ideas del programa de Erlangen en geometría). La idea es que una biyección computable simplemente renombra los números en un conjunto, en lugar de indicar alguna estructura en el conjunto, de manera similar a como una rotación del plano euclidiano no cambia ningún aspecto geométrico de las líneas dibujadas en él. Dado que dos conjuntos computables infinitos cualesquiera están vinculados por una biyección computable, esta propuesta identifica todos los conjuntos computables infinitos (los conjuntos computables finitos se consideran triviales). Según Rogers, los conjuntos de interés en la teoría de la computabilidad son los conjuntos no computables, divididos en clases de equivalencia por biyecciones computables de los números naturales.

La principal organización profesional dedicada a la teoría de la computabilidad es la Association for Symbolic Logic , que celebra varios congresos de investigación cada año. La asociación de investigación interdisciplinaria Computability in Europe ( CiE ) también organiza una serie de congresos anuales.

• Recursión (informática)
• Lógica de computabilidad
• Problema transcomputacional

Textos de nivel de pregrado

• Cooper, S. Barry (2004). Teoría de la computabilidad . Chapman & Hall /CRC. ISBN 1-58488-237-9.
• Matiyasevich, Yuri Vladimirovich (1993). El décimo problema de Hilbert . Prensa del MIT . ISBN 0-262-13295-8.

Textos avanzados

• Jain, Sanjay; Osherson, Daniel Nathan ; Royer, James S.; Sharma, Arun (1999). Sistemas que aprenden: una introducción a la teoría del aprendizaje (2.ª ed.). Bradford Book / MIT Press . ISBN 0-262-10077-0. Número de serie LCCN  98-34861.
• Lerman, Manuel (1983). Grados de insolubilidad . Perspectivas en lógica matemática. Springer-Verlag . ISBN. 3-540-12155-2.
• Nies, André (2009). Computabilidad y aleatoriedad . Oxford University Press . ISBN. 978-0-19-923076-1.
• Odifreddi, Piergiorgio (1989). Teoría de la recursión clásica . Holanda del Norte . ISBN 0-444-87295-7.
• Odifreddi, Piergiorgio (1999). Teoría clásica de la recursividad . vol. II. Elsevier . ISBN 0-444-50205-X.

Documentos y colecciones de encuestas

• Enderton, Herbert Bruce (1977). "Elementos de la teoría de la recursión". En Barwise, Jon (ed.). Handbook of Mathematical Logic . Holanda Septentrional . págs. 527–566. ISBN 0-7204-2285-X.

Artículos de investigación y colecciones

• Burgin, Mark; Klinger, Allen (2004). "Experiencia, generaciones y límites en el aprendizaje automático". Ciencias de la computación teórica . 317 (1–3): 71–91. doi :10.1016/j.tcs.2003.12.005.
• Friedberg, Richard M. (1958). "Tres teoremas sobre enumeración recursiva: I. Descomposición, II. Conjunto Maximal, III. Enumeración sin repetición". Revista de lógica simbólica . 23 (3): 309–316. doi :10.2307/2964290. JSTOR  2964290. S2CID  25834814.
• Gold, E. Mark (1967). "Identificación del lenguaje en el límite" (PDF) . Información y control . 10 (5): 447–474. doi : 10.1016/s0019-9958(67)91165-5 .[1]
• Jockusch, Carl Groos Jr. (1968). "Conjuntos semirecursivos y reducibilidad positiva". Transactions of the American Mathematical Society . 137 (2): 420–436. doi : 10.1090/S0002-9947-1968-0220595-7 . JSTOR  1994957.
• Kleene, Stephen Cole ; Post, Emil Leon (1954). "El semirretículo superior de grados de irresolubilidad recursiva". Anales de Matemáticas . Serie 2. 59 (3): 379–407. doi :10.2307/1969708. JSTOR  1969708.
• Myhill, John R. Sr. (1956). "La red de conjuntos recursivamente enumerables". Revista de lógica simbólica . 21 : 215–220. doi :10.1017/S002248120008525X. S2CID  123260425.
• Post, Emil Leon (1947). "Insolubilidad recursiva de un problema de Thue". Revista de lógica simbólica . 12 (1): 1–11. doi :10.2307/2267170. JSTOR  2267170. S2CID  30320278.Reimpreso en Davis 1965.

Wikimedia Commons tiene medios relacionados con Teoría de la computabilidad .

• Página de inicio de la Asociación para la Lógica Simbólica
• Página de inicio de Computabilidad en Europa Archivado el 17 de febrero de 2011 en Wayback Machine.
• Página web sobre el curso de teoría de la recursión a nivel de posgrado con aproximadamente 100 páginas de notas de clase
• Apuntes de la clase de lengua alemana sobre inferencia inductiva