Je ne comprends pas le concept de machine de Turing non déterministe [fermé]
je n'ai pas du comprendre le concept de Non Déterministe Machine de Turing . Je suppose que je comprends le terme algorithme non déterministe : (algorithme non déterministe est un algorithme qui peut montrer des comportements différents sur différents s'exécute, par opposition à un algorithme déterministe.) Ainsi l'algorithme pourrait être comme:
a = fromSomeAlgo();
if(a > foo)
stateA();
else
stateB();
Mais pour non-déterministe de la machine de turing je lire , il peut être dans plus d'un état à un moment donné. Aussi un article wikipedia suggère " une machine de Turing non déterministe( NTM), peut avoir un ensemble de règles qui prescrit plus plus d'une action pour une situation donnée " .
ça veut dire Quoi ? ..Plus d'une action pour une stituation...plusieurs états... Je ne comprends tout simplement pas cela.
1 réponses
dans une machine de Turing non déterministe, dans chaque branche - vous faites les deux possibilités - et seulement quand vous avez fait vous" choisissez " lequel est celui dont vous avez besoin pour la solution (si un existe).
par exemple , regardons le problème de la somme des sous-ensembles , avec S = {a,b,c... } . La machine de Turing non déterministe a une solution linéaire:
for each element:
"guess" if it is in the subset
check if the subset has the specified sum
L'arbre généré sera quelque chose comme:
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
il suffit qu'un calcul (chemin dans l'arbre) soit correct pour que l'algorithme donne"vrai". Il ne donne "faux" que s'il n'y a pas de tel calcul.
le concept de machine de turing non déterministe est purement théorique - il n'y a pas de machine de turing non déterministe disponible.
Bonus:
notez que tout ce qui peut être fait avec non déterministe Machine de Turing - peut être fait avec une machine de Turing déterministe (et vice versa) - par exemple, le problème D'arrêt n'est pas décidable dans l'un ou l'autre. Cependant, les problèmes de NPC peuvent être faits polynomialement dans les machines de Turing non déterministes, et nous ne savons pas (et nous supposons que nous ne pouvons pas) comment le faire polynomialement sur les Machines de Turing déterministes.