Ich verstehe das Konzept der nichtdeterministischen Turingmaschine nicht
Ich glaube nicht, die verstehen das Konzept der Nicht-Deterministische Turing-Maschine. Ich denke, ich verstehe den Begriff Nicht deterministischen Algorithmus : (nicht deterministische Algorithmus ist ein Algorithmus, weisen ein unterschiedliches Verhalten auf verschiedenen
läuft, im Gegensatz zu einem deterministischen Algorithmus.) Also der Algorithmus könnte wie :
a = fromSomeAlgo();
if(a > foo)
stateA();
else
stateB();
Aber für nicht-deterministische turing-Maschine ich Lesen , es kann in mehr als einem Staat zu einem bestimmten Zeitpunkt. Auch ein wikipedia-Artikel schlägt "Eine nicht-deterministische Turing-Maschine (NTM), kann ein Regelwerk, das vorschreibt, dass mehr
als eine Aktion für eine bestimmte situation".
Was bedeutet das ? ..Mehr als eine Aktion für eine bestimmte stituation...mehrere Staaten... ich einfach nicht verstehen.
InformationsquelleAutor der Frage Suhail Gupta | 2012-11-23
Du musst angemeldet sein, um einen Kommentar abzugeben.
In einer Nicht Deterministischen Turing Maschine, in jeder Filiale - führen Sie beide Möglichkeiten - und nur dann, wenn Sie fertig sind Sie "wählen", die eine ist die, die Sie brauchen für die Lösung (falls vorhanden).
Zum Beispiel, schauen wir uns die subset-sum-problemmit
S = {a,b,c... }
. Die Nicht-Deterministische Turing-Maschine hat eine lineare Lösung:Den Baum generiert wird etwas sein wie:
Es genug ist, dass eine Berechnung (Pfad im Baum) richtig ist, um die für den Algorithmus ergeben "wahr". Es ergibt sich "false" nur wenn es keine solche Berechnung.
Dem Konzept der Nicht-Deterministischen Turing-Maschine ist rein theoretisch - es gibt keine nicht-deterministischen turing-Maschine zur Verfügung.
Bonus:
Beachten Sie, dass alles, was getan werden kann, mit Nicht-Deterministischen Turing-Maschine kann durch eine Deterministische Turing-Maschine (und Umgekehrt) - für Beispiel, die Halteproblem ist nicht decideable entweder. Jedoch, NPC-Probleme getan werden kann, polynomially in Nicht Deterministischen Turing-Maschinen, und wir nicht wissen (und wir davon ausgehen können wir nicht), wie es zu tun polynomially, die auf Deterministischen Turing-Maschinen.
InformationsquelleAutor der Antwort amit