Salto de Turing

En teoría de computabilidad , el salto de Turing u operador de salto de Turing , llamado así por Alan Turing , es una operación que asigna a cada problema de decisión X un problema de decisión sucesivamente más difícil X ′ con la propiedad de que X ′ no es decidible por una máquina oráculo con un oráculo para X.

El operador se denomina operador de salto porque aumenta el grado de Turing del problema X . Es decir, el problema X ′ no es reducible por Turing a X . El teorema de Post establece una relación entre el operador de salto de Turing y la jerarquía aritmética de conjuntos de números naturales. ^[1] De manera informal, dado un problema, el salto de Turing devuelve el conjunto de máquinas de Turing que se detienen cuando se les da acceso a un oráculo que resuelve ese problema.

Definición

El salto de Turing de X puede considerarse como un oráculo para el problema de detención para máquinas oráculo con un oráculo para X. ^[1]

Formalmente, dado un conjunto X y una numeración de Gödel φ _i ^X de las X funciones computables , el salto de Turing X ′ de X se define como

${\displaystyle X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{is defined}}\}.}$

El n -ésimo salto de Turing X ^{( n )} se define inductivamente por

${\displaystyle X^{(0)}=X,}$

${\displaystyle X^{(n+1)}=(X^{(n)})'.}$

El salto ω X ^(ω) de X es la unión efectiva de la secuencia de conjuntos X ^{( n )} para n ∈ N :

${\displaystyle X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathbb {N} {\text{ and }}k\in X^{(i)}\},}$

donde p _i denota el i- ésimo primo.

La notación 0′ o ∅′ se utiliza a menudo para el salto de Turing del conjunto vacío. Se lee salto-cero o, a veces, primo-cero .

De manera similar, 0 ^{( n )} es el salto n- ésimo del conjunto vacío. Para n finitos , estos conjuntos están estrechamente relacionados con la jerarquía aritmética , ^[2] y están conectados en particular con el teorema de Post .

El salto se puede iterar en ordinales transfinitos : hay operadores de salto para conjuntos de números naturales cuando es un ordinal que tiene un código en Kleene (independientemente del código, los saltos resultantes son los mismos por un teorema de Spector), ^[2] en particular los conjuntos 0 ^(α) para α < ω ₁ ^CK , donde ω ₁ ^CK es el ordinal de Church–Kleene , están estrechamente relacionados con la jerarquía hiperaritmética . ^[1] Más allá de ω ₁ ^CK , el proceso puede continuarse a través de los ordinales contables del universo construible , utilizando el trabajo de Jensen sobre la teoría de la estructura fina de la L de Gödel . ^{[3] [2]} El concepto también se ha generalizado para extenderse a cardinales regulares incontables . ^[4] ${\displaystyle j^{\delta }}$ ${\displaystyle \delta }$ ${\displaystyle {\mathcal {O}}}$

Ejemplos

• El salto de Turing 0′ del conjunto vacío es el equivalente de Turing al problema de detención . ^[5]
• Para cada n , el conjunto 0 ^{( n )} es m-completo en el nivel de la jerarquía aritmética (por el teorema de Post ). ${\displaystyle \Sigma _{n}^{0}}$
• El conjunto de números de Gödel de fórmulas verdaderas en el lenguaje de la aritmética de Peano con un predicado para X es computable a partir de X ^(ω) . ^[6]

Propiedades

• X ′ es X - computablemente enumerable pero no X - computable .
• Si A es Turing-equivalente a B , entonces A ′ es Turing-equivalente a B ′ . La inversa de esta implicación no es verdadera.
• ( Shore y Slaman , 1999) La función que asigna X a X ′ es definible en el orden parcial de los grados de Turing. ^[5]

En el artículo sobre grados de Turing se analizan muchas propiedades del operador de salto de Turing .

Referencias

1. Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Grados de insolubilidad", Manual de la historia de la lógica , vol. 9, Elsevier, págs. 443–494, doi :10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.
2. SG Simpson, La jerarquía basada en el operador de salto, p. 269. El simposio de Kleene (Holanda del Norte, 1980)
3. Hodes, Harold T. (junio de 1980). "Saltando a través del transfinito: la jerarquía del código maestro de los grados de Turing". Journal of Symbolic Logic . 45 (2). Association for Symbolic Logic : 204–220. doi :10.2307/2273183. JSTOR  2273183. S2CID  41245500.
4. Lubarsky, Robert S. (diciembre de 1987). "Códigos maestros incontables y la jerarquía de saltos". The Journal of Symbolic Logic . 52 (4): 952–958. doi :10.2307/2273829. ISSN  0022-4812. JSTOR  2273829. S2CID  46113113.
5. Shore, 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 .
6. Hodes, Harold T. (junio de 1980). "Saltando a través del transfinito: la jerarquía del código maestro de los grados de Turing". The Journal of Symbolic Logic . 45 (2): 204–220. doi :10.2307/2273183. ISSN  0022-4812. JSTOR  2273183. S2CID  41245500.

• Ambos-Spies, K. y Fejer, P. Grados de insolubilidad. Inédito. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. (1983). Grados de insolubilidad: teoría local y global . Berlín; Nueva York: Springer-Verlag . ISBN. 3-540-12155-2.
• Lubarsky, Robert S. (diciembre de 1987). "Códigos maestros incontables y la jerarquía de saltos". Journal of Symbolic Logic . Vol. 52, núm. 4. págs. 952–958. JSTOR  2273829.
• Rogers Jr, H. (1987). Teoría de funciones recursivas y computabilidad efectiva . MIT Press , Cambridge, MA, EE. UU. ISBN 0-07-053522-1.
• Shore, RA; Slaman, TA (1999). "Definición del salto de Turing" (PDF) . Mathematical Research Letters . 6 (5–6): 711–722. doi : 10.4310/mrl.1999.v6.n6.a10 . Consultado el 13 de julio de 2008 .
• Soare, RI (1987). Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computacionalmente . Springer. ISBN 3-540-15299-7.