grado de Turing

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

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 la dificultad para resolver el problema de decisión asociado a dicho conjunto, es decir, determinar si un número arbitrario pertenece al conjunto dado.

Dos conjuntos son Turing equivalentes si tienen el mismo nivel de insolubilidad; cada grado de Turing es una colección de conjuntos Turing equivalentes, de modo que dos conjuntos tienen grados de Turing diferentes precisamente cuando no son Turing equivalentes. Además, los grados de Turing están parcialmente ordenados , de manera 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 en un procedimiento que decida 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 muchos resultados fundamentales fueron establecidos por Kleene y Post (1954) . Desde entonces, los grados de Turing han sido objeto de intensa investigación. Muchas demostraciones en este campo utilizan una técnica conocida como método de prioridad .

En el resto de este artículo, el término conjunto se referirá a un conjunto de números naturales. Se dice que un conjunto X es Turing reducible a un conjunto Y si existe una máquina de Turing oráculo que decide la pertenencia a X cuando se le da un oráculo para la pertenencia a Y. La notación X ≤ _T Y indica que X es Turing reducible a Y.

Dos conjuntos X e Y se definen como Turing equivalentes 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 Turing equivalentes. 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 ] denota la clase de equivalencia que contiene un conjunto X. La colección completa de grados de Turing se denota${\displaystyle {\mathcal {D}}}$.

Los grados de Turing tienen un orden parcial ≤ definido de modo que [ X ] ≤ [ Y ] si y solo si X ≤ _T Y . Existe un único grado de Turing que contiene todos los conjuntos computables , y este grado es menor que cualquier otro grado. Se denota como 0 (cero) porque es el elemento más pequeño del conjunto parcialmente ordenado.${\displaystyle {\mathcal {D}}}$(Es común usar la notación en negrita para los grados de Turing, con el fin de distinguirlos de los conjuntos. Cuando no puede haber confusión, como con [ X ], la negrita no es necesaria).

Para cualesquiera conjuntos X e Y , el conjunto X ⊕ 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 la menor cota superior de los grados de X e Y. Por lo tanto,${\displaystyle {\mathcal {D}}}$es un semirretículo de unión . La cota superior mínima de los grados a y b se denota como a ∪ b . Se sabe que${\displaystyle {\mathcal {D}}}$no es un retículo , ya que hay pares de grados sin límite inferior máximo.

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) al usar 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 la parada .

• Cada grado de Turing es infinitamente numerable , es decir, contiene exactamente${\displaystyle \aleph _{0}}$conjuntos.
• Hay${\displaystyle 2^{\aleph _ {0}}}$distintos grados de Turing.
• Para cada grado a se cumple la desigualdad estricta a < a ′ .
• Para cada grado a , el conjunto de grados menores que a es numerable . El conjunto de grados mayores que a tiene tamaño${\displaystyle 2^{\aleph _ {0}}}$.

Se han realizado numerosas investigaciones sobre la estructura de los grados de Turing. El siguiente resumen presenta solo algunos de los muchos resultados conocidos. Una conclusión general que se puede extraer de estas investigaciones es que la estructura de los grados de Turing es extremadamente compleja.

Un grado se denomina recursivamente enumerable (re) o computablemente enumerable (ce) si contiene un conjunto recursivamente enumerable . Todo grado re es menor que 0 ′ , pero no todo grado menor que 0 ′ es re. Sin embargo, un conjunto${\displaystyle A}$es reducible a 0 ′ muchos a uno si y solo si${\displaystyle A}$es re. ^{[ 3 ]}

• Sacks (1964) : Los grados re son densos; entre dos grados re cualesquiera hay un tercer grado re.
• 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 re distintos de cero cuyo límite inferior máximo es 0 .
• Lachlan (1966b) : No existe ningún par de grados re cuyo límite inferior máximo sea 0 y cuyo límite superior mínimo sea 0 ′ . Este resultado se conoce informalmente como el teorema no diamante .
• Thomason (1971) : Toda red distributiva finita puede incrustarse en los grados re. De hecho, el álgebra booleana numerable sin átomos puede incrustarse de manera que se preserven los supremos y los ínfimos .
• Lachlan y Soare (1980) : No todas las retículas finitas pueden incrustarse en los grados re (mediante una incrustación que preserve los supremos y los ínfimos). 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 lenguaje ⟨ 0 , ≤ , = ⟩ es equivalente en muchos a uno a la teoría de la verdadera aritmética de primer orden .

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

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

• 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 fusionando A con su función característica . (Eliminar esta condición produce una definición de A como "débilmente n -re" )
• A _s es un " predicado de n ensayos": para todo x , A ₀ ( x )=0 y la cardinalidad de${\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}$es ≤ n .

Propiedades de los grados n -re: ^{[ 4 ]}

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

Emil Post estudió los  grados de Turing re y se preguntó si existía algún grado re estrictamente entre 0 y 0 ′ . El problema de construir dicho grado (o demostrar que no existe) se conoció como el problema de Post . Este problema fue resuelto independientemente por Friedberg y Muchnik en la década de 1950, quienes demostraron que estos grados re intermedios sí existen ( teorema de Friedberg-Muchnik ). Sus demostraciones desarrollaron el mismo método para construir grados re, 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 conjuntos re.

La idea del método de prioridad para construir un re-conjunto X es enumerar una secuencia numerable de requisitos que X debe satisfacer. Por ejemplo, para construir un re-conjunto X entre 0 y 0 ′, basta con 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 ordenan por 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 pasos de tiempo durante los cuales se enumera el conjunto X. En cada etapa, se pueden agregar números a X o impedir permanentemente (si no están dañados) su entrada a X en un intento de satisfacer los requisitos (es decir, forzarlos a cumplirse una vez que se haya enumerado todo X ). A veces, se puede enumerar un número en X para satisfacer un requisito, pero esto provocaría que un requisito previamente satisfecho quedara insatisfecho (es decir, se viera afectado ). El orden de prioridad de los requisitos se utiliza para determinar cuál satisfacer en este caso. La idea informal es que si un requisito se ve afectado, eventualmente dejará de estarlo una vez que todos los requisitos de mayor prioridad hayan dejado de estarlo, aunque no todos los argumentos de prioridad poseen esta propiedad. Debe demostrarse que el conjunto X es re y satisface todos los requisitos. Los argumentos de prioridad pueden utilizarse para probar muchos hechos sobre los conjuntos re; los requisitos utilizados y la forma en que se satisfacen deben elegirse cuidadosamente para producir el resultado requerido.

Por ejemplo, un re simple (y por lo tanto no computable) bajo X (bajo significa X ′=0′) se puede construir en infinitas etapas como sigue. Al comienzo de la etapa n , sea T _n la cinta de salida (binaria), identificada con el conjunto de índices de celda donde colocamos 1 hasta ahora (de modo 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 hacer nada en la etapa), elegir el menor i < n tal que ∀ m P _n ( m )≠ i y la máquina de Turing i se detiene en < n pasos en alguna entrada S ⊇ T _n con ∀ m ∈ S \ T _n P _n ( m )≥ i . Elija cualquier S (finito) de este tipo , 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 a 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 detención; todas las prioridades son eventualmente constantes.

Para ver que X es bajo, la máquina i se detiene en X si y solo 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 recursión, esto es uniformemente computable desde 0′). X no es computable ya que de otro modo una máquina de Turing podría detenerse en Y si y solo si Y \ X no está vacío, lo que contradice la construcción ya que X excluye algunas celdas de prioridad i para i arbitrariamente grande ; y X es simple porque para cada i el número de celdas de prioridad i es finito.

• Martin mide