Teoría de la computabilidad

Comenzando con la teoría de conjuntos recursivos y funciones descritas anteriormente, el campo de la teoría de la recursividad ha crecido para incluir el estudio de muchos temas estrechamente relacionados. Estas no son á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 recursión están familiarizados con la mayoría de ellas.

Computabilidad relativa y los grados de Turingeditar

La teoría de recursión en lógica matemática se ha centrado tradicionalmente en la computabilidad relativa, una generalización de la computabilidad de Turing definida utilizando máquinas de Turing oracle, introducida por Turing (1939). Una máquina de Turing de oráculo es un dispositivo hipotético que, además de realizar las acciones de una máquina de Turing regular, es capaz de hacer preguntas a un oráculo, que es un conjunto particular de números naturales. La máquina oracle solo puede hacer preguntas de la forma ” Is n in the oracle set?”. Cada pregunta se responderá de inmediato correctamente, incluso si el conjunto de oracle no es computable. Por lo tanto, una máquina oracle con un oracle no computable será capaz de calcular conjuntos que una máquina de Turing sin un oracle no puede.

Informalmente, un conjunto de números naturales A es Turing reducible a un conjunto B si hay una máquina oráculo que indica correctamente si los números están en A cuando se ejecuta con B como el conjunto oráculo (en este caso, el conjunto A también se dice que 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, se dice que los conjuntos tienen el mismo grado de Turing (también llamado grado de irresoluble). El grado de Turing de un conjunto da una medida precisa de cuán intransigible 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 recursivamente enumerables, y
2. Cada uno se puede traducir a cualquier otro a través de una reducción múltiple. Es decir, dados tales conjuntos A y B, hay una función computable total f tal que A = {x: f (x) ∈ B}. Se dice que estos conjuntos son equivalentes a muchos y uno (o m-equivalente).

Las reducciones de muchos-uno son “más fuertes” que las reducciones de Turing: si un conjunto A es muchos-uno reducible a un conjunto B, entonces A es Turing reducible a B, pero lo contrario no siempre se mantiene. Aunque los ejemplos naturales de conjuntos no computables son todos equivalentes a muchos uno, es posible construir conjuntos recursivamente enumerables A y B de manera que A sea reducible a B en Turing, pero no a muchos uno reducibles a B. Se puede demostrar que cada conjunto enumerable recursivamente es reducible al problema de detención, y por lo tanto el problema de detención es el conjunto enumerable recursivamente más complicado con respecto a la reducibilidad de muchos y uno y con respecto a la reducibilidad de Turing. Post (1944) preguntó si cada conjunto enumerable recursivamente es computable o Turing equivalente al problema de detención, es decir, si no hay un conjunto enumerable recursivamente con un grado de Turing intermedio entre esos dos.

Como resultados intermedios, tipos naturales post definidos de conjuntos recursivamente enumerables como los conjuntos simple, hipersimple e hiperhipersimple. Post demostró que estos conjuntos están estrictamente entre los conjuntos computables y el problema de detención con respecto a la reducibilidad de muchos y uno. Post también mostró 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 recursivamente 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 hay grados de Turing intermedios entre los de los conjuntos computables y el problema de detención, pero no pudieron demostrar que ninguno de estos grados contiene un conjunto recursivamente enumerable. Muy poco después de esto, Friedberg y Muchnik resolvieron de forma independiente el problema de Post estableciendo la existencia de conjuntos recursivamente enumerables de grado intermedio. Este resultado innovador abrió un amplio estudio de los grados de Turing de los conjuntos recursivamente enumerables que resultaron poseer una estructura muy complicada y no trivial.

Hay incontables conjuntos que no son recursivamente enumerables, y la investigación de los grados de Turing de todos los conjuntos es tan central en la teoría de la recursión como la investigación de los grados de Turing recursivamente enumerables. Se construyeron muchos grados con propiedades especiales: grados libres de hiperinmunes donde cada función computable en relación con ese grado está majorizada 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 todos los 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 los conjuntos recursivos de límite.

El estudio de los grados de Turing arbitrarios (no necesariamente enumerables recursivamente) 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 parada para máquinas de Turing oracle que se ejecutan con oracle A. El salto de Turing de cualquier conjunto es siempre de mayor grado de Turing que el conjunto original, y un teorema de Friedburg muestra que cualquier conjunto que calcula el problema de parada se puede obtener 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.

Muchas investigaciones recientes sobre los grados de Turing se han centrado en la estructura general del conjunto de grados de Turing y el conjunto de grados de Turing que contienen conjuntos recursivamente enumerables. Un teorema profundo de Shore y Slaman (1999) establece que la función que mapea un grado x al grado de su salto de Turing es definible en el orden parcial de los grados de Turing. Una encuesta reciente de Ambos-Spies y Fejer (2006) da una visión general de esta investigación y su progresión histórica.

Otras reduccioneseditar

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

Las fuertes reducciones incluyen:

Reducibilidad uno-uno A es reducible uno-uno (o 1-reducible) a B si hay 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-uno Esto es esencialmente reducibilidad uno-uno sin la restricción de que f sea inyectiva. A es reducible (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. Tabla de verdad reducibilidad A es tabla de verdad reducible a B si A es de Turing reducible a B a través de una máquina de Turing de oráculo que calcula una función total independientemente del oráculo que se le da. Debido a la compacidad del espacio de Cantor, esto es equivalente a decir que la reducción presenta una sola lista de preguntas (dependiendo solo de la entrada) al oráculo simultáneamente, y luego, después de ver sus respuestas, puede 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 la tabla de verdad.

Otras reducciones (positivas, disyuntivas, conjuntivas, lineales y sus versiones débiles y acotadas) se discuten en el artículo Reducción (teoría de recursión).

La principal investigación sobre fuertes reduccionidades ha sido comparar sus teorías, tanto para la clase de todos los conjuntos recursivamente enumerables como para la clase de todos los subconjuntos de los números naturales. Además, se han estudiado las relaciones entre las reducciones. 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 las reducibilidades más débiles que la reducibilidad de Turing (es decir, las reducibilidades implícitas en la reducibilidad de Turing). Las más conocidas son la reducibilidad aritmética y la reducibilidad hiperaritmética. Estas reducciones están estrechamente relacionadas con la definibilidad sobre el modelo estándar de aritmética.

El teorema de Rice y la jerarquía aritméticaeditar

Rice mostró que para cada clase no trivial C (que contiene algunos pero no todos los conjuntos de e.r.) el conjunto de índices E = {e: el eth r.e. set We is in C} tiene la propiedad de que el problema de detención o su complemento es reducible a E, es decir, se puede mapear usando una reducción a E (ver el teorema de Rice para más detalles). Sin embargo, muchos de estos conjuntos de índices son aún más complicados que el problema de la detención. Este tipo de conjuntos se pueden clasificar utilizando la jerarquía aritmética. Por ejemplo, el conjunto de índices FIN de clase de todos los conjuntos finitos está en el nivel Σ2, el conjunto de índices REC de la clase de todos los conjuntos recursivos está en el nivel Σ3, el conjunto de índices COFIN de todos los conjuntos cofinitos también está en el nivel Σ3 y el conjunto de índices COMP de la clase de todos los conjuntos Turing completos Σ4. Estos niveles de jerarquía se definen inductivamente, Σn + 1 contiene solo todos los conjuntos que son recursivamente enumerables en relación con Σn; Σ1 contiene los conjuntos recursivamente enumerables. Los conjuntos de índices que se dan aquí incluso están completos para sus niveles, es decir, todos los conjuntos de estos niveles pueden ser muchos, uno reducido a los conjuntos de índices dados.

Matemáticas Inverseditar

El programa de matemáticas inversas pregunta qué axiomas de existencia de conjuntos son necesarios para probar 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; Simpson (1999) da una discusión detallada del programa. Los axiomas de existencia de conjuntos en cuestión corresponden informalmente a axiomas que dicen que el conjunto de potencias de los números naturales está cerrado bajo varias nociones de reducibilidad. El axioma más débil estudiado en matemáticas inversas es la comprensión recursiva, que establece que el conjunto de poderes de los naturales está cerrado bajo la reducibilidad de Turing.

NumberingsEdit

Una numeración es una enumeración de funciones; tiene dos parámetros, e y x y muestra el valor de la e-ésima función en la numeración de la entrada x. Las numeraciones pueden ser recursivas parciales, aunque algunos de sus miembros son recursivos totales, es decir, funciones computables. Los numeraciones admisibles son aquellos a los que se pueden traducir todos los demás. Una numeración Friedberg (llamada así por su descubridor) es una numeración uno-uno de todas las funciones recursivas parciales; no es necesariamente una numeración admisible. Investigaciones posteriores trataron también de numeraciones de otras clases, como clases de conjuntos recursivamente enumerables. Goncharov descubrió, por ejemplo, una clase de conjuntos recursivamente enumerables para los cuales los números caen en exactamente dos clases con respecto a isomorfismos recursivos.

El método de prioridadeditar

Para obtener más información, consulte la sección El problema de la publicación y el método de prioridad en el artículo Grado de Turing.

El problema de Post se resolvió con un método llamado método de prioridad; una prueba que usa este método se llama argumento de prioridad. Este método se utiliza principalmente para construir conjuntos enumerables recursivamente con propiedades particulares. Para usar 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. Cada requisito se asigna a un número natural que representa la prioridad del requisito; por lo tanto, 0 se asigna a la prioridad más importante, 1 a la segunda más importante, y así sucesivamente. El conjunto se construye entonces en etapas, cada etapa intenta satisfacer uno de más de los requisitos, ya sea agregando números al conjunto o prohibiendo números del conjunto para que el conjunto final satisfaga el requisito. Puede suceder que el cumplimiento de 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 recursión, y se han clasificado en una jerarquía basada en su complejidad (Soare 1987). Debido a que los argumentos de prioridad complejos pueden ser técnicos y difíciles de seguir, tradicionalmente se ha considerado conveniente probar resultados sin argumentos de prioridad, o ver si los resultados probados con argumentos de prioridad también se pueden probar sin ellos. Por ejemplo, Kummer publicó un artículo sobre una prueba de la existencia de numeraciones de Friedberg sin usar el método de prioridad.

La red de conjuntos recursivamente enumerableseditar

Cuando Post definió la noción de un conjunto simple como un conjunto de e.r.con un complemento infinito que no contiene ninguna e. r. infinita. conjunto, comenzó a estudiar la estructura de los conjuntos recursivamente enumerables bajo inclusión. Esta celosía se convirtió en una estructura bien estudiada. Los conjuntos recursivos se pueden definir en esta estructura por el resultado básico de que un conjunto es recursivo si y solo si el conjunto y su complemento son ambos recursivamente enumerables. Los conjuntos r.e. infinitos siempre tienen subconjuntos recursivos infinitos; pero por otro lado, existen conjuntos simples pero no tienen un superconjunto recursivo coinfinito. Post (1944) introdujo conjuntos ya hipersimples e hiperhipersimples; más tarde se construyeron conjuntos máximos que son conjuntos r.e. tales que cada r.e. el superconjunto es una variante finita del conjunto máximo dado o es co-finito. La motivación original de Post en el estudio de esta red era encontrar una noción estructural de tal manera que cada conjunto que satisface esta propiedad no esté en el grado de Turing de los conjuntos recursivos 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 su lugar; Harrington y Soare (1991) encontraron finalmente tal propiedad.

Problemas de automorfismoeditar

Otra cuestión importante es la existencia de automorfismos en estructuras teóricas de recursión. Una de estas estructuras es la de conjuntos recursivamente enumerables bajo la diferencia finita del módulo de inclusión; en esta estructura, A está por debajo de B si y solo si la diferencia del conjunto B − A es finita. Los conjuntos máximos (definidos en el párrafo anterior) tienen la propiedad de que no pueden ser automórficos a conjuntos no máximos, es decir, si hay un automorfismo de los conjuntos enumerables recursivos bajo la estructura mencionada, entonces cada conjunto máximo se asigna a otro conjunto máximo. Soare (1974) demostró que también los valores inversos, es decir, cada dos conjuntos máximos son automórficos. Así que los conjuntos máximos forman una órbita, es decir, cada automorfismo conserva la maximalidad y dos conjuntos máximos cualesquiera 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 recursivamente enumerables, los automorfismos también se estudian para la estructura de los grados de Turing de todos los conjuntos, así como para la estructura de los grados de Turing de conjuntos de e.r. En ambos casos, Cooper afirma haber construido automorfismos no triviales que mapean algunos grados a otros grados; esta construcción, sin embargo, no ha sido verificada y algunos colegas creen que la construcción contiene errores y que la cuestión de si hay un automorfismo no trivial de los grados de Turing sigue siendo una de las principales preguntas sin resolver en esta área (Slaman y Woodin 1986, Ambos-Spies y Fejer 2006).

Kolmogorov Complexiteditar

El campo de complejidad de Kolmogorov y 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 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) produzca x. Este enfoque revolucionó formas anteriores de determinar cuándo una secuencia infinita (de forma equivalente, función característica de un subconjunto de números naturales) es aleatoria o no invocando una noción de aleatoriedad para objetos finitos. La complejidad de Kolmogorov no solo se convirtió 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 este ámbito. Por esa razón, en enero de 2007 se celebró una reciente conferencia de investigación en esta área y Joseph Miller y Andre Nies mantienen una lista de problemas abiertos.

Cálculo de frecuenciaeditar

Esta rama de la teoría de la recursión analizó la siguiente pregunta: Para m y n fijos con 0 < m < n, para las cuales funciones A es posible calcular para cualquier entrada n diferente x1, x2,…, xn una tupla de n números y1, y2,…, yn tal que al menos m de las ecuaciones A(xk) = yk son verdaderas. Estos conjuntos se conocen como conjuntos recursivos (m, n). El primer resultado importante en esta rama de la Teoría de la Recursión es el resultado de Trakhtenbrot de que un conjunto es computable si es (m, n)-recursivo para algunos m, n con 2m > n. Por otro lado, los conjuntos semirecursivos 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 solo si 2m < n + 1. Hay incontables muchos de estos conjuntos y también algunos conjuntos recursivamente enumerables pero no computables de este tipo. Más tarde, Degtev estableció una jerarquía de conjuntos recursivamente enumerables que son (1, n + 1) recursivos pero no (1, n) recursivos. Después de una larga fase de investigación por científicos rusos, este tema se repopularizó en Occidente por la tesis de Beigel sobre consultas limitadas, que vinculaba el cálculo de frecuencias a las reducciones limitadas 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 solo si hay 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 elecciones deben contener la verdadera cardinalidad, pero dejar de lado al menos una falsa.

Inferencia inductivaeditar

Esta es la rama recursiva-teórica de la teoría del aprendizaje. Se basa en el modelo de aprendizaje en el límite de E. Mark Gold de 1967 y ha desarrollado desde entonces más y más modelos de aprendizaje. El escenario general es el siguiente: Dada una clase S de funciones computables, hay un aprendiz (es decir, funcional recursiva) que produce cualquier entrada de la forma(f(0),f (1),…, f(n)) una hipótesis. Un alumno 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 recursivamente 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 recursivamente enumerables a partir de datos positivos es un tema estudiado a partir del artículo pionero de Gold en 1967 en adelante.

Generalizaciones de la computación de Turingeditar

La teoría de la recursión 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 α, tal como la describe Sacks (1990). Estas nociones generalizadas incluyen reduccionidades que no pueden ser ejecutadas por máquinas de Turing, pero 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 orden de pozos y árboles; por ejemplo, el conjunto de todos los índices de árboles recursivos (no binarios) sin ramas infinitas está completo para el nivel Π 1 1 {\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.

Teoría de la computabilidad continuaeditar

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 y teoría de control de tiempo continuo, modelada por ecuaciones diferenciales y sistemas dinámicos continuos (Orponen 1997; Moore 1996).