Puede alguien demostrar que había una paralización de oracle?

Question

Supongamos que alguien viene y dice tener una paralización de oracle. Hay alguna manera de comprobar la verdad o falsedad de sus afirmaciones en tiempo finito? Si es así, ¿qué restricciones en el proceso a prueba hay? Hace la verificación tiene que ser interactivo? Puede que sólo probar un probabilístico bound?

Actualización: Henning, a continuación, se sugiere un oracle $A_F$ que va a decir, "Detener" a menos que la TM en cuestión puede ser demostrado tener infinita de tiempo de ejecución por algún sistema formal $F$. Entonces él decía que uno no puede decirle a este oráculo de una verdadera paralización de oracle. No estoy seguro de esto; sospecho que hay alguna secuencia de preguntas que uno puede pedir de oracle este viaje en una mentira. ¿Alguien puede probar o refutar esta afirmación?

Answer 1

Está claro que no puedes esperar algo más que un resultado probabilístico -- cualquier procedimiento de prueba de que se puede pasar a una verdadera paralización de oracle después de preguntar es $n$ preguntas también pasar un azar de oracle con una probabilidad de al menos $2^{-n}$.

Pero tengo mucha duda de que usted puede conseguir incluso un probabilística de la garantía. Supongamos que, en el supuesto de oracle fue en realidad una prueba de búsqueda de oracle que responde correctamente cuando el programa puede ser demostrado (en algunos fijos, pero se desconoce sistema formal) para terminar o divergen, y si no las respuestas "se Detiene". En orden a la conclusión de que esto es no un verdadero detener oracle, tendríamos que preguntar acerca de algo que se aparta, pero unprovably así. Se puede pedir a la búsqueda de una prueba de un indecidible Gödel frase, pero desde el sistema formal de la falsa oracle utiliza es desconocido, sólo podría haber añadido un número finito de Gödel oraciones a su estática conocimiento.