Pregunta No entiendo el concepto de Máquina de Turing no determinista [cerrado]


Yo no entiendo el concepto de Máquina no determinista de Turing. Supongo que entiendo el término Algoritmo no determinista : (algoritmo no determinista es un algoritmo que puede exhibir diferentes comportamientos en diferentes se ejecuta, a diferencia de un algoritmo determinista). Así que el algoritmo podría ser como:

a = fromSomeAlgo();

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

Pero para máquina de turing no determinista yo leer , 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 prescriba más de una acción para una situación dada ".

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


29
2017-11-23 06:19


origen


Respuestas:


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 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 arroje "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 la máquina de Turing no determinista se puede hacer con una máquina de Turing determinista (y viceversa), por ejemplo, la Deteniendo el problema no es decidible 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 suponemos que no podemos) cómo hacerlo polinomialmente en las máquinas de Turing deterministas.


43
2017-11-23 06:53