Baja (computabilidad)
En la teoría de la 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 limitar cualquier grado re en 0 ′ (Inversión de salto de Schoenfield). X siendo bajo dice que su salto X ′ tiene el menor grado posible en términos de reducibilidad de Turing para el salto de un conjunto.
Un grado es bajo n si su n- ésimo salto es el n-ésimo salto de 0. Un conjunto X se generaliza bajo si satisface X ′ ≡ T X + 0 ′, es decir: si su salto tiene el menor grado posible. Y un grado d se generaliza bajo n si su n-ésimo salto es el (n-1) 'st salto de la unión de d con 0 ′. De manera más general, las propiedades de los conjuntos que describen que son computacionalmente débiles (cuando se usan como un oráculo de Turing) se denominan bajo el término general propiedades de bajeza .
Según el teorema de base baja de Jockusch y Soare, cualquier clase no vacía de contiene un conjunto de grado bajo. Esto implica que, aunque los conjuntos bajos son computacionalmente débiles, aún pueden lograr hazañas como calcular una finalización de la aritmética de Peano . En la práctica, esto permite una restricción en el poder computacional de los objetos necesarios para las construcciones teóricas de recursividad: por ejemplo, los usados en el análisis de la fuerza de la teoría de la prueba del teorema de Ramsey .
