Grado de Turing

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

Descripción general

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

Dos conjuntos son equivalentes a Turing si tienen el mismo nivel de insolvencia; cada grado de Turing es una colección de conjuntos equivalentes de Turing, de modo que dos conjuntos con un grado de Turing diferente 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 (recursivo) que decida correctamente si los números están en Y se puede convertir eficientemente en un procedimiento que decide si los números son adecuadamente en X . Por tanto, 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 . Por lo tanto, los títulos de Turing han sido un área de intensa investigación.

Equivalencia de Turing

En todo este artículo, el conjunto de palabras se referirá a un conjunto de números naturales. Un conjunto X se dice Turing reducible a un conjunto Y si un oráculo que decide ser miembro de X cuando un oráculo decide 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 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 a Turing. La relación ≡ T puede verse como una relación de equivalencia , lo que significa que para cualquier conjunto 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 . $\ mathcal {D}$

Los grados de Turing están provistos de un orden parcial ≤ definido tal que [X] ≤ [Y] si y sólo si X ≤ T Y . El grado de Turing que contiene todos los conjuntos recursivos es el grado de Turing más pequeño, se anota 0 (cero).

Para cualquier conjunto X e Y , X se une a Y, denotado 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 X ⊕ Y es el límite superior de los grados de X y Y . Entonces, es una semi- celosía . El límite superior de los grados de un y b se denota un ∪ b . $\ mathcal {D}$

Para cualquier conjunto X , la notación X ' denota el conjunto de programas que utilizan un oráculo (o sus índices) que se detienen cuando X se utiliza como un oráculo. El conjunto X ' se llama el salto de Turing (en) de X . El salto de Turing de un grado [X] se define como el grado [X ']; Esta es una definición válida como X '≡ T Y ' cuando X ≡ T Y . Un ejemplo clave es 0 ′, el grado del problema de frenado .

Propiedades básicas

Cada grado de Turing es infinito contable , es decir, contiene exactamente conjuntos. $\ aleph_0$
Hay distintos grados de Turing. $2 ^ {\ aleph _ {0}}$
Para cada grado a , tenemos la desigualdad estricta a < a ′.
Para cada grado a , el conjunto de grados menores que a es contable . El conjunto de grados mayores que a es cardinal . $2 ^ {\ aleph _ {0}}$

Estructura

Se han realizado muchas investigaciones sobre la estructura de los títulos de Turing. Las siguientes propiedades son solo algunas de las muchas que existen. Una conclusión general que se puede extraer de esta investigación es que la estructura de los títulos de Turing es extremadamente complicada.

Propiedades teóricas de orden

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 .
Para cada grado distinto de cero un , existe un grado b incomparable con un .
Hay un conjunto de incomparables grados de Turing de dos a dos. $2 ^ {\ aleph _ {0}}$
Hay pares de grados sin límite inferior . Entonces, no es una celosía. $\ mathcal {D}$
Se sumerge cualquier conjunto contable parcialmente ordenado . $\ mathcal {D}$
Ninguna secuencia infinita estrictamente creciente de grados de Turing tiene un límite superior.

Propiedades que implican el salto

Por cada grado una , hay un grado entre una y una " . De hecho, existe una sucesión numerable de incomparables grados de dos por dos entre una y una ' .
Un grado a es de la forma b ′ si y solo si 0 ′ ≤ a .
Para cualquier grado a , existe un grado b tal que a < b y b ′ = a ′ ; tal grado b se dice que es bajo con respecto a 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 equivalente muchos-uno (en) a la teoría aritmética de segundo orden. Esto indica que la estructura de es extremadamente complicada. $\ mathcal {D}$ $\ mathcal {D}$
Shore y Slaman (1999) han demostrado que el operador de salto es definible en la estructura de grados de primer orden en el lenguaje ⟨≤, =⟩.

Ver también

Medida martin
máquina de Turing

Referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado " Turing degree " ( ver la lista de autores ) .

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 estudios (nivel universitario)

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 )
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-0691079417 )
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-0720420616 ) .
Shore, R. Las teorías de los grados T, tt y wtt re: indecidibilidad y más allá. Actas del IX Simposio Latinoamericano de Lógica Matemática, Parte 1 (Bahía Blanca, 1992), 61–70, Notas Lógica Mat., 38, Univ. Nac. del Sur, Bahía Blanca, 1993.
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. Amargo. Matemáticas. Soc. 84 (1978), núm. 6, 1149-1181. Enlace de revisiones de matemáticas

Trabajos de investigación

Kleene, Stephen Cole ; Post, Emil L. (1954), "La semienrejilla 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, doi : 10.1112 / plms / s3-16.1.537 .
Lachlan, AH (1966b), "La imposibilidad de encontrar complementos relativos para grados recursivamente enumerables", J. Symb. Logic , 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 Math , 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, 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 : 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", J. Symbolic Logic , 31 (2): 159-168, doi : 10.2307 / 2269807 , JSTOR 2269807 .