Máquina de Turing universal con un oráculo

Question

(Nota: Por comodidad, estoy expresando esto en términos de programas de ordenador en lugar de máquinas de Turing). Consideremos un programa de ordenador P que hace lo siguiente:

1. Pide al usuario que introduzca el código de un programa informático

2. Consulta un oráculo para saber si hay alguna posibilidad de que no se detenga si ejecuta el programa informático en cuestión.

3. Si el oráculo le dice que no puede detenerse si ejecuta el programa, entonces da la salida "ERROR" y se detiene.

4. Si el oráculo le dice que está garantizado que se detenga si ejecuta el programa, entonces ejecuta el programa.

Ahora la pregunta es, ¿está garantizado que P se detenga? Supongamos que está garantizado que se detenga, y dejemos que el código para P sea c. Entonces el usuario puede ejecutar P, y cuando se le pida puede introducir c, y entonces P se ejecutará de nuevo, y cuando se le pida el usuario puede introducir de nuevo c, y entonces P se ejecutará de nuevo, y el usuario puede introducir c, etc. Así que no se garantiza que P se detenga.

Pero si no se garantiza que P se detenga, entonces si el usuario ingresa c, P simplemente emitirá "ERROR" y luego se detendrá. Por lo tanto, se garantiza que P se detenga. Entonces, ¿qué está pasando?

Cualquier ayuda será muy apreciada.

Gracias por adelantado.

Answer 1

Creo que el problema aquí es un poco diferente: su "oráculo" es demasiado poderoso. Creo que los modelos computacionales válidos tienen oráculos bien fundados, en cierto sentido: un oráculo no puede predecir su propio comportamiento.

Editar: El problema de la interrupción se aplica también a los oráculos. Supongamos que tenemos una máquina de oráculo (una máquina de Turing conectada a un oráculo de alguna manera) que toma como entrada una descripción de una máquina de Turing diseñada para ser conectada al mismo oráculo y determina si esa máquina, conectada a ese oráculo, se detendría. Proceda de la misma manera que la prueba habitual del problema de detención para demostrar una contradicción.

Answer 2

Creo que P está garantizado para detener en cualquier finito que es donde tu prueba de que esto es imposible se rompe, ya que le das a P una entrada infinita.

Sería imposible garantizar que P se detenga con cualquier entrada, ya que si su entrada es infinitamente larga, incluso si P no hace nada más que leer la entrada y pasarla al oráculo, no se detendrá.

Edición: Aunque creo que lo anterior es correcto cuando el oráculo no puede actuar sobre sí mismo, la cuestión más importante aquí es que este oráculo no puede existir si se espera que funcione en los programas que se usan a sí mismos.