Wozu dient das Konzept der nicht-deterministischen Turing Maschine?
Die Turing-Maschine ist scheinbar ein wichtiges Konzept in der theoretischen Informatik. Ich selbst bin ein kompletter Laie in der Informatik, habe aber in anderen Zusammenhängen immer wieder davon gehört. Bisher habe ich aber nie verstanden, wozu man das Konzept einer "nicht-deterministischen Turing Maschine" (NTM) benötigt: Soweit ich laienhaft verstanden habe, tut man so, als könne diese NTM Ergebnisse für eine Eingabe quasi erraten (Orakel) und dann schnell auf Akzeptanz prüfen. Was meint man hier mit erraten? Wo ist der konzeptionelle Unterschied zu deterministischedn TMs? Auch dort kann ich ja auf beliebig viele Berechnungspfade aufspalten (Speicher ist ja unbegrenzt) und quasi "parallel" rechnen. Es geht ja bei NTM nicht darum wie effizient diese sind - aber dann verstehe ich nicht, was daran so interessant ist.
Kann mir jemand ein konkretes Beispiel liefern, sodass ich den Vorteil des Konzepts erkennen kann?
Wollte Touring auf Turing richtigstellen - das wurde aber abgelehnt.
2 Antworten
Eine NTM ist kein Orakel-TM - letztere gibt es auch.
Ja, natürlich kann man auch eine DTM nutzen, die ist aber ggf. einfach "unhandlicher".
Ich würde hier noch gerneetwas zur intuitiven Bedeutung sagen.
Bei der Frage P =?= NP geht es im Prinzip darum, ob man jedes Problem, für das man eine mögliche Lösung effizient (polynomiell) verifizieren kann (also feststellen kann, ob sie richtig ist), auch algorithmisch effizient lösen kann.
Ersteres ist die Interpretation einer OTM, welche äquivalent zur NTM ist, und letzteres die Interpretation der DTM.
Eine passendere Anschauung ist, dass die NTM nur den schnellsten Pfad durchläuft, ohne dass allgemein bekannt ist, welcher das ist. Da offenbart sich dann der Zusammenhang zur OTM. Sie "errät" den schnellsten Pfad. Das ist aus Sicht der Komplexität relevant, da das Ablaufen aller Pfade im Allgemeinen wesentlich länger dauert.
Es stimmt aber, dass sie nur aus theoretischer Sich tSinn ergibt. Sinn davon ist nicht, dies real anwenden zu können, sondern einen formalen Lösungsmechanismus zu haben, mit welchem man prinzipiell Überlegungen anstellen kann und dabei hilft, Beweise zu führen und die "Natur" von bestimmten Problemen zu verstehen, also was sie beispielsweise so schwer macht.
auf den ersten Blick macht sowas keinen Sinn. Ich glaube aber das Konzept nun verstanden zu haben: Bei der NTM geht man davon aus, dass sie alle möglichen Verzweigungen parallel erledigen kann und es geht nur darum, wie lange sie für einen der finalen Zweige maximal benötigt. Das hat mit einem realen Automaten nicjhts mehr zu tun. Interessant wird es bei Quantencomputern...