Detalle de detención para las máquinas de Turing con una entrada

Question

Mi pregunta es:

¿Hay una construcción simple similar a la construcción del programa 'LIAR' de Turing que muestra que las máquinas de Turing más un oráculo de hallo no pueden decidir si una máquina de Turing se detiene en todas las entradas?

Cuando hablo sobre el programa LIAR, me refiero a la prueba estándar de que una máquina de Turing no puede determinar la detención de todas las demás máquinas de Turing, ya que el análisis de caso en los siguientes conduce a contradicciones

def Liar(T):
   if Halts('T(T)'):
      loop()
   else:
      return

Puedo ver que tener un oráculo de hallo, me permitiría determinar si una máquina de Turing se detiene en cualquier conjunto finito de insumos (simplemente lo ejecutaríamos todo en orden).

Si llamamos Máquinas de Turing Regular Nivel 0, podemos llamar a las máquinas de Turing más el nivel de ORÁCO DE HALTA 1. He visto que la prueba utilizando el programa LIAR funciona igual que para mostrar que las máquinas de nivel 1 tienen su propio problema de detención quees indecidible para ellos.

Answer 1

Lo que llame un programa "mentiroso" se denomina generalmente un argumento de diagonalización , ya que de alguna manera se parece al argumento de diagonalización del cantor.

Por lo general, lo que queremos decir, es que si intentamos enumerar todos los elementos con una determinada propiedad, entonces podemos señalar, por la construcción, un elemento que es necesariamente "incorrecto", y lo hacemos demostrando que lo hace. No satisface la propiedad con respecto a sí misma (esto es completamente ondulado, pero si ha visto el argumento, con suerte entenderá lo que quiero decir).

Ahora, lo que está preguntando es si podemos hacer lo mismo para demostrar que all_tm (TM universality) no es decidible por un TM con Oracle a HaltM_TM.

bien, no realmente. Al menos no de una manera natural: el argumento tendría que comenzar asumiendo que existe una máquina de oráculo M que decide all_tm, y luego construir desde m alguna otra máquina n (lo que llamas una máquina "mentirosa"), lo que produciría un contradicción cuando ejecutamos n en N. Sin embargo, la máquina N tendría que ser una máquina de oracle, no un TM estándar (o esencialmente perdería el poder del Oracle en M). Pero dado que el Oracle en N toma como TMS estándar de entrada, entonces el funcionamiento interno de N de alguna manera necesitaría crear un TM estándar para alimentar a Oracle. Esto no parece una construcción natural, y ciertamente no sería simple.

Ahora, quizás haya alguna forma complicada de dar un argumento directo de diagonalización para esta reclamación, pero no está bien motivado, dado que demostrar la demanda directamente (a saber, que all_tm no sea decidible por un TM con Oracle para detenerse) no es Difícil usar herramientas estándar, como reducciones.