halting problem - parada - ¿Cómo funciona esta prueba de que el problema de la detención es indecidible?

problema de la parada ejemplos

Question

Estoy revisando la prueba del problema de detención en introducción a la teoría de la computación de Sipser y mi principal preocupación es la siguiente prueba:

Si TM M no sabe cuándo está en bucle (no puede aceptar o rechazar, por lo que una TM es Turing Recognizable para todas las cadenas), ¿cómo podría decidir la decisión H si M podría estar en un bucle? El mismo problema continuará cuando TM D realice su procesamiento.

Answer 1

Después de leer esto e intentar visualizar la prueba, se me ocurrió este código, que es una versión simplificada del código en esta respuesta a una pregunta relacionada:

function halts(func) {
  // Insert code here that returns "true" if "func" halts and "false" otherwise.
}

function deceiver() {
  if(halts(deceiver))
    while(true) { }
}

Si halts(deceiver) devuelve true , el deceiver se ejecutará para siempre, y si devuelve false , el deceiver se detendrá, lo que contradice la definición de halts . Por lo tanto, la función se halts es imposible.

Answer 2

Esta es una "prueba por contradicción", una reductio ad absurdum . (Las frases en latín siempre son buenas en las clases de teoría ... siempre que tengan sentido, por supuesto).

Este programa H es solo un programa con dos entradas: una cadena que representa un programa para alguna máquina y una entrada. A los fines de la prueba, simplemente asume que el programa H es correcto: simplemente se detendrá y aceptará si M acepta con w . No necesitas pensar en cómo haría eso; de hecho, estamos a punto de demostrar que no se puede, que no existe tal programa H , ...

PORQUE

si tal programa existiera, podríamos construir inmediatamente otro programa H '' que H no pudiera decidir. Pero, por supuesto, no existe tal programa: H puede decidir todo. Por lo tanto, nos vemos obligados a concluir que ningún programa definido como definimos H es posible.

Por cierto, el método de reducción de la prueba es más controvertido de lo que podría esperarse, considerando la frecuencia con que se utiliza, especialmente en informática. No deberías avergonzarte de encontrarlo un poco extraño. El término mágico es "no constructivo" y si te sientes realmente ambicioso, pregunta a uno de tus profesores acerca de la crítica de Errett Bishop a las matemáticas no constructivas.