No entiendo el concepto de Máquina de Turing No Determinista [cerrado]

Question

No entiendo el concepto de Máquina de Turing No Determinista [cerrado]

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 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 I léase, puede estar en más de un estado a la vez. También el artículo de wikipedia sugiere " Una máquina de Turing no determinista (NTM), puede tener un conjunto de reglas que prescriben más que una acción para una situación dada " .

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

29

algorithm turing-machines state non-deterministic

Author: Community, 2012-11-23

Source

1 answers

score 43 · Accepted Answer

En una máquina de Turing No Determinista, en cada rama - haces ambas posibilidades - y solo cuando terminas "eliges" cuál es la que necesitas para la solución (si existe).

Por ejemplo, veamos el problema de la suma del subconjunto , 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 en orden para que el algoritmo produzca "true". Da "falso" solo si no hay tal cálculo.

El concepto de Máquina de Turing No Determinista es puramente teórico - no hay máquina de turing no determinista disponible.

Bono:
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 Detención no se puede decidir en ninguno de los dos. Sin embargo, NPC los problemas 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.