¿Hay algún problema existente que no se pueda resolver con un oráculo de detención?

11

Entiendo que la mayoría de los problemas son triviales si hay un oráculo de detención disponible (o, creo, equivalentemente, hipercomputación). Sin embargo, aplicar el argumento que muestra que el problema de detención es imposible para una máquina de Turing también muestra que es imposible que un oráculo de Turing + decida el problema de detención para un oráculo de Turing +. ¿Hay ejemplos reales y prácticos de problemas que no se puedan resolver con un oráculo de detención?

Nota: por "oráculo" me refiero a oráculo para una máquina Turing estándar, no a un TM con un oráculo en sí.

ike
fuente
2
No son problemas "arbitrariamente" indecidibles, véase por ejemplo aquí . No conozco ejemplos "prácticos" (que tampoco coinciden con el título que elegiste); ¿Qué califica como "práctico" para usted?
Raphael
Eso no está diseñado simplemente para responder esta pregunta. Reconocí que el problema de detención del siguiente nivel todavía se aplica.
ike
Además, todos los idiomas que no son recursivamente enumerables no se pueden reducir a HALT. Los ejemplos incluyen FINITO, VACÍO, si dos CFG derivan el mismo idioma, etc.

Respuestas:

15

Simplemente tome un problema cuyo grado de Turing está por encima de , que es el grado de The Halting Oracle. En términos de la jerarquía aritmética , desea problemas que estén por encima de . Ejemplos de tales problemas (donde es la -ésima función computable parcial y es el - th conjunto computablemente enumerable):0Σ10ϕnnWn={kNϕn(k) is defined}n

  • {nNφn terminates for finitely many inputs} es -complete.Σ20
  • {nNφn is a total function} es -completo.Π20
  • {nNWn is a computable set} es -completo.Σ30

Ninguno de estos puede resolverse incluso si tiene un Oracle detenido. Por ejemplo, considere el segundo ejemplo, "¿es total?" Dado ¿cómo nos ayudaría el Halting Oracle a decidir si la máquina de Turing codificada por detiene en cada entrada? n nφnnn


[Agregado 2014-06-03] Para un aspecto "práctico" de todo esto, considere el problema: un programador ha escrito una función void charge_credit_card(int card_number, int amount)y nos gustaría saber si la función termina en todas las entradas. Es imposible escribir un compilador que pueda verificar automáticamente esto en general. Además, incluso si permitimos que el compilador nos haga preguntas de la forma "¿ charge_credit_cardtermina cuando se le da entrada (k,m)?", Todavía es imposible.

Andrej Bauer
fuente
2
Decir "No entiendo el ejemplo" sin explicar lo que te confunde no es productivo. ¿Leíste las páginas relevantes de Wikipedia que señalé? Esos están directamente relacionados con su pregunta, por lo que lo primero que debe hacer es familiarizarse con los conceptos básicos involucrados.
Andrej Bauer
1
@ike, el ejemplo estaba destinado a tener una cantidad infinita de int, obviamente. ¿Realmente necesita que escriba BigInto algo así, o se quejará de que la memoria de la computadora es finita?
Andrej Bauer
1
Lo que sea. Te dije cuál era la respuesta a tu pregunta. Si no quiere entenderlo de buena fe, no nos moleste con preguntas.
Andrej Bauer
2
HALT¯{<M,w>:M doesn't halt on w}
1
@ tAllan: debe publicar eso como respuesta. Me gana lo que el OP considera "práctico", pero su ejemplo es ciertamente mejor que el mío.
Andrej Bauer