6.4 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 diferencias importantes 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 propiedad realmente 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 reducibilidades intermedias, 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 no son 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 propio conjunto 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 de Turing. 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 (complementario de 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-hipersimples que 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 son T-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 que actualmente existen varioas
demostraciones diferentes, algunas de las cuales pueden considerarse la culminación del programa estructural de Post; pese a lo cual, los metodos de prioridad han de verse como el camino apropiado de solución.