Grado de Turing

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.

Resumen

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

Artículo principal: reducción 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 ∪${\displaystyle {\mathcal {D}}}$b . Se sabe que no es una celosía , ya que existen pares de grados sin límite inferior mayor.${\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 del 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 lo tanto, no es una celosía.${\displaystyle {\mathcal {D}}}$
• Cada conjunto contable parcialmente ordenado puede integrarse en los grados de Turing.
• Ninguna secuencia de grados infinita y estrictamente creciente tiene un límite superior mínimo.

Propiedades que involucran 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.

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 mayor límite inferior 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 entramado distributivo finito 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 .

Problema de la publicación y método de prioridad

El "problema de la publicación" vuelve a dirigir aquí. Para el otro "problema de Post", consulte Problema de correspondencia de Post .

Emil Post studied the r.e. Turing degrees and asked whether there is any r.e. degree strictly between 0 and 0′. The problem of constructing such a degree (or showing that none exist) became known as Post's problem. This problem was solved independently by Friedberg and Muchnik in the 1950s, who showed that these intermediate r.e. degrees do exist. Their proofs each developed the same new method for constructing r.e. degrees, which came to be known as the priority method. The priority method is now the main technique for establishing results about r.e. sets.

The idea of the priority method for constructing a r.e. set X is to list a countable sequence of requirements that X must satisfy. For example, to construct a r.e. set X between 0 and 0′ it is enough to satisfy the requirements A_e and B_e for each natural number e, where A_e requires that the oracle machine with index e does not compute 0′ from X and B_e requires that the Turing machine with index e (and no oracle) does not compute X. These requirements are put into a priority ordering, which is an explicit bijection of the requirements and the natural numbers. The proof proceeds inductively with one stage for each natural number; these stages can be thought of as steps of time during which the set X is enumerated. At each stage, numbers may be put into X or forever prevented from entering X in an attempt to satisfy requirements (that is, force them to hold once all of X has been enumerated). Sometimes, a number can be enumerated into X to satisfy one requirement but doing this would cause a previously satisfied requirement to become unsatisfied (that is, to be injured). The priority order on requirements is used to determine which requirement to satisfy in this case. The informal idea is that if a requirement is injured then it will eventually stop being injured after all higher priority requirements have stopped being injured, although not every priority argument has this property. An argument must be made that the overall set X is r.e. and satisfies all the requirements. Priority arguments can be used to prove many facts about r.e. sets; the requirements used and the manner in which they are satisfied must be carefully chosen to produce the required result.

See also

• Martin measure

References

Monographs (undergraduate level)

• Cooper, S.B. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. ISBN 1-58488-237-9
• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7

Monographs and survey articles (graduate level)

• Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. ISBN 3-540-12155-2
• Odifreddi, P. G. (1989), Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, 125, Amsterdam: North-Holland, ISBN 978-0-444-87295-1, MR 0982269
• Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, 143, Amsterdam: North-Holland, ISBN 978-0-444-50205-6, MR 1718169
• Rogers, H. The Theory of Recursive Functions and Effective Computability, 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. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631–652.
• Shoenfield, Joseph R. Degrees of Unsolvability, North-Holland/Elsevier, ISBN 978-0-7204-2061-6.
• Shore, R. (1993), Univ. Nac. del Sur, Bahía Blanca (ed.), The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond, Notas Lógica Mat., 38, pp. 61–70
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR508451

Research papers

• Kleene, Stephen Cole; Post, Emil L. (1954), "The upper semi-lattice of degrees of recursive unsolvability", Annals of Mathematics, Second Series, 59 (3): 379–407, doi:10.2307/1969708, ISSN 0003-486X, JSTOR 1969708, MR 0061078
• Lachlan, A.H. (1966a), "Lower Bounds for Pairs of Recursively Enumerable Degrees", Proceedings of the London Mathematical Society, 3 (1): 537–569, CiteSeerX 10.1.1.106.7893, doi:10.1112/plms/s3-16.1.537.
• Lachlan, A.H. (1966b), "The impossibility of finding relative complements for recursively enumerable degrees", J. Symb. Log., 31 (3): 434–454, doi:10.2307/2270459, JSTOR 2270459.
• Lachlan, A.H.; Soare, R.I. (1980), "Not every finite lattice is embeddable in the recursively enumerable degrees", Advances in Mathematics, 37: 78–82, doi:10.1016/0001-8708(80)90027-4.
• Nies, André; Shore, Richard A.; Slaman, Theodore A. (1998), "Interpretability and definability in the recursively enumerable degrees", 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), "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, 50 (5): 284–316, doi:10.1090/S0002-9904-1944-08111-1, ISSN 0002-9904, MR 0010514
• Sacks, G.E. (1964), "The recursively enumerable degrees are dense", 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), "First-order theory of the degrees of recursive unsolvability", Annals of Mathematics, Second Series, 105 (1): 121–139, doi:10.2307/1971028, ISSN 0003-486X, JSTOR 1971028, MR 0432435
• Thomason, S.K. (1971), "Sublattices of the recursively enumerable degrees", Z. Math. Logik Grundlag. Math., 17: 273–280, doi:10.1002/malq.19710170131.
• Yates, C.E.M. (1966), "A minimal pair of recursively enumerable degrees", Journal of Symbolic Logic, 31 (2): 159–168, doi:10.2307/2269807, JSTOR 2269807.