salto de turing

En teoría de la computabilidad , el salto de Turing o 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 llama 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 de las máquinas Oracle con un oráculo para X. ^[1]

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

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

El ené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, cebado cero .

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

El salto se puede iterar en ordinales transfinitos : existen 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 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 continuar 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 incontables cardenales regulares . ^[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 la detención . ^[5]
• Para cada n , el conjunto 0 ^{( n )} es m-completo en el nivel de la jerarquía aritmética (según 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 computable enumerable perono X computable .
• Si A es equivalente de Turing a B , entonces A ′ es equivalente de Turing a B ′ . Lo contrario de esta implicación no es cierto.
• ( Shore y Slaman , 1999) La función que asigna X a X ′ se puede definir en el orden parcial de los grados de Turing. ^[5]

Muchas propiedades del operador de salto de Turing se analizan en el artículo sobre grados de Turing .

Referencias

1. Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Grados de insolvabilidad", Manual de historia de la lógica , Elsevier, vol. 9, 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 Kleene (Holanda Septentrional, 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". Revista de Lógica Simbólica . Asociación de Lógica Simbólica . 45 (2): 204–220. doi :10.2307/2273183. JSTOR  2273183. S2CID  41245500.
4. Lubarsky, Robert S. (diciembre de 1987). "Incontables códigos maestros y la jerarquía de salto". La revista de lógica simbólica . 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". Cartas de investigación matemática . 6 (6): 711–722. doi : 10.4310/MRL.1999.v6.n6.a10 .
6. Hodes, Harold T. (junio de 1980). "Saltar a través de lo transfinito: la jerarquía del código maestro de los grados de Turing". La revista de lógica simbólica . 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 . Berlina; Nueva York: Springer-Verlag . ISBN 3-540-12155-2.
• Lubarsky, Robert S. (diciembre de 1987). "Incontables códigos maestros y la jerarquía de salto". Revista de Lógica Simbólica . vol. 52, núm. 4. págs. 952–958. JSTOR  2273829.
• Rogers hijo, H. (1987). Teoría de funciones recursivas y computabilidad efectiva . MIT Press , Cambridge, MA, EE.UU. ISBN 0-07-053522-1.
• Costa, RA; Slaman, TA (1999). "Definiendo el salto de Turing" (PDF) . Cartas de investigación matemática . 6 (5–6): 711–722. doi : 10.4310/mrl.1999.v6.n6.a10 . Consultado el 13 de julio de 2008 .
• Soare, Rhode Island (1987). Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente . Saltador. ISBN 3-540-15299-7.