grado de turing

Medida de insolubilidad

En informática y lógica matemática el grado de Turing (llamado así en honor a Alan Turing ) o grado de insolubilidad de un conjunto de números 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 números naturales suelen considerarse problemas de decisión . El grado de Turing de un conjunto es una medida de cuán difícil es resolver el problema de decisión asociado con el conjunto, es decir, determinar si un número arbitrario está en el conjunto dado.

Dos conjuntos son equivalentes a 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 diferentes grados de Turing 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 (posiblemente no computable) que decida correctamente si los números están en Y puede convertirse efectivamente a un procedimiento que decide correctamente 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 grados de Turing fueron introducidos por Post (1944) y Kleene y Post (1954) establecieron muchos resultados fundamentales. Los grados 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

Durante el resto de este artículo, la palabra conjunto se referirá a un conjunto de números naturales. Se dice que un conjunto X es reducible de Turing a un conjunto Y si hay una máquina oráculo de Turing que decide la membresía en X cuando se le da un oráculo para la membresía en Y. La notación X ≤ _T Y indica que X es reducible por Turing a Y.

Dos conjuntos X e Y se definen como equivalentes de Turing si X es Turing reducible a Y e Y es 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≡TX​_​ ​
• X ≡ _T Y implica Y ≡ _T X
• Si X ≡ _T Y e 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 ] denota 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 modo que [ X ] ≤ [ Y ] si y sólo si X ≤ _T Y . Existe 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 utilizar la notación en negrita para los grados de Turing, a fin de distinguirlos de los conjuntos. Cuando no puede haber confusión, como con [ X ], la negrita no es necesaria.) ${\displaystyle {\mathcal {D}}}$

Para cualquier conjunto X e Y , X se une a 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 límite superior mínimo de los grados de X e Y. Por lo tanto, es una semired de unión . El límite superior mínimo de grados a y b se denota a ∪ b . Se sabe que no es una red , ya que hay pares de grados sin límite inferior máximo. ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {D}}}$

Para cualquier conjunto X, la notación X ′ denota el conjunto de índices de máquinas Oracle que se detienen (cuando se les da su índice como entrada) cuando usan X como oráculo. El conjunto X ′ se llama salto de Turing de 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 ′ siempre 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 contablemente 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 debajo de a es contable . El conjunto de grados mayor que a tiene tamaño . ${\displaystyle 2^{\aleph _{0}}}$

Estructura de los grados de Turing

Se han realizado muchas investigaciones sobre la estructura de los grados de Turing. La siguiente encuesta enumera sólo algunos de los muchos resultados conocidos. Una conclusión general que se puede extraer de la investigación es que la estructura de los grados 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 .
• Los grados de Turing no están ordenados linealmente por ≤ _T. ^[1]
• De hecho, por cada grado a distinto de cero hay un grado b incomparable con a .
• 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 puede incluirse en los grados de Turing.
• Una secuencia infinita estrictamente creciente a ₁ , a ₂ , ... de grados de Turing no puede tener el mínimo límite superior, pero siempre tiene un par exacto c , d tal que ∀ e ( e < c ∧ e < d ⇔ ∃ i e ≤ a _i ), y por lo tanto tiene límites superiores mínimos (no únicos).
• Asumiendo el axioma de constructibilidad , se puede demostrar que existe una cadena máxima de grados de tipo de orden . ^[2] ${\displaystyle \omega _{1}}$

Propiedades que involucran el salto.

• Por cada grado a hay un grado estrictamente entre a y a′ . De hecho, existe una familia contable de grados incomparables por pares entre a y a′ .
• Inversión de salto: un grado a es de la forma b′ si y sólo si 0′ ≤ a .
• Para cualquier grado a existe un grado b tal que a < b y b′ = a′ ; tal grado b se llama bajo en relación con a .
• Existe una secuencia infinita a _i de grados tal que a ′ _{i +1} ≤ a _i para cada i .
• El teorema de Post establece una estrecha correspondencia entre la jerarquía aritmética y los saltos de Turing del conjunto vacío con iteraciones finitas.

Propiedades lógicas

• Simpson (1977b) demostró que la teoría de primer orden de en el lenguaje ⟨ ≤, = ⟩ o ⟨ ≤, ′, = ⟩ es equivalente muchos uno 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 se puede definir en la estructura de primer orden con el lenguaje ⟨ ≤, = ⟩ . ${\displaystyle {\mathcal {D}}}$

Grados de Turing recursivamente enumerables

Una red finita que no se puede incrustar en los grados re.

Un grado se llama recursivamente enumerable (re) o computablemente enumerable (ce) si contiene un conjunto recursivamente enumerable . Cada grado re está por debajo de 0′ , pero no todos los grados por debajo de 0′ son re. Sin embargo, un conjunto es reducible muchos uno a 0′ si y sólo si es re. ^[3] ${\displaystyle A}$ ${\displaystyle A}$

• Sacks (1964): Los grados son densos; entre dos re grados cualesquiera hay un tercer re grado.
• Lachlan (1966a) y Yates (1966): Hay dos grados re sin límite inferior máximo en los grados re.
• Lachlan (1966a) y Yates (1966): Hay un par de grados distintos de cero cuyo límite inferior mayor es 0 .
• Lachlan (1966b): No existe ningún par de re grados 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 .
• Thomason (1971): Cada red distributiva finita puede integrarse en los grados re. De hecho, el álgebra booleana contable y sin átomos se puede incrustar de una manera que preserve suprema e ínfima .
• Lachlan y Soare (1980): No todas las redes finitas pueden incrustarse en los grados re (mediante una incrustación que preserve suprema e ínfima). A la derecha se muestra un ejemplo particular. LA Harrington y TA Slaman (ver Nies, Shore & Slaman (1998)): La teoría de primer orden de los re grados en el lenguaje ⟨ 0 , ≤, = ⟩ es equivalente a muchos uno de la teoría de la verdadera aritmética de primer orden. .

Además, existe el lema límite de Shoenfield, un conjunto A satisface si y sólo si hay una "aproximación recursiva" a su función característica: una función g tal que para s suficientemente grande , . ^[4] ${\displaystyle [A]\leq _{T}\emptyset '}$ ${\displaystyle g(s)=\chi _{A}(s)}$

Un conjunto A se llama n -r e. si existe una familia de funciones tal que: ^[4] ${\displaystyle (A_{s})_{s\in \mathbb {N} }}$

• A _s es una aproximación recursiva de A : para algún t , para cualquier s ≥ t tenemos A _s ( x ) = A ( x ), en particular combinando A con su función característica. (La eliminación de esta condición produce una definición de que A es "débilmente n -re" )
• A _s es un " predicado de n prueba": para todo x , A ₀ ( x )=0 y la cardinalidad de es ≤n. ${\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}$

Propiedades de n -re grados: ^[4]

• La clase de conjuntos de n -re grado es una subclase estricta de la clase de conjuntos de ( n +1)-re grado.
• Para todo n >1 hay dos ( n +1) -re grados a , b con , tales que el segmento no contiene n -re grados. ${\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }$ ${\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}$
• ${\displaystyle A}$y son ( n +1 ) -re si ambos conjuntos son débilmente - n -re ${\displaystyle {\overline {A}}}$

El problema de Post y el método de prioridad.

Emil Post estudió los grados de Turing y preguntó si existe algún grado estrictamente entre 0 y 0′ . El problema de construir tal grado (o demostrar que no existe ninguno) pasó a conocerse 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 existen ( teorema de Friedberg-Muchnik ). Cada una de sus pruebas desarrolló el mismo nuevo método 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 reinicios.

La idea del método de prioridad para construir un conjunto de reinicio X es enumerar una secuencia contable de requisitos que X debe satisfacer. Por ejemplo, para construir un reinicio 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 _e requiere que la máquina de Turing con índice e (y sin 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 prueba procede de forma inductiva con una etapa para cada número natural; Estas etapas pueden considerarse como pasos de tiempo durante los cuales se enumera el conjunto X. En cada etapa, se pueden poner números en X o impedir para siempre (si no se daña) que entren en X en un intento de satisfacer los requisitos (es decir, obligarlos a mantenerse una vez que se haya enumerado todo X ). A veces, un número se puede enumerar en X para satisfacer un requisito, pero hacerlo provocaría que un requisito previamente satisfecho quede insatisfecho (es decir, resulte perjudicado ). El orden de prioridad de los requisitos se utiliza para determinar qué requisito satisfacer en este caso. La idea informal es que si un requisito se daña, eventualmente dejará de dañarse después de que todos los requisitos de mayor prioridad hayan dejado de dañarse, aunque no todos los argumentos de prioridad tienen esta propiedad. Se debe argumentar que el conjunto global X es re y satisface todos los requisitos. Los argumentos de prioridad se pueden utilizar para probar muchos hechos sobre los reinicios; Los requisitos utilizados y la manera en que se satisfacen deben elegirse cuidadosamente para producir el resultado requerido.

Por ejemplo, un re) bajo X simple (y por lo tanto no computable) (bajo significa X ′=0′) se puede construir en infinitas etapas de la siguiente manera. Al comienzo de la etapa n , sea T _n la cinta de salida (binaria), identificada con el conjunto de índices de celda donde hemos colocado 1 hasta ahora (por lo que X =∪ _n T _n ; T ₀ =∅); y sea P _n ( m ) la prioridad para no generar 1 en la ubicación m ; P ₀ ( m )=∞. En la etapa n , si es posible (de lo contrario no haga nada en la etapa), elija el mínimo i < n tal que ∀ m P _n ( m )≠ i y la máquina de Turing i se detenga en < n pasos en alguna entrada S ⊇ T _n con ∀ metro ∈ S \ T _norte P _norte ( metro )≥ yo . Elija cualquier S (finito) , establezca T _{n +1} = S , y para cada celda m visitada por la máquina i en S , establezca P _{n +1} ( m ) = min( i , P _n ( m )), y establezca todas las prioridades > i a ∞, y luego establezca una celda de prioridad ∞ (cualquiera servirá) que no esté en S con prioridad i . Esencialmente, hacemos que la máquina i se detenga si podemos hacerlo sin alterar las prioridades < i , y luego establecemos prioridades para evitar que las máquinas > i interrumpan la parada; todas las prioridades son finalmente constantes.

Para ver que X es bajo, la máquina i se detiene en X si se detiene en < n pasos en algún T _n tal que las máquinas < i que se detienen en X lo hacen < n - i pasos (por recursividad, esto es uniformemente computable desde 0′ ). X no es computable ya que de lo contrario una máquina de Turing podría detenerse en Y si Y \ X no está vacío, lo que contradice la construcción ya que X excluye algunas celdas i de prioridad para i arbitrariamente grande ; y X es simple porque para cada i el número de celdas de prioridad i es finito.

Ver también

• medida martin

Referencias

Monografías (nivel pregrado)

• Cooper, SB (2004). Teoría de la computabilidad . Boca Ratón, FL: Chapman & Hall/CRC. pag. 424.ISBN​ 1-58488-237-9.
• Cutland, Nigel J. (1980). Computabilidad, una introducción a la teoría de funciones recursivas . Cambridge-Nueva York: Cambridge University Press. pag. 251.ISBN​ 0-521-22384-9.; ISBN 0-521-29465-7 

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

• Ambos-Spies, Klaus; Fejer, Peter (20 de marzo de 2006). "Grados de insolubilidad" (PDF) . Consultado el 20 de agosto de 2023 . Inédito
• Epstein, RL; Haas, R; Kramer, LR (1981). Lemán, M; Schmerl, J.; Soare, R. (eds.). Jerarquías de conjuntos y grados inferiores a 0 . Apuntes de conferencias de matemáticas. vol. 859. Springer-Verlag.
• Lerman, M. (1983). Grados de insolubilidad. Perspectivas en lógica matemática . Berlín: Springer-Verlag. ISBN 3-540-12155-2.
• Odifreddi, Piergiorgio (1989). Teoría clásica de la recursión . Estudios de Lógica y Fundamentos de las Matemáticas. vol. 125. Ámsterdam: Holanda Septentrional. ISBN 978-0-444-87295-1. SEÑOR  0982269.
• Odifreddi, Piergiorgio (1999). Teoría clásica de la recursión. vol. II . Estudios de Lógica y Fundamentos de las Matemáticas. vol. 143. Ámsterdam: Holanda Septentrional. ISBN 978-0-444-50205-6. SEÑOR  1718169.
• Rogers, Hartley (1967). Teoría de funciones recursivas y computabilidad efectiva . Cambridge, Massachusetts : MIT Press . ISBN 9780262680523. OCLC  933975989 . Consultado el 6 de mayo de 2020 .
• Sacos, GE (1966). Grados de insolubilidad . Anales de estudios de matemáticas. Prensa de la Universidad de Princeton. ISBN 978-0-6910-7941-7. JSTOR  j.ctt1b9x0r8.
• Simpson, Steven G. (1977a). "Grados de insolubilidad: una encuesta de resultados". Anales de estudios de matemáticas . Estudios de Lógica y Fundamentos de las Matemáticas. 90 . Elsevier : 631–652. doi :10.1016/S0049-237X(08)71117-0. ISBN 9780444863881.
• Shoenfield, José R. (1971). Grados de insolubilidad . Holanda Septentrional/Elsevier. ISBN 978-0-7204-2061-6.
• Orilla, R. (1993). "Las teorías de los grados T, tt y wtt re: indecidibilidad y más allá". En la 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. vol. 38. págs. 61–70.
• Soare, Robert Irving (1987). Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente . Perspectivas en lógica matemática. Berlín: Springer-Verlag. ISBN 3-540-15299-7.
• Soare, Robert Irving (1978). "Conjuntos y grados recursivamente enumerables". Toro. América. Matemáticas. Soc . 84 (6): 1149-1181. doi : 10.1090/S0002-9904-1978-14552-2 . SEÑOR  0508451. S2CID  29549997.

Trabajos de investigación

• Chong, CT; Yu, Liang (diciembre de 2007). "Cadenas máximas en los grados de Turing". Revista de Lógica Simbólica . 72 (4): 1219-1227. doi :10.2178/jsl/1203350783. JSTOR  27588601. S2CID  38576214.
• DeAntonio, Jasper (24 de septiembre de 2010). «Los grados de Turing y su falta de orden lineal» (PDF) . Consultado el 20 de agosto de 2023 .
• Kleene, Stephen Cole ; Post, Emil L. (1954), "La semired superior de grados de insolubilidad recursiva", Annals of Mathematics , Segunda Serie, 59 (3): 379–407, doi :10.2307/1969708, ISSN  0003-486X, JSTOR  1969708, señor  0061078
• Lachlan, Alistair H. (1966a), "Límites inferiores para pares de grados enumerables recursivamente", Actas de la Sociedad Matemática de Londres , 3 (1): 537–569, CiteSeerX  10.1.1.106.7893 , doi :10.1112/plms/s3 -16.1.537.
• Lachlan, Alistair H. (1966b), "La imposibilidad de encontrar complementos relativos para grados recursivamente enumerables", J. Symb. Registro. , 31 (3): 434–454, doi :10.2307/2270459, JSTOR  2270459, S2CID  30992462.
• Lachlan, Alistair H.; Soare, Robert Irving (1980), "No todas las redes finitas son integrables en grados recursivamente enumerables", Advances in Mathematics , 37 : 78–82, doi : 10.1016/0001-8708(80)90027-4
• Nies, André; Orilla, Richard A.; Slaman, Theodore A. (1998), "Interpretabilidad y definibilidad en grados recursivamente enumerables", Actas de la Sociedad Matemática de Londres , 77 (2): 241–291, CiteSeerX  10.1.1.29.9588 , doi :10.1112/S002461159800046X, ISSN  0024-6115, SEÑOR  1635141, S2CID  16488410
• Post, Emil L. (1944), "Conjuntos enumerables recursivamente de números enteros positivos y sus problemas de decisión", Boletín de la Sociedad Matemática Estadounidense , 50 (5): 284–316, doi : 10.1090/S0002-9904-1944-08111- 1 , ISSN  0002-9904, SEÑOR  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
• Orilla, Richard A .; Slaman, Theodore A. (1999), "Definición del salto de Turing", Mathematical Research Letters , 6 (6): 711–722, doi : 10.4310/mrl.1999.v6.n6.a10 , ISSN  1073-2780, SEÑOR  1739227
• Simpson, Stephen G. (1977b). "Teoría de primer orden de los grados de insolubilidad recursiva". Anales de Matemáticas . Segunda Serie. 105 (1): 121-139. doi :10.2307/1971028. ISSN  0003-486X. JSTOR  1971028. SEÑOR  0432435.
• Thomason, SK (1971), "Subredes de 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, S2CID  38778059

Notas

1. DeAntonio 2010, pag. 9.
2. Chong y Yu 2007, pág. 1224.
3. Odifreddi 1989, pag. 252, 258.
4. Epstein, Haas y Kramer 1981.