¿Una máquina de Turing indecidible pero no universal?

Question

He visto muchos ejemplos de máquinas de Turing universales, todas ellas indecidibles debido a la indecidibilidad del problema de parada. También he visto pruebas de que ciertas máquinas de Turing realmente pequeñas son decidibles y, por tanto, no son universales. También he visto máquinas de Turing que hacen cálculos lo suficientemente simples como para no ser universales. Parece que todas las máquinas de Turing son lo suficientemente complejas para ser universales o lo suficientemente simples para ser decidibles.

Mi pregunta es si existe una máquina de Turing que viva en esta línea, es decir, que sea indecidible pero demostrablemente no universal. (Pregunta relacionada: ¿Cómo se podría demostrar que dicha máquina no es universal en esas condiciones?)

Answer 1

Se puede construir fácilmente una máquina de Turing M tal que $$M(x)=0 \mbox{ if } M_x(x) \mbox{ else do not halt} $$

No es universal, ya que siempre vuelve $0$ pero no puedes decidir si $M$ se detiene.

Para ejemplos más complejos que no utilicen ninguna máquina universal (aquí la utilizamos al simular $M_x(x)$ ), se necesitan muchos más conocimientos sobre los grados de Turing y El problema del puesto . La dificultad proviene del hecho de que la mayoría de las definiciones naturales de indecidible conducen a algo que es equivalente al problema de detención (y por lo tanto semidecidible) o más complejo (pero en una sola máquina, no se puede tener tal cosa).

Desde mi punto de vista, esto es una consecuencia informal de la Teorema de Rice . Por eso el problema del Correo era tan difícil de resolver y su prueba requiere algunas herramientas nuevas como el método de la prioridad.

Así que la respuesta es " Sí, hay ". Pero si realmente quieres entender en profundidad esa respuesta, tienes que aprender qué son el Grado de Turing, el problema de Post y su prueba.