Entender por qué el problema de Halting puede ' resolver t

Question

Entiendo que este hilo puede ser similar a uno de mis viejos hilos pero no es el mismo desde ahora voy a aportar mi visión sobre lo que yo entiendo.

Entiendo lo de la suspensión problema, dice, pero no puedo entender por qué no puede ser resuelto. Mi profesor utiliza una diagonalización argumento de que estoy a punto de explicar.

La cardinalidad del conjunto de máquinas de turing es contable, por lo que cualquier máquina de turing puede ser representado como una cadena. Él puso sobre la mesa un gráfico con dos ejes. Una de las máquinas de turing y una de sus entradas, que son cadenas de texto que describe una máquina de turing y su acuerdo de entrada y, a continuación, comenzó a llenar la red con Aceptar o rechazar o bucle para siempre. Entonces él sacó una diagonal a lo largo de esa red y crea una nueva máquina de turing con los valores en la diagonal. Entiendo que estamos tratando de demostrar que la lengua es indecidible. ¿Por qué es esta máquina de turing que no es en el primer gráfico importante? y ¿cómo se lleva esto a la conclusión de que la detención problema no puede ser resuelto?. Entiendo por qué los números reales son innumerables, por lo que no hay necesidad de explicar eso.

Necesito entender la prueba de por qué la detención problema no puede ser resuelto con el argumento de diagonalización.

Answer 1

No tiene que ver con la uncountability de los números reales, a pesar de que el argumento es similar.

Basado en su más reciente edición, en respuesta a los comentarios, parece que usted no desea que la tradicional prueba, desea que la prueba de su profesor estaba proporcionando. Lo que su profesor estaba haciendo no es de ninguna manera estándar, por lo que sólo podemos adivinar; pero aquí es lo que creo que el argumento era.

Las máquinas de Turing no sólo contables, pueden ser enumerados por una máquina de Turing. Así que tenemos un algoritmo que nos permite una lista de las máquinas de Turing, en fin. Supongamos que tenemos un algoritmo, $H$, lo que nos diría si una máquina de Turing se detendría en una entrada determinada. Ahora la construcción de un nuevo algoritmo, $T$, de la siguiente manera: para determinar el $T(n)$, nos fijamos en la $n$th máquina de Turing, y pedir a $H$ si se detiene en la entrada de $n$. Si no es así, podemos decir $T(n) = 0$. Si no, corremos ese $n$th máquina de Turing en la entrada de $n$, y, finalmente, obtener un resultado; deje $T(n)$ ser que el resultado más uno.

Ahora, $T$ es un algoritmo, por lo que es representado por una máquina de Turing. Pero todas las máquinas de Turing estaban en nuestra lista, por lo $T$ está en nuestra lista. Dicen que es el $N$th máquina de Turing en nuestra lista. Lo $T(N)$? Si $T$ no paro de entrada de $N$, luego en el $N$th paso de nuestra construcción decidimos que $T(N) = 0$, lo $T$ hace parada en la entrada de $N$, una contradicción. Si $T(N) = k$ algunos $k$, entonces decidimos que $T(N) = k + 1$, otra contradicción. Pero esas eran las únicas opciones - o $T(N)$ no detener, o eventualmente salidas de algunos $k$. Así que esto contradice la suposición de que la $T$ es en realidad una máquina de Turing, lo que significa que el elemento clave - la detención algoritmo de $H$ - no debe existir.

Answer 2

Reese hizo un muy buen trabajo de explicar cómo una prueba de la undecidability de la detención de un problema que puede ser escrito de una manera que explícitamente hace uso de diagonalización. Voy a ofrecer una informal brillo.

Diagonalización se emplea para llegar a una contradicción que nos obliga a abandonar una suposición. Aquí el supuesto es la existencia de una TM (vamos a llamar a $H$) el que decide la suspensión problema.

Diagonalización es aplicado por la construcción de una tabla de $A$ que $A_{i,j}$ dice que si el $i$-th TM se detiene en la entrada de $j$. Se dice entonces, "Vamos a construir un TM que en la entrada de $i$ hace lo contrario de TM $i$."

Ahora la pregunta es, "¿tal una máquina de Turing existe?" No es difícil ver que, dada $H$, se puede construir el deseado TM; pero luego esta el TM no está en la tabla, debido a que fue construido por diagonalización y sin embargo la tabla enumera todos los TMs (TMs pueden ser enumeradas) ... Contradicción!

La única suposición que podemos dar es la existencia de la TM $H$ que decide la suspensión problema, que es lo que queremos hacer, así que no estamos obligados a admitir que hay un TM que no está de acuerdo con TM $i$ en la entrada de $i$ todos los $i$.

¿Cómo podemos construir la "diagonal TM" dado $H$? Tal como se ha explicado en la "otra" prueba: duplicar la entrada, vamos a $H$ decidir si la entrada de TM se detiene cuando se lee a sí mismo, y luego hacer lo contrario de lo $H$ dijo. Este último paso es de diagonalización.

Answer 3

Personalmente, cuando me enteré del problema de la parada, me gusta pensar de la máquina conduce a contradicción como el siguiente programa en C concreto:

#include <stdio.h>
#include <stdbool.h>

/* If we assume the existence of a halting machine 'does_it_halt'.  */
bool
does_it_halt(void *turing_machine, void *input);

/* Then we can build the following machine 'absurd'.  */
void
absurd(void *input)
{
  if (does_it_halt(input, input))
    {
      while (true) {/* infinite loop  */}
    }
  else
    {
      return;
    }
}

/* Now if we run the machine 'absurd' with itself as input, does it halt?  */
int
main(void)
{
  absurd(absurd);
  return 0;
}

Answer 4

Cómo hacer pruebas de diagonalización de trabajo?

¿Por qué es esta máquina de turing, que no es en el primer gráfico, importante?

1. Proponer una declaración como "existe un TM, que resuelve la suspensión problema" o "los reales entre 0 y 1 son contables", que vamos a desmentir.
2. La construcción de un camino para enumerar (contar) con todos los elementos que forman parte de la tesis (aquí: Máquinas de Turing o reales). Los elementos (TMs, reales, ...) deberán consistir de sub-elementos (por ejemplo, símbolos de la Emt, los dígitos de reales), así que podemos hacer una tabla correcto. No importa que la tabla tiene una infinidad de columnas y filas. Hacer esta construcción es tan fácil/trivial como sea posible, para puntos de bonificación. Bastante fácil para TMs y reales.
3. Encontrar un camino a través de la enumeración que llega a cada célula. Aquí es donde la diagonalización; se asegura de que, a diferencia de uno de los ejes hasta el infinito, cada una de las células que se alcanza en una cantidad finita de pasos.
4. La construcción de un nuevo elemento de este tutorial en el que se garantiza que no sea una parte de la tabla original. Sí, acaba de sumar 1 a cada dígito que encuentro (envolver). Para TMs, hacer lo que el profesor hizo. Como hemos construido la tabla de modo que contenía todos los elementos, tenemos una contradicción, ya que este nuevo elemento es, obviamente, que no figuran en la tabla (que es diferente de cada elemento que nos encontramos es nuevo).

El paso 4 es la respuesta a tu pregunta:

Todo nuestro esfuerzo fue hecho exclusivamente para la construcción de una Máquina de Turing que no es un miembro del conjunto de todas las Máquinas de Turing. Esto nos da una contradicción. Hemos construido cuidadosamente nuestro pequeño algoritmo para que cada paso es muy sencillo y, obviamente, (o, si así lo desea, de modo demostrable) correcta, así que la única parte de todo nuestro diagonalización argumento de que es negociable es la conjetura. Por lo tanto la conjetura debe ser falsa.

Addendum, cómo aplicar para Máquinas de Turing

Para aplicar el método de diagonalización para Máquinas de Turing y de la suspensión problema:

• Como se indicó anteriormente, suponemos que existe una máquina de turing H(h,i) que toma dos parámetros (otra TM y arbitraria de entrada) y decide si esa otra TM va a detener para dicha entrada, o no. Esta es la definición de la detención problema.
• Tenga en cuenta que el conjunto de posibles entradas (en el dominio i) es, de nuevo, el conjunto de todas las máquinas de turing (codificado en algunos representación textual)! Este es lo suficientemente pequeño. Este es un enfoque similar a decir que sí, es suficiente para mirar en el intervalo [0;1], en lugar de todos los números, para hacer la prueba más simple. Nos muestran que la detención problema no puede ser resuelto por este subconjunto de posibles máquinas; es decir, máquinas que trabajan en el "código fuente" de las máquinas.
• En la mencionada tabla se enumeran las máquinas en uno de los ejes, y las entradas en el otro. Cada célula (pensar en Excel) es el resultado de la ejecución de nuestra supuesta máquina en la que de entrada específico. Los pasos 2 y 3 son por lo tanto mecánicamente a cabo y la necesidad de ningún conocimiento en absoluto acerca de las Máquinas de Turing.
• En el paso 4, se construye una nueva máquina de turing H' por ir en diagonal a través de la mesa y haciendo que la nueva máquina de H', por lo que se detiene si la celda contiene FALSA, y no se puede detener si la celda contiene CIERTO. Esto es muy fácil de hacer ya que H' puede contener H como una subrutina y pedir que uno, a continuación, salir o entrar en un bucle infinito (que es fácil de programar).
• Como con los reales, ahora hemos creado una nueva entrada para nuestra mesa que, por el mero definición difiere de todos los otros de la entrada. q.e.d.

Answer 5

No puedo dar la prueba exacta de su profesor le dio. Sin embargo, aquí es una manera muy sencilla, puede ser pensado como una paradoja.

Leve nota: voy a anotar las máquinas de torneado como funciones por simple conveniencia de la redacción. Pido disculpas si hay una manera más sencilla para referirse a ellos.

Supongamos que tenemos una máquina de turing $E$ que se lleva en una sola entrada de una máquina de turing $f$. Si y sólo si $f$ nunca termina para la entrada de $E$, $E$ terminar. De lo contrario, $E$ nunca va a detener.

También vamos a tener una máquina de turing $G$ que se lleva en una sola entrada de una máquina de turing $f$. Si y sólo si $f$ termina para la entrada de $G$, $G$ nunca parar. De lo contrario, $G$ va a detener.

Ahora, aquí está el contraejemplo a detener problema:

Qué $G(E)$ terminar?

Mediante la implicación de la declaración que han "si y sólo si $E$ termina por la entrada de G no G terminar".

Sin embargo, examinemos que implícita la declaración: "Si y sólo si $G$ nunca termina para la entrada de $E$, $E$ terminar".

Por lo tanto, si $G(E)$ termina, luego por la segunda declaración, $E(G)$ nunca termina. Sin embargo, esto implica entonces que G(E) no termina!

Esencialmente, esta es la máquina de turing ejemplo combinado con una entrada que no es justo no puede ser predicho. Más bien, es indeterminado. No podemos determinar si esta máquina de turing termina como su propia terminación implica que no termina. Este es un ejemplo contrario a la proposición de la detención problema de "para cualquier entrada y la máquina de turing se puede determinar si es o no termina". En este caso, es... ninguno de los dos.