teoría de la computabilidad

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 máquinas de Turing oráculo , introducida por Turing en 1939. ^{[ 14 ]} 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 convencional, puede formular preguntas a un oráculo , que es un conjunto particular de números naturales. La máquina oráculo solo puede formular preguntas del tipo "¿Está n en el conjunto oráculo?". Cada pregunta se responderá inmediatamente de forma correcta, incluso si el conjunto 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 oráculo no puede.

De manera informal, un conjunto de números naturales A es Turing reducible a un conjunto B si existe una máquina oráculo que determina correctamente si los números pertenecen a A al utilizar B como 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 Turing reducible a un conjunto B y B es Turing reducible a A, entonces se dice que ambos conjuntos tienen el mismo grado de Turing (también llamado grado de insolubilidad ). El grado de Turing de un conjunto proporciona una medida precisa de cuán incomputable es dicho conjunto.

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

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

La reducibilidad muchos a uno es "más fuerte" que la reducibilidad de Turing: si un conjunto A es reducible muchos a uno a un conjunto B , entonces A es reducible de Turing a B , pero lo contrario no siempre se cumple. Aunque los ejemplos naturales de conjuntos no computables son todos equivalentes muchos a uno, es posible construir conjuntos computablemente enumerables A y B tales que A sea reducible de Turing a B pero no muchos a uno a B. Se puede demostrar que todo conjunto computablemente enumerable es muchos a uno reducible al problema de la parada, y por lo tanto el problema de la parada es el conjunto computablemente enumerable más complicado con respecto a la reducibilidad muchos a uno y con respecto a la reducibilidad de Turing. En 1944, Post ^{[ 15 ]} preguntó si todo conjunto computablemente enumerable es computable o equivalente de Turing al problema de la parada, 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 simple , hipersimple e hiperhipersimple. Post demostró que estos conjuntos se encuentran estrictamente entre los conjuntos computables y el problema de la parada con respecto a la reducibilidad 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. Sin embargo, 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 . Diez años después, en 1954, Kleene y Post demostraron que existen grados de Turing intermedios entre los de los conjuntos computables y el problema de la parada, pero no lograron demostrar que ninguno de estos grados contuviera un conjunto computablemente enumerable. Poco después, Friedberg y Muchnik resolvieron independientemente el problema de Post al establecer la existencia de conjuntos computablemente enumerables de grado intermedio. Este resultado revolucionario abrió un amplio estudio de los grados de Turing de los conjuntos computablemente enumerables, que resultaron poseer una estructura muy compleja y no trivial.

Hay una cantidad incontable de conjuntos que no son computacionalmente 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 computacionalmente enumerables. Se construyeron muchos grados con propiedades especiales: grados hiperinmunes libres donde cada función computable con respecto a ese grado es mayorizada por una función computable (no relativizada); grados altos con respecto a los cuales se puede calcular una función f que domina a 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 parada de conjuntos computables por límite .

El estudio de grados de Turing arbitrarios (no necesariamente enumerables computacionalmente) 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 codifica una solución al problema de la parada para máquinas de Turing oráculo que operan con el oráculo A. El salto de Turing de cualquier conjunto siempre tiene un grado de Turing mayor que el conjunto original, y un teorema de Friedburg muestra que cualquier conjunto que resuelva el problema de la parada puede obtenerse como el salto de Turing de otro conjunto. El teorema de Post establece una estrecha relación 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 fundamental de Shore y Slaman ^{[ 16 ]} 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 de Ambos-Spies y Fejer ^{[ 17 ]} 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 ^{[ 15 ]} introdujo varias reducibilidades fuertes , llamadas así porque implican reducibilidad de tabla de verdad . Una máquina de Turing que implementa 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 muchos a uno : Esto es esencialmente reducibilidad uno a uno sin la restricción de que f sea inyectiva. A es reducible muchos a uno (o m-reducible ) a B si hay 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 a B mediante una tabla de verdad si A es reducible a B mediante una máquina de Turing oráculo que calcula una función total independientemente del oráculo que se le proporcione. Debido a la compacidad del espacio de Cantor , esto equivale a decir que la reducción presenta una única lista de preguntas (que dependen únicamente de la entrada) al oráculo simultáneamente, y luego, tras ver 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 la reducibilidad de tabla de verdad.

En el artículo Reducción (teoría de la computabilidad) se analizan otras reducibilidades (positivas, disyuntivas, conjuntivas, lineales y sus versiones débiles y acotadas) .

La investigación principal sobre reducibilidades fuertes se ha centrado en comparar sus teorías, tanto para la clase de todos los conjuntos computacionalmente 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 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 implícitas en la reducibilidad de Turing). Las más conocidas son la reducibilidad aritmética y la 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 pero no todos los conjuntos ce) el conjunto de índices E = { e : el e th ce set W _e está en C } tiene la propiedad de que o bien el problema de parada o su complemento es reducible muchos a uno a E , es decir, puede ser mapeado usando una reducción muchos a uno a E (ver el teorema de Rice para más detalles). Pero, muchos de estos conjuntos de índices son incluso más complicados que el problema de parada. Este tipo de conjuntos pueden clasificarse usando la jerarquía aritmética . Por ejemplo, el conjunto de índices FIN de la clase de todos los conjuntos finitos está en el nivel Σ ₂ , el conjunto de índices REC de la clase de todos los conjuntos recursivos está en el nivel Σ ₃ , el conjunto de índices COFIN de todos los conjuntos cofinitos también está en el nivel Σ ₃ y el conjunto de índices COMP de la clase de todos los conjuntos Turing-completos Σ ₄ . Estos niveles jerárquicos se definen inductivamente: Σ _{n +1} contiene todos los conjuntos que son computacionalmente enumerables con respecto a Σ _n ; Σ ₁ contiene los conjuntos computacionalmente enumerables. Los conjuntos de índices que se presentan aquí son incluso completos para sus niveles; es decir, todos los conjuntos en estos niveles pueden reducirse mediante la regla de muchos a uno a los conjuntos de índices dados.

El programa de matemáticas inversas se pregunta qué axiomas de existencia de conjuntos son necesarios para demostrar teoremas particulares de matemáticas en subsistemas de aritmética de segundo orden . Este estudio fue iniciado por Harvey Friedman y estudiado en detalle por Stephen Simpson y otros; en 1999, Simpson ^{[ 18 ]} ofreció una discusión detallada del programa. Los axiomas de existencia de conjuntos en cuestión corresponden informalmente a axiomas que afirman que el conjunto potencia de los números naturales es cerrado bajo diversas 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 números 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 produce el valor de la e -ésima función de la numeración en la entrada x . Las numeraciones pueden ser parcialmente computables aunque algunos de sus miembros sean funciones totalmente computables. Las numeraciones admisibles son aquellas en las que se pueden traducir todas las demás. Una numeración de Friedberg (llamada así por su descubridor) es una numeración biyectiva de todas las funciones parcialmente computables; no es necesariamente una numeración admisible. Investigaciones posteriores también trataron numeraciones de otras clases, como clases de conjuntos computables enumerables. Goncharov descubrió, por ejemplo, una clase de conjuntos computables enumerables para los cuales las numeraciones caen en exactamente dos clases con respecto a isomorfismos computables .

El problema de Post se resolvió con un método llamado método de prioridad ; una demostración que utiliza este método se denomina argumento de prioridad . Este método se utiliza principalmente para construir conjuntos enumerables computacionalmente con propiedades particulares. Para utilizar este método, las propiedades deseadas del conjunto 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. A cada requisito se le asigna un número natural que representa su prioridad; así, 0 se asigna a la prioridad más importante, 1 a la segunda más importante, y así sucesivamente. El conjunto se construye entonces por etapas, intentando cada etapa satisfacer uno o más requisitos, ya sea añadiendo números al conjunto o excluyéndolos, de modo que el conjunto final satisfaga el requisito. Puede ocurrir 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 según su complejidad. ^{[ 12 ]} Dado que los argumentos de prioridad complejos pueden ser técnicos y difíciles de seguir, tradicionalmente se ha considerado deseable demostrar resultados sin ellos, o comprobar si los resultados demostrados con ellos también pueden demostrarse sin ellos. Por ejemplo, Kummer publicó un artículo sobre una demostración de la existencia de numeraciones de Friedberg sin utilizar el método de prioridad.

Cuando Post definió la noción de 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. Este retículo se convirtió en una estructura ampliamente estudiada. Los conjuntos computables pueden definirse en esta estructura mediante el resultado básico de que un conjunto es computable si y solo si tanto el conjunto como su complemento son computablemente enumerables. Los conjuntos ce infinitos siempre tienen subconjuntos computables infinitos; pero, por otro lado, los conjuntos simples existen, pero no siempre tienen un superconjunto computable coinfinito. Post ^{[ 15 ]} introdujo los conjuntos hipersimples e hiperhipersimples; posteriormente se construyeron los conjuntos maximales, que son conjuntos ce tales que cada superconjunto ce es una variante finita del conjunto maximal dado o es cofinito. La motivación original de Post en el estudio de este retículo fue encontrar una noción estructural tal que todo conjunto que satisfaga esta propiedad no esté ni en el grado de Turing de los conjuntos computables ni en el grado de Turing del problema de la parada. Post no encontró tal propiedad y la solución a su problema aplicó métodos de prioridad en su lugar; en 1991, Harrington y Soare ^{[ 19 ]} finalmente encontraron tal propiedad.

Otra cuestión importante es la existencia de automorfismos en estructuras teóricas de computabilidad. Una de estas estructuras es la de conjuntos computablemente enumerables bajo inclusión módulo diferencia finita; en esta estructura, A está por debajo de B si y solo si la diferencia de conjuntos B − A es finita. Los conjuntos maximales (como se definen en el párrafo anterior) tienen la propiedad de que no pueden ser automorfos a conjuntos no maximales; es decir, si existe un automorfismo de los conjuntos computablemente enumerables bajo la estructura recién mencionada, entonces todo conjunto maximal se mapea a otro conjunto maximal. En 1974, Soare ^{[ 20 ]} demostró que también se cumple lo contrario, es decir, que cualquier par de conjuntos maximales son automorfos. Así, los conjuntos maximales forman una órbita; es decir, todo automorfismo preserva la maximalidad y cualquier par de conjuntos maximales se transforman entre sí mediante algún automorfismo. Harrington dio otro ejemplo de una propiedad automórfica: la de los conjuntos creativos, los conjuntos que son muchos a uno equivalentes al problema de la parada.  

Además del retículo de conjuntos computablemente enumerables, también se estudian automorfismos para la estructura de los grados de Turing de todos los conjuntos, así como para la estructura de los grados de Turing de los conjuntos ce. En ambos casos, Cooper afirma haber construido automorfismos no triviales que mapean algunos grados a otros grados; sin embargo, esta construcción no ha sido verificada y algunos colegas creen que 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 este campo. ^{[ 21 ] [ 17 ]}

El campo de la complejidad de Kolmogorov y la aleatoriedad algorítmica fue desarrollado durante las décadas de 1960 y 1970 por Chaitin, Kolmogorov, Levin, Martin-Löf y Solomonoff (los nombres se presentan aquí en orden alfabético; gran parte de la investigación fue independiente y la unidad del concepto de aleatoriedad no se comprendía en ese momento). La idea principal consiste en 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 p más corta tal que U ( p ) produce x . Este enfoque revolucionó las formas anteriores de determinar si una secuencia infinita (o, equivalentemente, la función característica de un subconjunto de los números naturales) es aleatoria o no, al invocar una noción de aleatoriedad para objetos finitos. La complejidad de Kolmogorov no solo se convirtió en objeto de estudio independiente, sino que también se aplica a otros campos como herramienta para obtener demostraciones. Aún existen muchos problemas abiertos en esta área. ^{[ d ]}

Esta rama de la teoría de la computabilidad analizó la siguiente pregunta: 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 tal que al menos m de las ecuaciones A ( x _k ) = y _k sean verdaderas? Dichos 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 otro lado, los conjuntos semirrecursivos de Jockusch (que ya se conocían informalmente antes de que Jockusch los introdujera en 1968) son ejemplos de conjuntos que son ( m , n )-recursivos si y solo si 2m < n + 1. Hay una cantidad incontable de estos conjuntos y también algunos conjuntos de este tipo que son computablemente enumerables pero no computables. Posteriormente, Degtev estableció una jerarquía de conjuntos computablemente enumerables 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 popularizó nuevamente en Occidente gracias a la tesis de Beigel sobre consultas acotadas, que vinculó el cálculo de frecuencias con las reducibilidades acotadas mencionadas anteriormente y otras nociones relacionadas. Uno de los resultados principales fue el teorema de cardinalidad de Kummer ^{[ 22 ] [ 23 ]} , que establece que un conjunto A es computable si y solo si existe una máquina de Turing que, dadas n entradas x ₁ , x ₂ , ..., x _n , devuelve como máximo n salidas, una de las cuales es la cardinalidad de { x ₁ , x ₂ , ..., x _n }∩A (solo hay n + 1 valores posibles de la cardinalidad: 0, ..., n ).                                 ).

Esta es la rama de la teoría del aprendizaje basada en la computabilidad. Se fundamenta 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, un funcional computable) que produzca, 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 tienen el mismo índice e de f con respecto a una numeración aceptable previamente acordada para todas las funciones computables; M aprende S si M aprende cada f en S. Los resultados básicos indican que todas las clases de funciones computables enumerables son aprendibles, mientras que la clase REC de todas las funciones computables no lo es. Se han considerado muchos modelos relacionados, y el aprendizaje de clases de conjuntos computables enumerables a partir de datos positivos es un tema estudiado desde el artículo pionero de Gold en 1967.   

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 , descritas por Sacks en 1990. ^{[ 24 ]} 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 órdenes y los árboles; por ejemplo, el conjunto de todos los índices de árboles computables (no binarios) sin ramas infinitas es completo para el nivel${\displaystyle \Pi _{1}^{1}}$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 .

La teoría de la computabilidad para la computación digital está bien desarrollada. La teoría de la 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 . ^{[ 25 ] [ 26 ]} Por ejemplo, modelos de computación como el modelo de máquina de Blum-Shub-Smale han formalizado la computación en los reales.