Hispanopedia WikiEn teoría de computabilidad , un grado de Turing [ X ] es bajo si el salto de Turing [ X ′] es 0′. Un conjunto es bajo si tiene un grado bajo. Dado que cada conjunto es computable a partir de su salto, cualquier conjunto bajo es computable en 0′, pero el salto de conjuntos computables en 0′ puede acotar cualquier grado recursivamente enumerable en 0′ (Inversión de salto de Schoenfield). El hecho de que X sea bajo indica que su salto X ′ tiene el menor grado posible en términos de reducibilidad de Turing para el salto de un conjunto.
Existen varias propiedades relacionadas con grados bajos:
- Un grado es n bajo si su salto n-ésimo es el salto n-ésimo de 0. [1] [2]
- Un conjunto X es generalizado bajo si satisface X ′ ≡ TX + 0′, es decir: si su salto tiene el menor grado posible.
- Un grado d es n bajo generalizado si su n'ésimo salto es el (n-1)'ésimo salto de la unión de d con 0'.
De manera más general, las propiedades de los conjuntos que describen su debilidad computacional (cuando se utilizan como un oráculo de Turing) se conocen bajo el término general de propiedades de baja densidad .
Según el teorema de base baja de Jockusch y Soare, cualquier clase no vacía en contiene un conjunto de grado bajo. Esto implica que, aunque los conjuntos bajos son computacionalmente débiles, aún pueden lograr hazañas tales como calcular una completitud de la Aritmética de Peano . En la práctica, esto permite una restricción en la potencia computacional de los objetos necesarios para las construcciones teóricas de recursión: por ejemplo, aquellos utilizados en el análisis de la fuerza teórica de la prueba del teorema de Ramsey .
Véase también
Referencias
- ^ R. Downey, RA Shore, Definiciones teóricas de grado de los conjuntos recursivamente enumerables Low2. The Journal of Symbolic Logic, vol. 60, n.º 3 (septiembre de 1995), pág. 728
- ^ CJ Ash, J. Knight, Estructuras computables y la jerarquía hiperaritmética (Estudios en lógica y fundamentos de las matemáticas, 2000), pág. 22
- Soare, Robert I. (1987). Conjuntos y grados enumerables recursivamente. Un estudio de funciones computables y conjuntos generados computacionalmente . Perspectivas en lógica matemática. Berlín: Springer-Verlag . ISBN. 3-540-15299-7.Zbl 0667.03030 .
- Nies, André (2009). Computabilidad y aleatoriedad . Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1.Zbl 1169.03034 .