La siguiente imagen ilustra este teorema:
Pero no he podido entender de dónde vienen los números de la tercera cinta, ¿alguien podría explicármelo, por favor?
Gracias.
Respuesta
¿Demasiados anuncios?
Recordando la definición de una NDTM, la máquina que intentamos simular computará un árbol de cómputos de expansión infinita, donde la raíz es el estado inicial y los hijos de cada nodo son el resultado de aplicar una instrucción no determinista (que mapea un estado de la MT a un conjunto de estados).
Cada uno de los nodos de este grafo de cómputo puede identificarse unívocamente mediante un código de prefijo. Por ejemplo, podríamos asignar el código 13 a los terceros hijos de los primeros hijos de la raíz.
La NDTM aceptará la entrada si alguno de los estados de su árbol de cálculo se detiene en un estado de aceptación. Así que podemos hacer lo siguiente:
Genera secuencialmente todos los códigos prefijo posibles y ejecuta la rama de cálculo que te lleva al nodo del árbol de cálculo con dicho código. Si el estado acepta la entrada, entonces el NDTM simulado acepta la entrada y has terminado. Si no se detiene, entonces genera el siguiente prefijo y haz lo mismo.
La cinta en la que llevas la cuenta de los números de prefijo que has generado y visitado hasta ahora es la cinta de direcciones de la imagen.
Una sutileza que la prueba anterior pasa por alto es cómo determinar cuándo el NDTM se detiene sin aceptar. Para ello, tenemos que hacer un seguimiento de los prefijos asignados a los estados que se detienen sin aceptar, y sólo generar prefijos cuyo padre no se ha detenido todavía. Esto es fácil de hacer a través de un procedimiento como la primera búsqueda de amplitud.
Para ganar puntos extra, fíjate en que este procedimiento lleva un tiempo exponencial en relación con los pasos que da la NDTM. La conjetura P!=NP afirma que no existe ningún procedimiento de simulación que permita simular un NDTM en tiempo polinómico.
PD: por estado de la TM me refiero tanto al estado interno como al contenido de la cinta.
