Teoría de la computabilidad

Rama de lógica matemática, informática y teoría de la computación estudiando funciones computables y grados de Turing.

Para conocer el concepto de computabilidad, consulte Computabilidad .

La teoría de la computabilidad , también conocida como teoría de la recursividad , 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 recursividad se superpone con la teoría de la prueba y la teoría descriptiva de conjuntos efectiva .

Las preguntas básicas abordadas por la teoría de la recursividad incluyen:

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

Aunque existe una superposición considerable en términos de conocimiento y métodos, los teóricos de la recursividad matemática estudian la teoría de la computabilidad relativa, las nociones de reducibilidad y las estructuras de grado; los del campo de la informática se centran en la teoría de jerarquías subrecursivas , métodos formales y lenguajes formales .

Conjuntos computables y no computables

La teoría de la recursividad 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 . ^{[1] [2]}

Los resultados fundamentales que obtuvieron los investigadores establecieron la computabilidad de Turing como la formalización correcta de la idea informal de cálculo efectivo. Estos resultados llevaron a Stephen Kleene (1952) a acuñar los dos nombres "Tesis de Church" (Kleene 1952: 300) y "Tesis de Turing" (Kleene 1952: 376). Hoy en día, estos a menudo se consideran como una sola hipótesis, la tesis de Church-Turing , que establece que cualquier función que sea computable por un algoritmo es una función computable . Aunque inicialmente escéptico, en 1946 Gödel argumentó a favor de esta tesis:

"Tarski ha enfatizado 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 parte al hecho de que con este concepto uno tiene por primera vez el tiempo logró dar una noción absoluta a una noción epistemológica interesante, es decir, que no dependía del formalismo elegido. * ”(Gödel 1946 en Davis 1965: 84). ^[3]

Con una definición de cálculo efectiva llegaron las primeras pruebas de que hay problemas en matemáticas que no pueden ser efectivamente decidieron . Church (1936a, 1936b) y Turing (1936), inspirados en las técnicas utilizadas por Gödel (1931) para probar sus teoremas de incompletitud, demostraron de forma independiente que el problema de la Entscheidung no es efectivamente decidible. Este resultado mostró que no existe un procedimiento algorítmico que pueda decidir correctamente si las proposiciones matemáticas arbitrarias son verdaderas o falsas.

Se ha demostrado que muchos problemas matemáticos son indecidibles después de que se establecieron estos ejemplos iniciales. En 1947, Markov y Post publicaron artículos independientes que mostraban que el problema verbal de los semigrupos no se puede resolver de manera eficaz. La extensión de este resultado, Pyotr Novikov y William Boone mostraron de forma independiente en la década de 1950 que la palabra problema para los grupos no es efectivamente resolubles: no existe un procedimiento eficaz que, dada una palabra en un número finito presentado grupo , decidirá si el elemento representado por la palabra es el elemento de identidad del grupo. En 1970, Yuri Matiyasevich demostró (utilizando 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 preguntó si existe un procedimiento eficaz para decidir si una ecuación diofántica sobre los números enteros tiene una solución en los números enteros. La lista de problemas indecidibles ofrece ejemplos adicionales de problemas sin solución computable.

El estudio de qué construcciones matemáticas se pueden realizar de manera eficaz se denomina a veces matemática recursiva ; el Handbook of Recursive Mathematics (Ershov et al. 1998) cubre muchos de los resultados conocidos en este campo.

Computabilidad de Turing

La principal forma de computabilidad estudiada en la teoría de la recursividad fue introducida por Turing (1936). Se dice que un conjunto de números naturales es un conjunto computable (también llamado un conjunto computable decidible , recursivo o de Turing ) si hay una máquina de Turing que, dado un número n , se detiene con la 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 los números naturales a sí mismos es una función recursiva o computable (de Turing) si hay una máquina de Turing que, en la entrada n, 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 el mismo poder de computación que las máquinas de Turing; por ejemplo, las funciones recursivas μ obtenidas de la recursividad primitiva y el operador μ.

La terminología para funciones y conjuntos recursivos 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 llevó al nombre tradicional recursivo para conjuntos y funciones computables por una máquina de Turing. La palabra decidible proviene de la palabra alemana Entscheidungsproblemque 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 Cutland (1980), es una función recursiva parcial (que puede ser indefinida para algunas entradas), mientras que según Soare (1987) es una función recursiva total ( equivalentemente, función recursiva general). Este artículo sigue la segunda de estas convenciones. Soare (1996) ofrece 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 deriva del hecho de que solo hay un número numerable de máquinas de Turing y, por lo tanto, solo un número numerable de conjuntos computables, pero de acuerdo con el teorema de Cantor , hay incontables conjuntos de números naturales.

Aunque el problema de la detención no es computable, es posible simular la ejecución del programa y producir una lista infinita de los programas que se detienen. Así, el problema de la detención es un ejemplo de un conjunto recursivamente enumerable , que es un conjunto que puede ser enumerado por una máquina de Turing (otros términos para recursivamente enumerable incluyen computablemente enumerable y semidecidable ). De manera equivalente, un conjunto es recursivamente enumerable si y solo si es el rango de alguna función computable. Los conjuntos recursivamente enumerables, aunque no decidibles en general, se han estudiado en detalle en la teoría de la recursividad.

Áreas de investigación

A partir de la teoría de funciones y conjuntos recursivos descrita anteriormente, el campo de la teoría de la recursividad ha crecido hasta 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 recursividad están familiarizados con la mayoría de ellas.

Computabilidad relativa y grados de Turing

Artículos principales: reducción de Turing y grado de Turing

La teoría de la recursividad en la 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 de oráculo , 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 normal, es capaz de hacer preguntas a un oráculo , que es un conjunto particular de números naturales. La máquina de oráculo solo puede hacer preguntas del tipo "¿Hay n en el conjunto de oráculo?". Cada pregunta será inmediatamente respondida correctamente, incluso si el conjunto de oráculo no es computable. Por lo tanto, una máquina de 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 Turing reducible a un conjunto B si hay una máquina de oráculo que dice correctamente si los números están en A cuando se ejecuta con B como el conjunto de oráculo (en este caso, también se dice que el conjunto A es ( relativamente ) computable desde 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 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 incuestionable 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 puede traducirse en cualquier otro mediante una reducción de varios . Es decir, dados tales conjuntos A y B , existe una función calculable total f tal que A = { x  : f ( x ) ∈ B }. Se dice que estos conjuntos son varios equivalentes (o m-equivalentes ).

Las reducciones 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 cumple. Aunque los ejemplos naturales de conjuntos no computables son todos equivalentes de muchos-uno, es posible construir conjuntos A y B recursivamente enumerables de manera que A sea ​​Turing reducible a B pero no muchos-uno reducible a B. Puede demostrarse que todo conjunto recursivamente enumerable es muchos-uno reducible al problema de la detención, y por tanto el problema de la detención es el conjunto recursivamente enumerable más complicado con respecto a la reducibilidad muchos-uno y con respecto a la reducibilidad de Turing. Post (1944) preguntó si todo conjunto recursivamente enumerable es computable o Turing equivalente al problema de la detención, es decir, si no hay ningún conjunto recursivamente enumerable con un grado de Turing intermedio entre esos dos.

Como resultados intermedios, Post definió tipos naturales de conjuntos recursivamente enumerables como los conjuntos simple , hipersimple e hiperhipersimple. Post mostró que estos conjuntos están estrictamente entre los conjuntos computables y el problema de la detención con respecto a la reducibilidad muchos-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 intermedio de Turing; este problema se conoció como 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 alguno de estos grados contiene un conjunto recursivamente enumerable. Muy poco después de esto, Friedberg y Muchnik resolvieron independientemente el problema de Post al establecer la existencia de conjuntos recursivamente enumerables de grado intermedio. Este innovador resultado 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 recursividad como la investigación de los grados de Turing recursivamente enumerables. Se construyeron muchos grados con propiedades especiales: grados libres de hiperinmunidad donde cada función computable relativa 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 toda 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 ; 1-genéricos grados de conjuntos 1-genéricos; y los grados por debajo del problema de la detención de los conjuntos recursivos límite .

El estudio de grados de Turing arbitrarios (no necesariamente recursivamente 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 la parada de las máquinas de Turing de Oracle que se ejecutan con Oracle Una . 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 calcule el problema de detención 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 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 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 asigna 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) ofrece una descripción general de esta investigación y su progresión histórica.

Otras reducibilidades

Artículo principal: Reducción (teoría de la recursividad)

Un área de investigación en curso en la teoría de la recursividad estudia las relaciones de reducibilidad distintas de la reducibilidad de Turing. Post (1944) introdujo varias reducibilidades fuertes , llamadas así porque implican reducibilidad de la tabla de verdad. Una máquina de Turing que implemente una fuerte reducibilidad 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 fuertes reducibilidades incluyen:

Reducibilidad uno a uno

A es uno-uno reducible (o 1-reducible ) a B si hay un computable total de función inyectiva f tal que cada n está en A si y sólo si f ( n ) está en B .

Reducibilidad muchos-uno

Esto es esencialmente reductibilidad uno a uno sin la restricción de que f sea ​​inyectiva. A es mucho-uno reducible (o -m reducible ) a B si hay una función computable total de f tal que cada n está en A si y sólo si f ( n ) es en B .

Reducibilidad de la tabla de la verdad

A es la tabla de verdad reducible a B si A es 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 dé. Debido a la compacidad del espacio de Cantor , esto equivale a decir que la reducción presenta una única lista de preguntas (dependiendo solo de la entrada) al oráculo simultáneamente, y luego de haber 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 la tabla de verdad.

Las reducibilidades adicionales (positivas, disyuntivas, conjuntivas, lineales y sus versiones débiles y acotadas) se discuten en el artículo Reducción (teoría de la recursividad) .

La principal investigación sobre reducibilidades fuertes 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 reducibilidades. Por ejemplo, se sabe que cada grado de Turing es un grado de tabla de verdad o es la unión de un número infinito de 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). Los más conocidos 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 aritmética.

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

Rice mostró que por cada clase no trivial C (que contiene algunos pero no todos los juegos re) el conjunto de índices E = { e : el correo ª re establecido W _e está en C } tiene la propiedad de que, o bien el problema de la parada o su complemento es que muchos -uno reducible a E , es decir, se puede mapear usando una reducción muchos-uno a E (vea el teorema de Rice para más detalles). Pero muchos de estos conjuntos de índices son incluso 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 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 completos de Turing Σ ₄ . Estos niveles de jerarquía se definen inductivamente, Σ _{n +1} contiene solo todos los conjuntos que son recursivamente enumerables en relación con Σ _n ; Σ ₁ contiene los conjuntos enumerables de forma recursiva. Los conjuntos de índices dados aquí son incluso 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 inversas

Artículo principal: Matemáticas inversas

El programa de matemáticas inversas pregunta qué axiomas de existencia de conjuntos son necesarios para probar 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; Simpson (1999) ofrece 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.

Numeraciones

Una numeración es una enumeración de funciones; tiene dos parámetros, e y x, y genera el valor de la función e -ésima 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. Las numeraciones admisibles son aquellas a las que se pueden traducir todas las demás. Una numeración de Friedberg(llamado así por su descubridor) es una numeración uno-uno de todas las funciones recursivas parciales; no es necesariamente una numeración admisible. La investigación posterior se ocupó 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 que las numeraciones se dividen exactamente en dos clases con respecto a los isomorfismos recursivos.

El método de prioridad

Para una explicación más detallada, consulte la sección 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 utiliza este método se denomina argumento de prioridad . Este método se utiliza principalmente para construir conjuntos enumerables recursivamente 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 la satisfacción de todos los requisitos hará que el conjunto construido tenga las propiedades deseadas. A cada requisito se le asigna un número natural que representa la prioridad del requisito; por lo que se asigna 0 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 la satisfacción de un requisito haga que otro quede insatisfecho; el orden de prioridad se utiliza para decidir qué hacer en tal caso.

Se han empleado argumentos de prioridad para resolver muchos problemas en la teoría de la recursividad y se han clasificado en una jerarquía en función de 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 deseable probar los 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.

La celosía de conjuntos enumerables recursivamente

Cuando Post definió la noción de un conjunto simple como un re-conjunto con un complemento infinito que no contiene ningún re-conjunto infinito, 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 recursivamente enumerables. Los conjuntos de re 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 hipersimple e hiperhipersimple; posteriormente se construyeron conjuntos máximos que son reajustes tales que cada superconjunto restante es una variante finita del conjunto máximo dado o es co-finito. Correo'La motivación original en el estudio de esta red 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 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 prioritarios en su lugar; Harrington y Soare (1991) finalmente encontraron tal propiedad.

Problemas de automorfismo

Otra cuestión importante es la existencia de automorfismos en estructuras teóricas de recursividad. Una de estas estructuras es la de conjuntos recursivamente enumerables bajo inclusión en módulo de diferencia finita; en esta estructura, A está por debajo de B si y solo si la diferencia de conjuntos B  -  A es finita. Conjuntos máximos(como se define en el párrafo anterior) tienen la propiedad de que no pueden ser automórficos para conjuntos no máximos, es decir, si hay un automorfismo de los conjuntos enumerables recursivos bajo la estructura que se acaba de mencionar, entonces cada conjunto máximo se asigna a otro máximo. colocar. Soare (1974) mostró que también se cumple lo contrario, es decir, cada dos conjuntos máximos son automórficos. Entonces, los conjuntos máximos forman una órbita, es decir, cada automorfismo conserva la maximalidad y dos conjuntos máximos cualesquiera 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, 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 los conjuntos. 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 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 (Slaman y Woodin 1986, pág. Ambos-Spies y Fejer 2006).

Complejidad de Kolmogorov

Artículo principal: complejidad de Kolmogorov

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 dan aquí en orden alfabético; gran parte de la investigación fue independiente, y la unidad del concepto de la aleatoriedad no se entendió 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ó las formas anteriores de determinar cuándo una secuencia infinita (de manera equivalente, 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 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. Por esa razón, en enero de 2007 se celebró una conferencia de investigación reciente en esta área ^[4] y Joseph Miller y Andre Nies mantienen una lista de problemas abiertos ^[5] .

Cálculo de frecuencia

Esta rama de la teoría de la recursividad analizó la siguiente pregunta: Para m y n fijos con 0 <  m  <  n , para qué funciones A es posible calcular para 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 son verdaderas. Tales conjuntos se conocen como ( m,  n ) -conjuntos recursivos. El primer resultado importante en esta rama de la teoría de la recursividad es el resultado de Trakhtenbrot de que un conjunto es computable si es ( m ,  n ) -recursivo para algunos m ,  n con 2 m  >  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 2 m  <  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 parte de científicos rusos, este tema se volvió popular en Occidente por la tesis de Beigel sobre consultas limitadas, que vinculaban el cálculo de frecuencias con las reducibilidades limitadas mencionadas anteriormente y otras nociones relacionadas. Uno de los principales resultados fue la teoría de la cardinalidad de Kummer, que establece que un conjunto A es computable si y solo si hay una n tal que algún algoritmo enumere para cada tupla de n números diferentes hasta nmuchas elecciones posibles de la cardinalidad de este conjunto de n números cruzados con A ; estas opciones deben contener la cardinalidad verdadera pero omitir al menos una falsa.

Inferencia inductiva

Ésta es la rama de la teoría de la recursividad de la teoría del aprendizaje. Se basa en el modelo de aprendizaje en el límite de 1967 de E. Mark Gold y desde entonces ha desarrollado 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 recursivo) que emite para 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 tienen el mismo índice e de f con respecto a una numeración aceptable previamente acordada de todas las funciones computables; METROaprende S si M aprende cada f en S . Los resultados básicos son que todas las clases de funciones enumerables de forma recursiva se pueden aprender mientras que la clase REC de todas las funciones computables no se puede aprender. Se han considerado muchos modelos relacionados y también el aprendizaje de clases de conjuntos enumerables recursivamente a partir de datos positivos es un tema estudiado desde el artículo pionero de Gold en 1967 en adelante.

Generalizaciones de la computabilidad de Turing

La teoría de la recursividad incluye el estudio de nociones generalizadas de este campo como la reducibilidad aritmética , la reducibilidad hiperaritmética y la teoría de la recursividad α , tal como la describe Sacks (1990). Estas nociones generalizadas incluyen reducibilidades que no pueden ser ejecutadas por máquinas de Turing pero que, no obstante, 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 ordenamiento 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 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 descriptiva de conjuntos eficaz . La noción aún más general de grados de constructibilidad se estudia en la teoría de conjuntos .${\displaystyle \Pi _{1}^{1}}$

Teoría de la computabilidad continua

La teoría de la computabilidad para la computación digital está bien desarrollada. Teoría Computability está menos desarrollado para el cálculo análogo que se produce en ordenadores analógicos , procesamiento de señal analógica , electrónica analógica , redes neuronales y de tiempo continuo la teoría de control , modelado por ecuaciones diferenciales y continuos sistemas dinámicos (Orponen 1997; Moore, 1996).

Relaciones entre definibilidad, prueba y computabilidad

Existen estrechas relaciones 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 . Kurt Gödel demostró una relación más débil en las demostraciones de su teorema de completitud y teoremas de incompletitud . Las demostraciones de Gödel muestran que el conjunto de consecuencias lógicas de una teoría de primer orden eficaz es un conjunto recursivamente enumerable , y que si la teoría es lo suficientemente fuerte, este conjunto será incomputable. De manera similar, el teorema de indefinibilidad de Tarski se puede interpretar tanto en términos de definibilidad como en términos de computabilidad.

La teoría de la recursividad también está vinculada a la aritmética de segundo orden , una teoría formal de números naturales y 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 aritmética de segundo orden. El programa de matemáticas inversas utiliza estos subsistemas para medir la incomputabilidad inherente a teoremas matemáticos bien conocidos. Simpson (1999) analiza muchos aspectos de la aritmética de segundo orden y 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 fortaleza de estos sistemas débiles es caracterizar qué funciones computables puede resultar total del sistema (ver Fairtlough y Wainer (1998)). Por ejemplo, en aritmética recursiva primitiva, cualquier función computable que sea probadamente total es en realidad recursiva primitiva , mientras que la aritmética de Peano demuestra que funciona como la función de Ackermann., que no son recursivas primitivas, son totales. Sin embargo, no todas las funciones computables totales son probables en la aritmética de Peano; un ejemplo de tal función lo proporciona el teorema de Goodstein .

Nombre

El campo de la lógica matemática que se ocupa de la computabilidad y sus generalizaciones se ha denominado "teoría de la recursividad" desde sus inicios. Robert I. Soare , un destacado investigador en el campo, ha propuesto (Soare 1996) que el campo debería llamarse "teoría de la computabilidad". Sostiene que la terminología de Turing que usa la palabra "computable" es más natural y más ampliamente comprendida que la terminología que usa la palabra "recursiva" introducida por Kleene. Muchos investigadores contemporáneos han comenzado a utilizar esta terminología alternativa. ^[6] Estos investigadores también utilizan terminología como función computable parcial y computablemente enumerable ( ce ) establecer en lugar defunción recursiva parcial y recursivamente enumerable ( re ) set . Sin embargo, no todos los investigadores están convencidos, como explican Fortnow ^[7] y Simpson. ^[8] Algunos comentaristas sostienen que tanto los nombres teoría de la repetición y la teoría de la computabilidad dejan de transmitir el hecho de que la mayoría de los objetos estudiados en la teoría de la repetición no son computables. ^[9]

Rogers (1967) ha sugerido que una propiedad clave de la teoría de la recursividad es que sus resultados y estructuras deben ser invariantes bajo biyecciones computables sobre los números naturales (esta sugerencia se basa en las ideas del programa de Erlangenen geometría). La idea es que una biyección computable simplemente cambia el nombre de los números en un conjunto, en lugar de indicar cualquier estructura en el conjunto, al igual que una rotación del plano euclidiano no cambia ningún aspecto geométrico de las líneas dibujadas en él. Dado que cualesquiera dos conjuntos computables infinitos 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 recursividad son los conjuntos no computables, divididos en clases de equivalencia por biyecciones computables de los números naturales.

Organizaciones profesionales

La principal organización profesional de la teoría de la recursividad 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 conferencias anuales.

Ver también

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

Notas

1. Muchos de estos artículos fundamentales se recopilan en The Undecidable (1965) editado por Martin Davis .
2. Soare, Robert Irving (22 de diciembre de 2011). "Teoría y aplicaciones de la computabilidad: el arte de la computabilidad clásica" (PDF) . Departamento de Matemáticas . Universidad de Chicago . Consultado el 23 de agosto de 2017 .
3. El artículo completo también se puede encontrar en las páginas 150 y siguientes (con comentarios de Charles Parsons en 144 y siguientes) en Feferman et al. editores 1990 Kurt Gödel Volume II Publications 1938-1974 , Oxford University Press, Nueva York, ISBN 978-0-19-514721-6 . Ambas reimpresiones tienen la siguiente nota al pie * agregada al volumen de Davis por Gödel en 1965: "Para ser más precisos: una función de números enteros es computable en cualquier sistema formal que contenga aritmética si y solo si es computable en aritmética, donde una función f es llamado computable en S si hay en S un término computable que representa f (p. 150). 
4. Conferencia sobre lógica, computabilidad y aleatoriedad. Archivado el 26 de diciembre de 2007en la Wayback Machine , del 10 al 13 de enero de 2007.
5. La página de inicio de Andre Nies tiene una lista de problemas abiertos en la complejidad de Kolmogorov
6. búsquedas de Mathscinet para títulos como "computablemente enumerable" y "ce" muestran que muchos artículos se han publicado con esta terminología, así como con la otra.
7. Lance Fortnow, " ¿Es recursivo, computable o decidible? ", 2004-2-15, consultado el 2018-3-22.
8. Stephen G. Simpson , " ¿Qué es la teoría de la computabilidad? ", Lista de correo electrónico de FOM, 1998-8-24, consultado 2006-1-9.
9. Harvey Friedman, " Cambiar el nombre de la teoría de la recursividad ", lista de correo electrónico de FOM, 1998-8-28, consultado 2006-1-9.

Referencias

Textos de grado

• Cooper, SB (2004). Teoría de la computabilidad . Chapman y Hall / CRC. ISBN 1-58488-237-9.
• Cutland, N. (1980). Computabilidad, una introducción a la teoría de funciones recursivas . Prensa de la Universidad de Cambridge. ISBN 0-521-29465-7.
• Matiyasevich, Y. (1993). Décimo problema de Hilbert . MIT Press. ISBN 0-262-13295-8.

Textos avanzados

• Jain, S .; Osherson, D .; Royer, J .; Sharma, A. (1999). Sistemas que aprenden, introducción a la teoría del aprendizaje (2ª ed.). Libro de Bradford. ISBN 0-262-10077-0.
• Kleene, S. (1952). Introducción a las metamatemáticas . Holanda Septentrional. ISBN 0-7204-2103-9.
• Lerman, M. (1983). Grados de insolubilidad . Perspectivas en lógica matemática. Springer-Verlag. ISBN 3-540-12155-2.
• Nies, Andre (2009). Computabilidad y aleatoriedad . Prensa de la Universidad de Oxford. ISBN 978-0-19-923076-1.
• Odifreddi, P. (1989). Teoría clásica de la recursividad . Holanda Septentrional. ISBN 0-444-87295-7.
• Odifreddi, P. (1999). Teoría clásica de la recursividad . II . Elsevier. ISBN 0-444-50205-X.
• Rogers, Jr., H. (1987). La teoría de las funciones recursivas y la computabilidad efectiva (2ª ed.). MIT Press. ISBN 0-262-68052-1.
• Sacks, G. (1990). Teoría de la recursividad superior . Springer-Verlag. ISBN 3-540-19305-7.
• Simpson, SG (1999). Subsistemas de aritmética de segundo orden . Springer-Verlag. ISBN 3-540-64882-8.
• Soare, RI (1987). Conjuntos y grados recursivamente enumerables . Perspectivas en lógica matemática. Springer-Verlag. ISBN 0-387-15299-7.

Documentos y colecciones de encuestas

• Ambos-Spies, K .; Fejer, P. (2006). "Grados de insolubilidad" (PDF) . Archivado desde el original (PDF) el 20 de abril de 2013 . Consultado el 27 de octubre de 2006 . Preimpresión inédita.
• Enderton, H. (1977). "Elementos de la teoría de la recursividad". En Barwise, J. (ed.). Manual de lógica matemática . Holanda Septentrional. págs.  527–566 . ISBN 0-7204-2285-X.
• Ershov, YL; Goncharov, SS; Nerode, A .; Remmel, JB (1998). Manual de matemáticas recursivas . Holanda Septentrional. ISBN 0-7204-2285-X.
• Fairtlough, M .; Wainer, SS (1998). "Jerarquías de funciones recursivas demostrables" . En Buss, SR (ed.). Manual de teoría de la prueba . Elsevier. págs. 149-208. ISBN 978-0-08-053318-6.
• Soare, RI (1996). "Computabilidad y recursividad" (PDF) . Boletín de Lógica Simbólica . 2 (3): 284–321. doi : 10.2307 / 420992 . JSTOR  420992 .

Artículos de investigación y colecciones

• Burgin, M .; Klinger, A. (2004). "Experiencia, generaciones y límites en el aprendizaje automático" . Informática Teórica . 317 (1-3): 71-91. doi : 10.1016 / j.tcs.2003.12.005 .
• Iglesia, A. (1936). "Un problema irresoluble de la teoría de números elementales". Revista Estadounidense de Matemáticas . 58 (2): 345–363. doi : 10.2307 / 2371045 . JSTOR  2371045 .Reimpreso en Davis 1965 .
• Iglesia, A. (1936). "Una nota sobre el Entscheidungsproblem". Revista de lógica simbólica . 1 (1): 40–41. doi : 10.2307 / 2269326 . JSTOR  2269326 . Reimpreso en Davis 1965 .
• Davis, Martin, ed. (2004) [1965]. Lo indecidible: artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Mensajero. ISBN 978-0-486-43228-1.
• Friedberg, RM (1958). "Tres teoremas sobre enumeración recursiva: I. Descomposición, II. Conjunto máximo, III. Enumeración sin repetición". El diario de la lógica simbólica . 23 (3): 309–316. doi : 10.2307 / 2964290 . JSTOR  2964290 .
• Gold, E. Mark (1967). "Identificación de idioma en el límite" (PDF) . Información y control . 10 (5): 447–474. doi : 10.1016 / s0019-9958 (67) 91165-5 . [1]
• Harrington, L .; Soare, RI (1991). "Programa de Post y conjuntos enumerables recursivamente incompletos" . Proc. Natl. Acad. Sci. USA . 88 (22): 10242–6. Código Bibliográfico : 1991PNAS ... 8810242H . doi : 10.1073 / pnas.88.22.10242 . PMC  52904 . PMID  11607241 .
• Jockusch jr, CG (1968). "Conjuntos semirecursivos y reducibilidad positiva" . Trans. Amer. Matemáticas. Soc . 137 (2): 420–436. doi : 10.1090 / S0002-9947-1968-0220595-7 . JSTOR  1994957 .
• Kleene, SC; Publicación, EL (1954). "La semi-celosía superior de grados de insolubilidad recursiva". Annals of Mathematics . Segundo. 59 (3): 379–407. doi : 10.2307 / 1969708 . JSTOR  1969708 .
• Moore, C. (1996). "Teoría de la recursividad sobre los reales y computación en tiempo continuo". Informática Teórica . 162 (1): 23–44. CiteSeerX  10.1.1.6.5519 . doi : 10.1016 / 0304-3975 (95) 00248-0 .
• Myhill, J. (1956). "La celosía de conjuntos recursivamente enumerables". El diario de la lógica simbólica . 21 : 215–220. doi : 10.1017 / S002248120008525X .
• Orponen, P. (1997). "Un estudio de la teoría de la computación en tiempo continuo". Avances en algoritmos, lenguajes y complejidad : 209–224. CiteSeerX  10.1.1.53.1991 . doi : 10.1007 / 978-1-4613-3394-4_11 . ISBN 978-1-4613-3396-8.
• Publicar, E. (1944). "Conjuntos recursivamente enumerables de números enteros positivos y sus problemas de decisión" . Boletín de la American Mathematical Society . 50 (5): 284–316. doi : 10.1090 / S0002-9904-1944-08111-1 . Señor  0010514 .
• Publicar, E. (1947). "Insolubilidad recursiva de un problema de Thue". Revista de lógica simbólica . 12 (1): 1–11. doi : 10.2307 / 2267170 . JSTOR  2267170 .Reimpreso en Davis 1965 .
• Shore, Richard A .; Slaman, Theodore A. (1999). "Definición del salto de Turing" (PDF) . Cartas de investigación matemática . 6 (6): 711–722. doi : 10.4310 / mrl.1999.v6.n6.a10 . Señor  1739227 .
• Slaman, T .; Woodin, WH (1986). "Definibilidad en los grados de Turing" . Illinois J. Math . 30 (2): 320–334. doi : 10.1215 / ijm / 1256044641 . Señor  0840131 .
• Soare, RI (1974). "Automorfismos de la red de conjuntos recursivamente enumerables, Parte I: Conjuntos máximos". Annals of Mathematics . 100 (1): 80-120. doi : 10.2307 / 1970842 . JSTOR  1970842 .
• Turing, A. (1937). "Sobre números computables, con una aplicación al Entscheidungsproblem". Actas de la London Mathematical Society . t2-42 (1): 230-265. doi : 10.1112 / plms / s2-42.1.230 . Turing, AM (1938). "Sobre números computables, con una aplicación al Entscheidungsproblem. Una corrección". Actas de la London Mathematical Society . t2-43 (1): 544-6. doi : 10.1112 / plms / s2-43.6.544 .Reimpreso en Davis 1965 . PDF de comlab.ox.ac.uk
• Turing, AM (1939). "Sistemas de lógica basados ​​en ordinales". Actas de la London Mathematical Society . t2-45 (1): 161-228. doi : 10.1112 / plms / s2-45.1.161 . hdl : 21.11116 / 0000-0001-91CE-3 .Reimpreso en Davis 1965 .

Enlaces externos

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

• Página de inicio de la Asociación para la lógica simbólica
• Computabilidad en la página de inicio de Europa
• Página web sobre el curso de teoría de la recursividad a nivel de posgrado con aproximadamente 100 páginas de notas de clase
• Apuntes de clase en lengua alemana sobre inferencia inductiva