algorithm - teoria - No entiendo el concepto de máquina de Turing no determinista

maquina de turing universal

Question

No entiendo el concepto de máquina de Turing no determinista . Supongo que entiendo el término algoritmo no determinista : (algoritmo no determinista es un algoritmo que puede mostrar diferentes comportamientos en diferentes ejecuciones, a diferencia de un algoritmo determinista). Por lo tanto, el algoritmo podría ser como:

a = fromSomeAlgo();

if(a > foo)
   stateA();
else
   stateB();

Pero para la máquina de read no determinista que read , puede estar en más de un estado en un momento dado. También un artículo de wikipedia sugiere "Una máquina de Turing no determinista (NTM) puede tener un conjunto de reglas que prescribe más de una acción para una situación dada" .

Qué significa eso ? ..Más de una acción para una situación dada ... múltiples estados ... Simplemente no entiendo esto.

Answer 1

En una máquina de Turing no determinista, en cada rama, usted hace ambas posibilidades, y solo cuando termina, "elige" cuál es la que necesita para la solución (si existe).

Por ejemplo, veamos el problema de la suma de subconjuntos , con S = {a,b,c... } . La máquina de Turing no determinista tiene una solución lineal:

for each element:
   "guess" if it is in the subset
check if the subset has the specified sum

El árbol generado será algo así:

                                       start
                 with a                                      without a
               /         /                                   /          /
              /           /                                 /            /
             /             /                               /              /
      with b               without b                  with b              without b
      /     /               /       /                 /     /             /        /
  with c    without c    with c     without c     with c    without c    with c     without c

Es suficiente que un cálculo (ruta en el árbol) sea correcto para que el algoritmo produzca "verdadero". Da "falso" solo si no hay tal cálculo.

El concepto de máquina de Turing no determinista es puramente teórico: no hay una máquina de turing no determinista disponible.

Prima:
Tenga en cuenta que todo lo que se puede hacer con una máquina de Turing no determinista, se puede hacer con una máquina de Turing determinista (y viceversa); por ejemplo, el problema de la detención no se puede decidir en ninguno de los dos. Sin embargo, los problemas de NPC se pueden hacer polinomialmente en máquinas de Turing no deterministas, y no sabemos (y asumimos que no podemos) cómo hacerlo polinomialmente en máquinas de Turing deterministas.