Teoría de la computabilidad

ImprimirCitar

Estudio de funciones computables y grados de Turing

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 funciones computables y 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 descriptiva efectiva.

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

¿Qué significa que una función en los números naturales sea computable?
¿Cómo pueden clasificarse las funciones no compatibles en una jerarquía basada en su nivel de no competencia?

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 grado; 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.

Introducción

n	2	3	4	5	6	7	...
.n)	4	6	13	4098 ?	■ 3.5×10¹⁸²⁶⁷	■ 10^{10^{10^{10^18705353}}}	?
No aparece Función Busy Beavern) crece más rápido que cualquier función computable. Por lo tanto, no es computable; sólo algunos valores son conocidos.

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.

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. En 1952, estos resultados llevaron a Kleene a acuñar los dos nombres "Tesis de la Iglesia" y la 'tesis de Turing'. Hoy en día, estos se consideran a menudo 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 subrayado en su conferencia (y creo justamente) 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 uno ha logrado por primera vez dar una noción absoluta a una noción epistemológica interesante, es decir, una no dependiendo del formalismo elegido".

Con una definición de cálculo efectivo surgieron las primeras pruebas de que hay problemas en matemáticas que no se pueden resolver de manera efectiva. En 1936, Church y Turing se inspiraron en las técnicas utilizadas por Gödel para probar sus teoremas de incompletitud; en 1931, Gödel demostró de forma independiente que el Entscheidungsproblem 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 efectiva. Ampliando este resultado, Pyotr Novikov y William Boone demostraron de forma independiente en la década de 1950 que el problema verbal para grupos no se puede resolver de manera efectiva: no existe un procedimiento efectivo que, dada una palabra en un grupo finito, decida 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 solución efectiva; este problema preguntaba 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 proporciona ejemplos adicionales de problemas sin solución computable.

El estudio de qué construcciones matemáticas se pueden realizar de manera efectiva a veces se denomina matemática recursiva; el Manual de matemáticas recursivas cubre muchos de los resultados conocidos en este campo.

Computabilidad de Turing

La principal forma de computabilidad estudiada en la teoría de la computabilidad fue introducida por Turing en 1936. Se dice que un conjunto de números naturales es un conjunto computable (también llamado decidible, recursivo, o turing computable conjunto) 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 la 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 (Turing) computable o recursiva 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 cómputo 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 computables no está completamente estandarizada. La definición en términos de funciones μ-recursivas, así como una definición diferente de las funciones rekursiv de Gödel llevó a la 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 usó 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, es una función recursiva parcial (que puede ser indefinida para algunas entradas), mientras que según Robert I. Soare es una función recursiva total (equivalentemente, recursiva general). Este artículo sigue la segunda de estas convenciones. En 1996, Soare hizo 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 muchas máquinas de Turing contables y, por lo tanto, solo muchos conjuntos computables contables, pero de acuerdo con el teorema de Cantor, hay muchos conjuntos incontables de números naturales.

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

Áreas de investigación

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

Computabilidad relativa y los grados de Turing

La teoría de la computabilidad en la 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 del oráculo, introducidas por Turing en 1939. Una máquina de Turing del oráculo es un dispositivo hipotético que, en 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 del oráculo solo puede hacer preguntas del tipo "¿Está n en el conjunto del oráculo?". Cada pregunta se responderá correctamente de inmediato, incluso si el conjunto del 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.

Informalmente, 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 ejecutan con B como el conjunto del 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 reducible por Turing a un conjunto B y B es reducible por Turing a A entonces los conjuntos son se dice que tiene el mismo grado de Turing (también llamado grado de irresolubilidad). 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:

Son computadamente enumerables, y
Cada uno puede ser traducido a cualquier otro a través de una reducción de muchos. Es decir, dados tales conjuntos A y B, hay una función computable total f tales que A =x: f()x) B}. Estos juegos se dice que muchos-uno equivalente (o m-equivalente).

Las reducciones de varios 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 no siempre ocurre lo contrario. Aunque los ejemplos naturales de conjuntos no computables son todos equivalentes de muchos uno, es posible construir conjuntos numerables computables A y B tales que A es Turing reducible a B pero no muchos-uno reducible a B. Se puede demostrar que todo conjunto enumerable computacionalmente es reducible por muchos-uno al problema de detención y, por lo tanto, el problema de detención es el conjunto enumerable computacionalmente más complicado con respecto a la reducibilidad de muchos-uno y con respecto a la reducibilidad de Turing. En 1944, Post preguntó si todos conjuntos enumerables computablemente son equivalentes de Turing o computables al problema de detención, es decir, si no hay ningún conjunto enumerable computable 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 mostró que estos conjuntos están estrictamente entre los conjuntos computables y el problema de detención con respecto a la reducibilidad de muchos a 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 computablemente enumerables de grado intermedio de Turing; este problema se conoció como problema de la publicación. 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 lograron demostrar que ninguno de estos grados contuviera un conjunto computable enumerable. Muy poco después de esto, Friedberg y Muchnik resolvieron de forma independiente el problema de Post al establecer la existencia de conjuntos enumerables computablemente de grado intermedio. Este innovador resultado abrió un amplio estudio de los grados de Turing de los conjuntos computablemente enumerables que resultó poseer una estructura muy complicada y no trivial.

Existen incontables 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 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 todas las funciones computables g en el sentido de que hay una constante c dependiendo de g tal que g(x) < f(x) para todo x > c; grados aleatorios que contienen conjuntos algorítmicamente aleatorios; 1-genérico grados de 1-conjuntos genéricos; y los grados por debajo del problema de detención de conjuntos computables límite.

El estudio de los grados de Turing arbitrarios (no necesariamente computables) 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 del oráculo que funcionan con oráculo 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 calcule el problema de Halting 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 en función de su definibilidad en la 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 computablemente enumerables. Un teorema profundo de Shore y Slaman 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 de Ambos-Spies y Fejer ofrece una visión general de esta investigación y su progresión histórica.

Otras reducibilidades

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 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 reductibilidades débiles son aquellas en las que un proceso de reducción no puede terminar para todos los oráculos; La reducibilidad de Turing es un ejemplo.

Las reductibilidades fuertes incluyen:

Reducibilidad uno-uno: A es uno-uno reducible (o 1-reducible) a B si hay una función de inyección computable f tal que cada uno n está dentro A si f()n) está en B.

Una reducibilidad: Esto es esencialmente una reducibilidad sin la restricción de que f ser inyectable. A es muchos-uno reducible (o m-reducible) a B si hay una función computable total f tal que cada uno n está dentro A si f()n) está en B.

Reducibilidad de tabla de verdad: A es la verdad-tabla reducible a B si A es Turing reducible a B a través de un oráculo Turing máquina que calcula una función total independientemente del oráculo que se da. Debido a la compactidad del espacio Cantor, esto equivale a decir que la reducción presenta una lista única de preguntas (dependiendo sólo de la entrada) al oráculo simultáneamente, y después de haber visto sus respuestas es capaz de producir una salida sin hacer preguntas adicionales sin importar la respuesta del oráculo a las consultas iniciales. También se han estudiado muchas variantes de reducibilidad de mesa de verdad.

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

La principal investigación sobre las reductibilidades 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 las reducibilidades más débiles que la reducibilidad de Turing (es decir, las reducibilidades implícitas en la reducibilidad de Turing). Los más conocidos son la reducibilidad aritmética y la reducibilidad hiperaritmética. Estas reductibilidades 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 para cada clase no trivial C (que contiene algunos conjuntos c.e. pero no todos) el conjunto índice E = {e: el ee d.C. el conjunto W_e está en C} tiene la propiedad de que el problema de detención o su complemento es reducible por muchos a E, es decir, se puede mapear utilizando una reducción de muchos a E (consulte el teorema de Rice para obtener 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 í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 completos de Turing Σ₄. Estos niveles de jerarquía se definen de forma 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 en muchos a uno a los conjuntos de índices dados.

Matemática inversa

El programa de matemáticas inversas pregunta qué axiomas de existencia de conjuntos son necesarios para probar teoremas matemáticos particulares 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 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 está cerrado bajo varias nociones de reducibilidad. El axioma más débil estudiado en matemáticas inversas es comprensión recursiva, que establece que el conjunto potencia de los naturales está cerrado bajo la reducibilidad de Turing.

Numeración

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

El método de prioridad

El problema de la publicación 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 computables enumerables con propiedades particulares. Para utilizar este método, las propiedades deseadas del conjunto a construir se descomponen en una lista infinita de objetivos, conocidos como requisitos, de modo que al satisfacer todos los requisitos, el conjunto construido tendrá las características deseadas. propiedades. A cada requerimiento se le asigna un número natural que representa la prioridad del requerimiento; 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 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 computabilidad y se han clasificado en una jerarquía basada en su complejidad. 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 usar el método de prioridad.

La red de conjuntos computablemente enumerables

Cuando Post definió la noción de un conjunto simple como un c.e. conjunto con un complemento infinito que no contiene ningún infinito c.e. conjunto, comenzó a estudiar la estructura de los conjuntos numerables computablemente bajo inclusión. Esta red se convirtió en una estructura bien estudiada. Los conjuntos computables se pueden definir en esta estructura por el resultado básico de que un conjunto es computable si y solo si el conjunto y su complemento son numerables computablemente. Infinito c.e. los conjuntos tienen siempre infinitos subconjuntos computables; pero por otro lado, existen conjuntos simples pero no siempre tienen un superconjunto computable coinfinito. Post introdujo conjuntos ya hipersimples e hiperhipersimples; más tarde se construyeron conjuntos máximos que son c.e. conjuntos tales que cada c.e. 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 fue encontrar una noción estructural tal que cada 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 detención. 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 finalmente encontraron una propiedad de este tipo.

Problemas de automorfismo

Otra pregunta 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 define en el párrafo anterior) tienen la propiedad de que no pueden ser automórficos a conjuntos no maximales, es decir, si hay un automorfismo de los conjuntos enumerables computablemente bajo la estructura que acabamos de mencionar, entonces cada conjunto maximal se asigna a otro conjunto máximo. En 1974, Soare demostró que también se cumple lo contrario, es decir, cada dos conjuntos máximos son automórficos. Entonces, los conjuntos maximales forman una órbita, es decir, cada automorfismo conserva la maximalidad y dos conjuntos maximales 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 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 c.e. conjuntos En ambos casos, Cooper afirma haber construido automorfismos no triviales que asignan algunos grados a otros grados; sin embargo, esta construcción no se ha verificado 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.

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 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) genera x. Este enfoque revolucionó las formas anteriores de determinar cuándo una secuencia infinita (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 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 realizó una reciente conferencia de investigación en esta área y Joseph Miller y André Nies mantienen una lista de problemas abiertos.

Cálculo de frecuencia

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 cualquier entrada diferente n 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 ciertas. Estos conjuntos se conocen como conjuntos recursivos (m, n). 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 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 enumerables pero no computables de este tipo. Más tarde, 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 volvió a popularizarse en Occidente gracias a la tesis de Beigel sobre consultas acotadas, que relacionaba el cálculo de frecuencias con las reductibilidades acotadas 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 un n tal que algún algoritmo enumera para cada tupla de n números diferentes hasta n muchas elecciones posibles de la cardinalidad de este conjunto de n números intersecados con A; estas opciones deben contener la verdadera cardinalidad pero dejar de lado al menos una falsa.

Inferencia inductiva

Esta es la rama teórica de la computabilidad de la teoría del aprendizaje. Se basa en el modelo de aprendizaje en el límite de E. Mark Gold de 1967 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 computable) cuya salida 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 previamente acordado sobre la numeración aceptable 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 enumerables computablemente 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 computablemente 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 computación incluye el estudio de las nociones generalizadas de este campo como la reducibilidad aritmética, la reducibilidad hiperaritmética y la teoría de la recursión α, como lo describe Sacks en 1990. Estas nociones generalizadas incluyen rociaciones que no pueden ser ejecutadas por las máquinas Turing, pero son sin embargo generalizaciones naturales de la reducibilidad Turing. Estos estudios incluyen enfoques para investigar la jerarquía analítica que difiere de la jerarquía aritmética permitiendo 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 las ordenaciones y árboles; por ejemplo, el conjunto de todos los índices de árboles computables (no binarios) sin ramas infinitas está completo para el nivel $Pi _{1}^{1}$ de la jerarquía analítica. Tanto la reducibilidad Turing como la reducibilidad hiperaritmética son importantes en el campo de la teoría de conjunto descriptiva eficaz. La noción más general de grados de constructibilidad se estudia en la teoría de conjuntos.

Teoría de la computabilidad continua

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. Por ejemplo, modelos de computación como el modelo de máquina Blum-Shub-Smale han formalizado la computación en los reales.

Relaciones entre definibilidad, prueba y computabilidad

Existe una estrecha relación entre el grado de Turing de un conjunto de números naturales y la dificultad (en términos de jerarquía aritmética) de definir ese conjunto mediante 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 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 efectiva de primer orden es un conjunto numerable computable, y que si la teoría es lo suficientemente fuerte, este conjunto será no computable. De manera similar, el teorema de indefinibilidad de Tarski puede interpretarse tanto en términos de definibilidad como 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 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 no computabilidad inherente a teoremas matemáticos bien conocidos. En 1999, Simpson discutió muchos aspectos de la aritmética de segundo orden y las matemáticas inversas.

El campo de la teoría de la demostración 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 que el sistema es total. Por ejemplo, en la aritmética recursiva primitiva, cualquier función computable que probablemente sea 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; el teorema de Goodstein proporciona un ejemplo de tal función.

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 recursión" desde sus inicios. Robert I. Soare, un destacado investigador en el campo, ha propuesto que el campo se denomine "teoría de la computabilidad" en cambio. Argumenta que la terminología de Turing usando la palabra 'computable' es más natural y se entiende mejor que la terminología que usa la palabra "recursiva" introducido por Kleene. Muchos investigadores contemporáneos han comenzado a utilizar esta terminología alternativa. Estos investigadores también usan terminología como función computable parcial y numerable computacionalmente (c.e.) conjunto en lugar de función recursiva parcial y recursivamente enumerable(r.e.)conjunto. Sin embargo, no todos los investigadores han quedado convencidos, como explican Fortnow y Simpson. Algunos comentaristas argumentan que tanto los nombres teoría de la recursividad 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.

En 1967, Rogers 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 en los números naturales (esta sugerencia se basa en las ideas del programa Erlangen en 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 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 mediante biyecciones computables de los números naturales.

Organizaciones profesionales

La principal organización profesional para la teoría de la computabilidad es la Association for Symbolic Logic, que organiza varias conferencias 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.

Contenido relacionado

Más resultados...