Reducibilidad de turing

REDUCIBILIDAD DE TURING
Post propuso un camino para obtener un conjunto no completo para la reductibidad de Turing, definiendo y estudiando reducibilidades intermedias. Así, las diferenciasimportantes entre la reducción M y la de Turing son
obviamente el poder efectuar mas de una pregunta, y en segundo lugar el poder “hacer lo contrario” de lo que indica la respuesta; pero la propiedadrealmente relevante resulta ser un poder que cada pregunta dependa
esencialmete de las respuestas obtenidas a preguntas anteriores 
(“adaptabilidad” de la reducción). Es posible definir reducibilidadesintermedias, entre ellas las reducciones por la tabla de variedad, que no son adaptativas.

Y, en efecto, una versión reforzada de los conjuntos simples, los hipersimples, proporciona conjuntos que noson completos respecto de la reductibilidad por tablas de verdad. Post demostró este hecho, y construyo un conjunto hipersimple; nosotros lo tenemos facil por que, de hecho, ya lño tenemos: el propioconjunto SK no solo es simple si no hipersimple.

Asimismo, propuso un concepto de hiper-hipersimple, y demostró que existen, en la esperanza de que no fueran completos respecto reducciones deTuring. La idea era procurar que los complementarios fueran “lo mas delgados
posible” en cierto sentido intuitivo: en un inmune “no cabe” un recursivamente enumerable y en un hiperinmune (complementariode un hipersimple) “el siguiente elemento esta siempre demasiado lejos” para lo que puede
lograr enumerar una función recursiva. Sin embargo mas adelante se estableció que existen hiper-hipersimplesque son T-completos e incluso que existen recursivamente numerables maximales respecto a la inclusión, y por
tanto con complementario “lo mas delgado posible” en este sentido intuitivo, y que sonT-completos.

La solucion finalmente requirió un concepto tecnico nuevo, las construcciones por metodos de prioridad, que extendieron otra de las varias contribuciones de Post. Merece la pena comentar...