En la teoría de la computabilidad , el salto de Turing o el 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 X ′ sucesivamente más difícil con la propiedad de que X ′ no es decidible por una máquina de oráculo con un oráculo. para X .
El operador se llama un operador de salto , ya que aumenta el grado de Turing del problema X . Es decir, el problema X ' no es Turing reducible 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 X puede ser pensado como un oráculo para el problema de la parada de máquina 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 funciones computables de X , el salto de Turing X ′ de X se define como
El n- ésimo salto de Turing X ( n ) se define inductivamente por
El ω salto X (ω) de X es la unión efectiva de la secuencia de conjuntos X ( n ) para n ∈ N :
donde p i denota el i- ésimo primo.
La notación 0 ′ o ∅ ′ se usa a menudo para el salto de Turing del conjunto vacío. Se lee zero-jump o, a veces, zero-prime .
De manera similar, 0 ( n ) es el n- ésimo salto del conjunto vacío. Para n finito , estos conjuntos están estrechamente relacionados con la jerarquía aritmética .
El salto se puede iterar en ordinales transfinitos : los conjuntos 0 (α) para α <ω 1 CK , donde ω 1 CK es el ordinal de Church-Kleene , están estrechamente relacionados con la jerarquía hiperaritmética . [1] Más allá de ω 1 CK , el proceso puede continuar a través de los ordinales contables del universo construible , utilizando métodos de teoría de conjuntos (Hodes 1980). El concepto también se ha generalizado para extenderse a incontables cardenales regulares (Lubarsky 1987). [2]
Ejemplos de
- El salto de Turing 0 ′ del conjunto vacío es el equivalente de Turing al problema de la detención . [3]
- Para cada n , el conjunto 0 ( n ) es m-completo en el nivelen la jerarquía aritmética (por el teorema de Post ).
- 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 se puede calcular a partir de X (ω) . [4]
Propiedades
- X ′ es X - computablemente enumerable pero no X - computable .
- Si A es Turing-equivalente a B , entonces A ′ es Turing-equivalente 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. [3]
Muchas propiedades del operador de salto de Turing se analizan en el artículo sobre grados de Turing .
Referencias
- ^ a b c Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Degrees of Unsolvability", Handbook of the History of Logic , Elsevier, 9 , págs. 443–494, doi : 10.1016 / b978-0-444-51624-4.50010-1 , ISBN 9780444516244.
- ^ Lubarsky, Robert S. (diciembre de 1987). "Códigos maestros incontables y la jerarquía de salto". El diario de la lógica simbólica . 52 (4): 952–958. doi : 10.2307 / 2273829 . ISSN 0022-4812 . JSTOR 2273829 .
- ^ a b 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 .
- ^ 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". El diario de la lógica simbólica . 45 (2): 204–220. doi : 10.2307 / 2273183 . ISSN 0022-4812 . JSTOR 2273183 .
- Ambos-Spies, K. y Fejer, P. Grados de insolubilidad. Inédito. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
- 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". Revista de lógica simbólica . Asociación de Lógica Simbólica . 45 (2): 204–220. doi : 10.2307 / 2273183 . JSTOR 2273183 .
- 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). "Códigos maestros incontables y la jerarquía de salto". Revista de lógica simbólica . 52 (4). págs. 952–958. JSTOR 2273829 .
- Rogers Jr, H. (1987). Teoría de funciones recursivas y computabilidad efectiva . MIT Press , Cambridge, MA, Estados Unidos. ISBN 0-07-053522-1.
- Shore, RA; Slaman, TA (1999). "Definición del 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 . CS1 maint: parámetro desalentado ( enlace )
- Soare, RI (1987). Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente . Saltador. ISBN 3-540-15299-7.