Grado de Turing - Turing degree

En informática y lógica matemática, el grado de Turing (llamado así por Alan Turing ) o grado de insolubilidad de un conjunto de números naturales mide el nivel de insolubilidad algorítmica del conjunto.

Visión general

El concepto de grado de Turing es fundamental en la teoría de la computabilidad , donde los conjuntos de números naturales a menudo se consideran problemas de decisión . El grado de Turing de un conjunto es una medida de lo difícil que es resolver el problema de decisión asociado con el conjunto, es decir, determinar si hay un número arbitrario en el conjunto dado.

Dos conjuntos son equivalentes de Turing si tienen el mismo nivel de insolubilidad; cada grado de Turing es una colección de conjuntos equivalentes de Turing, de modo que dos conjuntos están en grados de Turing diferentes exactamente cuando no son equivalentes de Turing. Además, los grados de Turing están parcialmente ordenados de modo que si el grado de Turing de un conjunto X es menor que el grado de Turing de un conjunto Y, entonces cualquier procedimiento (no computable) que decida correctamente si los números están en Y puede convertirse efectivamente en un procedimiento que correctamente decide si los números están en X . Es en este sentido que el grado de Turing de un conjunto corresponde a su nivel de insolubilidad algorítmica.

Los títulos de Turing fueron introducidos por Emil Leon Post (1944), y Stephen Cole Kleene y Post (1954) establecieron muchos resultados fundamentales . Los títulos de Turing han sido un área de intensa investigación desde entonces. Muchas pruebas en el área utilizan una técnica de prueba conocida como método de prioridad .

Equivalencia de Turing

En el resto de este artículo, el conjunto de palabras se referirá a un conjunto de números naturales. Un conjunto X se dice que es Turing reducible a un conjunto Y si hay una máquina de Turing oráculo que decide la pertenencia a X cuando se les da un oráculo para ser miembro de Y . La notación X ≤ _T Y indica que X es Turing reducible a Y .

Dos conjuntos de X y Y se definen para ser Turing equivalente si X es Turing reducible a Y y Y se Turing reducible a X . La notación X ≡ _T Y indica que X e Y son equivalentes de Turing. La relación ≡ _T puede verse como una relación de equivalencia , lo que significa que para todos los conjuntos X , Y y Z :

• X ≡ _T X
• X ≡ _T Y implica Y ≡ _T X
• Si X ≡ _T Y y Y ≡ _T Z entonces X ≡ _T Z .

Un grado de Turing es una clase de equivalencia de la relación ≡ _T . La notación [ X ] indica la clase de equivalencia que contiene un conjunto X . Se denota toda la colección de grados de Turing . ${\ Displaystyle {\ mathcal {D}}}$

Los grados de Turing tienen un orden parcial ≤ definido de manera que [ X ] ≤ [ Y ] si y sólo si X ≤ _T Y . Hay un grado de Turing único que contiene todos los conjuntos computables, y este grado es menor que cualquier otro grado. Se denota 0 (cero) porque es el elemento menor del poset . (Es común usar la notación en negrita para los grados de Turing, a fin de distinguirlos de los conjuntos. Cuando no puede ocurrir confusión, como con [ X ], la negrita no es necesaria). ${\ Displaystyle {\ mathcal {D}}}$

Para cualquier conjunto X e Y , X une Y, escrito X ⊕ Y , se define como la unión de los conjuntos {2 n  : n ∈ X } y {2 m +1: m ∈ Y }. El grado de Turing de X ⊕ Y es el extremo superior de los grados de X y Y . Así es una unión-semirrejilla . El extremo superior de grados a y b se denota un ∪ b . Se sabe que no es una celosía , ya que existen pares de grados sin límite inferior mayor. ${\ Displaystyle {\ mathcal {D}}}$${\ Displaystyle {\ mathcal {D}}}$

Para cualquier conjunto X, la notación X ′ denota el conjunto de índices de máquinas oráculo que se detienen (cuando se les da su índice como entrada) cuando se usa X como oráculo. El conjunto X 'se llama el salto de Turing del X . El salto de Turing de un grado [ X ] se define como el grado [ X ′]; esta es una definición válida porque X '≡ _T Y ' cada vez que X ≡ _T Y . Un ejemplo clave es 0 ′, el grado del problema de detención .

Propiedades básicas de los grados de Turing

• Cada grado de Turing es numerablemente infinito , es decir, contiene exactamente conjuntos.${\ Displaystyle \ aleph _ {0}}$
• Hay distintos grados de Turing.${\ Displaystyle 2 ^ {\ aleph _ {0}}}$
• Para cada grado a se cumple la desigualdad estricta a < a ′.
• Para cada grado a , el conjunto de grados por debajo de a es contable . El conjunto de grados mayores que un tamaño tiene .${\ Displaystyle 2 ^ {\ aleph _ {0}}}$

Estructura de los grados de Turing

Se ha realizado una gran cantidad de investigación sobre la estructura de los títulos de Turing. La siguiente encuesta enumera solo algunos de los muchos resultados conocidos. Una conclusión general que se puede extraer de la investigación es que la estructura de los títulos de Turing es extremadamente complicada.

Propiedades de pedido

• Hay grados mínimos . Un grado a es mínimo si a es distinto de cero y no hay ningún grado entre 0 y a . Por tanto, la relación de orden en los grados no es un orden denso .
• Por cada grado distinto de cero una hay un grado b incomparables con una .
• Hay un conjunto de grados de Turing incomparables por pares.${\ Displaystyle 2 ^ {\ aleph _ {0}}}$
• Hay pares de grados sin límite inferior máximo. Por tanto, no es una celosía.${\ Displaystyle {\ mathcal {D}}}$
• Cada conjunto contable parcialmente ordenado se puede incrustar en los grados de Turing.
• Ninguna secuencia de grados infinita y estrictamente creciente tiene un límite superior mínimo.

Propiedades que implican el salto

• Por cada grado una hay un grado estrictamente entre una y una " . De hecho, hay una familia numerable de grados incomparables por parejas entre una y una " .
• Inversión de salto: un grado a tiene la forma b ′ si y solo si 0 ′ ≤ a .
• Para cualquier grado a hay un grado b tal que a < b y b ′ = a ′ ; tal grado b se llama bajo en relación con a .
• Hay una secuencia infinita a _i de grados tal que a ′ _{i +1} ≤ a _i para cada i .

Propiedades lógicas

• Simpson (1977) mostró que la teoría de primer orden de en el lenguaje ⟨≤, =⟩ o ⟨≤, ′, =⟩ es muchos-uno equivalente a la teoría de la verdadera aritmética de segundo orden . Esto indica que la estructura de es extremadamente complicada.${\ Displaystyle {\ mathcal {D}}}$${\ Displaystyle {\ mathcal {D}}}$
• Shore y Slaman (1999) demostraron que el operador de salto es definible en la estructura de primer orden de con el lenguaje ⟨≤, =⟩ .${\ Displaystyle {\ mathcal {D}}}$

Grados de Turing recursivamente enumerables

Una celosía finita que no se puede incrustar en los grados re.

Un grado se denomina recursivamente enumerable (re) si contiene un conjunto recursivamente enumerable . Cada grado re está por debajo de 0 ′ , pero no todo grado por debajo de 0 ′ es re.

• ( GE Sacks , 1964) Los grados son densos; entre dos grados cualesquiera hay un tercer grado.
• (AH Lachlan, 1966a y CEM Yates, 1966) Hay dos grados re sin límite inferior máximo en los grados re.
• (AH Lachlan, 1966a y CEM Yates, 1966) Hay un par de grados re distintos de cero cuyo mayor límite inferior es 0 .
• (AH Lachlan, 1966b) No existe un par de grados re cuyo límite inferior mayor sea 0 y cuyo límite superior mínimo sea 0 ′ . Este resultado se denomina informalmente teorema del no diamante .
• (SK Thomason, 1971) Cada retícula distributiva finita se puede incrustar en los grados. De hecho, el álgebra booleana sin átomos contables se puede incrustar de una manera que conserve suprema e infima .
• (AH Lachlan y RI Soare , 1980) No todas las celosías finitas se pueden incrustar en los grados re (a través de una incrustación que preserva suprema e infima). Un ejemplo particular se muestra a la derecha.
• ( LA Harrington y TA Slaman , ver Nies, Shore y Slaman (1998)) La teoría de primer orden de los grados re en el idioma ⟨ 0 , ≤, =⟩ es mucho-uno equivalente a la teoría de la verdad de primer orden aritmética .

El problema de la publicación y el método de prioridad

Emil Post estudió los grados re Turing y preguntó si hay algún grado re estrictamente entre 0 y 0 ′ . El problema de construir tal título (o demostrar que no existe) se conoció como el problema de Post . Este problema fue resuelto de forma independiente por Friedberg y Muchnik en la década de 1950, quienes demostraron que estos grados intermedios sí existen. Cada una de sus pruebas desarrolló el mismo método nuevo para construir re grados, que llegó a conocerse como el método de prioridad . El método de prioridad es ahora la técnica principal para establecer resultados sobre reajustes.

La idea del método de prioridad para construir un conjunto X es enumerar una secuencia contable de requisitos que X debe satisfacer. Por ejemplo, para construir un re conjunto X entre 0 y 0 ′ es suficiente satisfacer los requisitos A _e y B _e para cada número natural e , donde A _e requiere que la máquina oráculo con índice e no calcule 0 ′ a partir de X y B _correo requiere que la máquina de Turing con el índice de correo (y ningún oráculo) no calcule X . Estos requisitos se colocan en un orden de prioridad , que es una biyección explícita de los requisitos y los números naturales. La demostración procede inductivamente con una etapa para cada número natural; estas etapas pueden considerarse como etapas de tiempo durante las cuales se enumera el conjunto X. En cada etapa, los números pueden colocarse en X o evitar para siempre que ingresen X en un intento de satisfacer los requisitos (es decir, obligarlos a que se mantengan una vez que se haya enumerado todo X ). A veces, un número se puede enumerar en X para satisfacer un requisito, pero hacer esto provocaría que un requisito previamente satisfecho no se satisfaga (es decir, se lesione ). El orden de prioridad de los requisitos se utiliza para determinar qué requisito satisfacer en este caso. La idea informal es que si se daña un requisito, eventualmente dejará de estar dañado después de que todos los requisitos de mayor prioridad hayan dejado de serlo, aunque no todos los argumentos de prioridad tienen esta propiedad. Se debe argumentar que el conjunto general X es re y satisface todos los requisitos. Los argumentos de prioridad se pueden utilizar para probar muchos hechos sobre reajustes; Los requisitos utilizados y la forma en que se satisfacen deben elegirse cuidadosamente para producir el resultado requerido.

Ver también

• Medida martin

Referencias

Monografías (nivel de pregrado)

• Cooper, SB Teoría de la computabilidad . Chapman & Hall / CRC, Boca Raton, FL, 2004. ISBN  1-58488-237-9
• Cutland, N. Computabilidad. Cambridge University Press, Cambridge-Nueva York, 1980. ISBN  0-521-22384-9 ; ISBN  0-521-29465-7

Monografías y artículos de encuestas (nivel de posgrado)

• Ambos-Spies, K. y Fejer, P. Grados de insolubilidad. Inédito. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. Grados de insolubilidad. Perspectivas en lógica matemática. Springer-Verlag, Berlín, 1983. ISBN  3-540-12155-2
• Odifreddi, PG (1989), Teoría de la recursividad clásica , Estudios de lógica y fundamentos de las matemáticas, 125 , Amsterdam: Holanda Septentrional, ISBN 978-0-444-87295-1, MR  0982269
• Odifreddi, PG (1999), Teoría de la recursividad clásica. Vol. II , Estudios de lógica y fundamentos de las matemáticas, 143 , Amsterdam: Holanda Septentrional, ISBN 978-0-444-50205-6, Señor  1718169
• Rogers, H. La teoría de las funciones recursivas y la computabilidad efectiva , MIT Press. ISBN  0-262-68052-1 , ISBN  0-07-053522-1
• Sacks, Gerald E. Degrees of Unsolvability (Annals of Mathematics Studies), Princeton University Press. ISBN  978-0-6910-7941-7
• Simpson, S. Grados de insolubilidad: una encuesta de resultados. Manual de lógica matemática , Holanda Septentrional, 1977, págs. 631–652.
• Shoenfield, Joseph R. Grados de insolubilidad , Holanda Septentrional / Elsevier, ISBN  978-0-7204-2061-6 .
• Shore, R. (1993). "Las teorías de los grados T, tt y wtt re: indecidibilidad y más allá". En Univ. Nac. del Sur, Bahía Blanca (ed.). Actas del IX Simposio Latinoamericano de Lógica Matemática, Parte 1 (Bahía Blanca, 1992) . Notas Lógica Mat. 38 . págs. 61–70.
• Soare, R. Conjuntos y grados recursivamente enumerables. Perspectivas en lógica matemática. Springer-Verlag, Berlín, 1987. ISBN  3-540-15299-7
• Soare, Robert I. Conjuntos y grados recursivamente enumerables. Toro. Amer. Matemáticas. Soc. 84 (1978), núm. 6, 1149-1181. Señor 508451

Trabajos de investigación

• Kleene, Stephen Cole ; Post, Emil L. (1954), "El semienrejado superior de grados de insolubilidad recursiva", Annals of Mathematics , Second Series, 59 (3): 379–407, doi : 10.2307 / 1969708 , ISSN  0003-486X , JSTOR  1969708 , MR  0061078
• Lachlan, AH (1966a), "Límites inferiores para pares de grados recursivamente enumerables", Actas de la London Mathematical Society , 3 (1): 537–569, CiteSeerX  10.1.1.106.7893 , doi : 10.1112 / plms / s3-16.1 .537 .
• Lachlan, AH (1966b), "La imposibilidad de encontrar complementos relativos para grados recursivamente enumerables", J. Symb. Tronco. , 31 (3): 434–454, doi : 10.2307 / 2270459 , JSTOR  2270459 .
• Lachlan, AH; Soare, RI (1980), "No todas las celosías finitas se pueden incrustar en los grados recursivamente enumerables", Advances in Mathematics , 37 : 78-82, doi : 10.1016 / 0001-8708 (80) 90027-4 .
• Nies, André; Shore, Richard A .; Slaman, Theodore A. (1998), "Interpretabilidad y definibilidad en los grados recursivamente enumerables", Proceedings of the London Mathematical Society , 77 (2): 241-291, CiteSeerX  10.1.1.29.9588 , doi : 10.1112 / S002461159800046X , ISSN  0024-6115 , MR  1635141
• Post, Emil L. (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 , ISSN  0002-9904 , Sr.  0010514
• Sacks, GE (1964), "Los grados recursivamente enumerables son densos", Annals of Mathematics , Second Series, 80 (2): 300-312, doi : 10.2307 / 1970393 , JSTOR  1970393 .
• Shore, Richard A .; Slaman, Theodore A. (1999), "Defining the Turing jump", Mathematical Research Letters , 6 (6): 711–722, doi : 10.4310 / mrl.1999.v6.n6.a10 , ISSN  1073-2780 , MR  1739227
• Simpson, Stephen G. (1977), "Teoría de primer orden de los grados de insolubilidad recursiva", Annals of Mathematics , Second Series, 105 (1): 121-139, doi : 10.2307 / 1971028 , ISSN  0003-486X , JSTOR  1971028 , MR  0432435
• Thomason, SK (1971), "Sublattices de los grados recursivamente enumerables", Z. Math. Logik Grundlag. Matemáticas. , 17 : 273–280, doi : 10.1002 / malq.19710170131 .
• Yates, CEM (1966), "Un par mínimo de grados recursivamente enumerables", Journal of Symbolic Logic , 31 (2): 159-168, doi : 10.2307 / 2269807 , JSTOR  2269807 .