La madre de todos los problemas indecidibles

Question

Es habitual demostrar que un problema P es indecidible demostrando que el problema de detención se reduce a P .

¿Es el caso de que el problema de detención ¿es la madre de todos los problemas indecidibles en el sentido de que se reduce a cualquier problema indecidible? Si la respuesta es negativa, ¿puede mostrar un contraejemplo (preferiblemente sencillo), es decir, un problema indecidible al que el problema de parada no se reduzca?

Answer 1

Una forma de demostrarlo es probando que el conjunto de reales que calculan el problema de detención tiene medida cero y es de primera categoría (unión contable de conjuntos densos de ninguna parte). La existencia de reales que no calculan el problema de detención se deduce.

Answer 2

Si entiendo bien la pregunta, es : "¿es el problema de detención el más simple de todos los problemas indecidibles, en el sentido de que el conocimiento de cualquier otro problema indecidible sería suficiente para resolver el problema de detención?".

Yo diría que la respuesta es a la vez no y tal vez. Es no en el sentido de que hay conjuntos indecidibles que no pueden calcular el problema de detención. "almostall" propuso un bonito argumento no constructivo para ello. También es posible construir tales conjuntos. En particular, hay conjuntos computables no decidibles (entonces decidibles por el problema de detención) pero que no pueden decidir el problema de detención (buscar "Post problem" y "priority method" en google).

Ahora, para el "tal vez", es cierto que no hay ningún ejemplo natural de tales problemas, y se ha intentado formalizar matemáticamente lo que es un "ejemplo natural", para demostrar que el problema de halting es el único. Cito aquí una parte de "There is no degree invariant half-jump" de Rod Downey, que destaca este fenómeno:

Un fenómeno sorprendente en los primeros días de la teoría de la computabilidad fue que todos los problemas de decisión para las teorías axiomatizables resultaron decidible o del mismo grado de Turing que el problema de detención problema de detención $\emptyset'$ el conjunto completo computablemente enumerable). Quizás el problema más influyente en la teoría de la computabilidad en los últimos cincuenta años ha sido el problema de Post de encontrar una excepción a esta regla, es decir, un grado incompleto computable no computable grado. El problema se ha resuelto muchas veces en varios escenarios y disfraces, pero las soluciones siempre implican construcciones específicas de conjuntos extraños, generalmente por el método de prioridad que se desarrolló por primera vez (Friedberg y Muchnik) para resolver este problema. No hay problemas problemas de decisión naturales o conjuntos de cualquier tipo que no sean computables ni completos. La cuestión es entonces cómo definir lo que caracteriza a los grados naturales computables y demostrar que ninguno de ellos puede proporcionar una solución al problema de Post.

Puede que nos lleve demasiado lejos ahora continuar con lo que es la formalización matemática de la cuestión de la existencia de un "ejemplo natural" de problemas indecidibles, además, no soy un especialista en esto de todos modos. Pero si quieres investigar un poco, tal vez puedas buscar la pregunta de Sacks: "¿Existe una solución invariante de grado para el problema de Correos?", que por lo que sé sigue abierta, al menos en su forma general.