Diskussion:Nichtdeterministische Turingmaschine

Tag,

bei der Beschreibung des Übergangs von einer Konfiguration in eine anderre steht am Beginn jeder Zeile dass ein a aus Q existieren soll. Hier soll es meiner Meinung nach aber a aus Gamma heißen. Da ich mich aber nicht wirklich auskenne in dem Gebiet, möchte ich das nicht selbst ändern.

Ciao

Da hast du natürlich recht. Hab ich geändert. --92.195.1.87 16:07, 14. Jun. 2008 (CEST)

Quantencomputer

Hallo,

die neueren Ergebnisse der Quantenmechanik haben ja nun das Konzept des -Quantencomputers- hervorgebracht. Konkreter, mittlerweile existiert ja schon die Quanten-Turingmaschine in der Theoretischen Informatik, der die Mächtigkeit eines Quantencomputer abbildet. Entspricht diese Quantenturingmaschine der nichtdeterministischen Turingmaschine ? (nicht signierter Beitrag von 84.142.162.163 (Diskussion) 14:21, 3. Nov. 2005)

---

Sur3 22:51, 28. Nov 2005 (MEZ):

Ich habe fast die gleiche frage, nämlich ob eine nichtdeterministische Turingmaschine

1. wirklich nur zufällig einen Weg wählt, denn das ließe sich doch wohl realisieren, und ich wüßte nicht wie man damit ein problem besser lösen kann?!?

oder

2. alle angegebenen Alternativen gleichzeitig durchläuft, wie bei einem Quantencomputer?

oder doch ganz anders?

Ich finde auch ein Beispiel wäre nicht schlecht, am besten eines, das ein NP-Problem in P löst!

---

11:54, 30. Nov 2005 (CET) FreW

Die NTM ist ist nicht mit einer Übergangsfunktion sondern mit einer Übergangsrelation definiert, diese Relation wird aber nicht näher spezifiziert. Die NTM ´rät´ eine richtige Lösung, so wurde das damals im Studium Informatik vermittelt. Die Quantenturigmaschine (QTM) hingegegen befindet sich in allen Lösungszuständen gleichzeitig, ein Ergebnis wird durch eine ´Messung´ abgegriffen. Die Komplexitätsklassen von NTM und QTM sind wohl nicht identisch, nach der neueren theoretischen Informatik.

Siehe meine Ergänzung des Artikels gerade: Die NTM kann auf beide Weisen interpretiert werden. Über Quanten-Turingmaschinen weiß ich leider nichts. -- UKoch (Diskussion) 17:10, 20. Mär. 2013 (CET)

Nicht realisierbar

Es wird behauptet, dass eine NTM nach heutigem Kenntnisstand "nicht realisierbar" sei. Das stimmt so nicht, denn jede NTM-Berechnung kann auf einer DTM simuliert werden, wenngleich bei meist dramatisch erhöhter Laufzeitkomplexität. Auch eine DTM ist natürlich nur innerhalb bestimmter Grenzen hinsichtlich der Speicherkapazität realisierbar. Aragorn2 14:06, 26. Apr 2006 (CEST)

---

Also zum ersten: die Quantenturingmaschine entspricht nicht der nichtdeterministischen Turingmaschine, da sie sehr wohl deterministisch rechnet, wenngleich sie sich zeitweise in einer Superposition aus Zuständen befindet und damit mehrere Berechnungspfade "gleichzeit" berechnet. Einfach ausgedrückt "wissen" bei der QTM unter bestimmten Bedingungen die Berechnungspfade voneinander, bei der NTM laufen sie wirklich parallel ohne, dass ein Berechnungspfad von einem anderen beeinflusst wird.

Zum zweiten: 1. Sie wählt die Wege nicht "zufällig", sie probiert alle Berechnungspfade gleichzeitig durch. Es gibt natürlich noch die probabilistischen Turingmaschinen, die unter einer gegebenen Wahrscheinlichkeitsverteilung einen Weg wählen. D.h. man kann mit einer bestimmten Fehlergenauigkeit sagen, ob das Ergebnis richtig ist oder nicht. 2. Die QTM durchläuft nicht immer alle Berechnugnspfade gleichzeitig. Die NTM jedoch schon. Und wenn ich ein Beispiel angeben könnte, dass ein Problem aus NP in P gelößt wird, dann hätte ich ne Menge mehr Geld ;) Mal ganz im Ernst, eine NTM probiert alle Wege parallel durch, kann aber in polynomieller Zeit verifizieren, ob eine Lösung richtig ist. Daher _N_ichtdeterministisch _P_olynomiell. Nebenbei bemerkt wurde von Bennet und Bernstein (Strength and weaknesses of quantum computing, SIAM Journal of Computer Sciences Vol. 26., No. 5, pp. 1510-1523, 1997) schon gezeigt, dass ein Problem aus NP nicht in unter $o(2^{n/2})$ gelöst werden kann. Also doch nicht polynomiell.

Zum Thema Realisierbarkeit: Wenn ich eine NTM mit einer DTM simuliere, dann ist sie ja nicht realisiert, sondern halt _simuliert_. Wenn ich natürlich nur eine ganz begrenzte Wortmenge in der Sprache habe kann ich eine NTM simulieren, indem ich parallel alle Pfade auf Korrektheit prüfe. Läßt sich nur nicht generalisieren. --Fraterq 11:29, 17. Nov. 2006 (CET)

Nein, Geld bekommen Sie erst, wenn Sie ein NP-vollstaendiges Problem in P loesen. Jedes P-Problem liegt ja trivialerweise in NP. Insbesondere muessen Bennet und Bernstein etwas anderes gesagt haben. Wahrscheinlich haben sie gezeigt, dass jedes NP-Problem deterministisch unter $o(2^{n/2})$ also schlimmstenfalls in exponentieller Zeit geloest werden kann. Das stimmt jedenfalls. --TB 0:05, 25. Nov. 2006 (CET)

Wäre dann also eine probabilistische Turingmaschine (wo an einer Stelle der nächste Rechenschritt durch einen zufälligen Input ausgewählt wird) eine NTM ? Das ist ohne weiteres realisierbar. Der zufällige Input kann z.B. der Eintritt (oder Nicht-Eintritt) des Zerfalls eines Atomkerns in einer bestimmten Zeiteinheit sein.--Claude J (Diskussion) 09:23, 10. Mai 2020 (CEST)

Ungenauigkeit?

Im Text steht: "Es ist eine allgemeine Fehleinschätzung, dass Quantencomputer NTMs entsprächen. NTMs können NP-vollständige Probleme lösen, Quantencomputer aber nicht."

Meiner Meinung nach kann sogar jeder stinknormale Computer NP-vollständige Probleme lösen, nur eben nicht in polynomieller Laufzeit.

Genau das wollte ich eben auch anmerken ;) --89.247.114.105 13:14, 21. Feb. 2007 (CET)

Es sind keine weiteren Bedingungen an die Übergangsrelation genannt. Auch habe ich hier aus anderen Quellen bisher keine konkreteren Angaben gefunden. Es scheint aber implizit immer angenommen zu werden, dass es für jeden Zustand mindestens einen Nachfolgezustand gibt (also d.h. es gibt eine Teilmenge der Relation, welche eine Funktion ist). Ist das korrekt? Hierauf sollte denke ich im Text hingewiesen werden, da es ja nicht unbedeutend ist. --Albertzeyer 18:30, 23. Mär. 2007 (CET)

Es kann durchaus sein, dass eine NTM für einen Zustand q und ein Eingabesymbol s keinen Folgezustand definiert, also kein Tupel der Form $(q,s,.,.,.,)$ in der Übergangsrelation enthalten ist. Gruss, --89.247.61.39 18:33, 30. Apr. 2007 (CEST)

Viele definieren NTMS mit einer Übergangsfunktion in der Weise, dass die Bilder dieser Funktion eine Menge von möglichen Folgezuständen nebst der Aktionen (Bewegung des Kopfes und Schreiben eines Zeichens) sind.

Damit wird der Erwartung entsprochen, dass man von einer Maschine eine Funktion erwartet.

--corpus 10:30, 29. Okt. 2010 (CEST)

Baubarkeit

Hallo,

Nichtdeterministische Turingmaschinen sind nur schwer baubar. Mein Behauptung ist, nichtdeterministische Turingmaschinen sind nur über parallele Turingmaschinen baubar. Der Satz von Salvitch sagt nur aus, daß parallele Turingmaschinen nichtdeterministische Turingmaschinen simulieren. Die einzige simulierende Maschine ist die Maschine.

Es geht um die Frage, ob die Simulation die Identität ist. Es geht also um die Frage was ist "baubar". Wie setze ich ein mathematisch Beschreibung in eine Maschine um. Nun baut heute niemand(?) eine Maschine mit Magnetbändern. Aber man simuliert diese Magnetbandmaschinen in den heute gängigen Computern. Diese simulierte Magnetbandmaschine kann man mit Hilfe paralleler Prozesse zu einer Nichtdeterministischen Turingmaschine umbauen.(zumindest glaube ich das jetzt noch). Die simulierte Magnetbandmaschinde wird über ein "Programm" gesteuert. Die daraus entwickelte Nichtdeterministische Turingmaschine wird dann durch Programme für diese Maschine gesteuert. Damit die Programmierbarkeit erhalten bleibt, kommt man um die Parallelität nicht rum. Ansonsten kommt es zu einer zunehmend zufällig reagierenden Maschine. Leider kann ich mich nicht einfacher ausdrücken.

--Watakiki 21:15, 28. Jun. 2011 (CEST)

1. Neue Beiträge bitte nach unten.

2. Leider kannst du auch nicht ausdrücken, was du möchtest. Ist das ein Kommentar zum Artikel? Ansonsten hilft ein Blick auf Wikipedia:Diskussionsseiten. --Zahnradzacken 23:54, 28. Jun. 2011 (CEST)

Merkwürdige Defnitionen

Warum wird entgegen der Praxis und entgegen andere Artikel merkwürdige Definitionen eingebracht die nicht nur umständlich sondern auch sehr wahrscheinlich falsch sind? F ist die Menge der akzep. Zustand. Es gibt logischerweise auch Endzustände die nichtakzeptierend sind. Was beide gemein haben, sie besitzen keine Folgekonfiguration. Gamma ist das Bandalphabet, logisch das dazu auch das Blanksymbol gehört. Von den Unstimmigkeiten bei den Übergangsrelation und Konfigurationen mal außer vor. Es gibt Skripte oder großartige Bücher von Papadimitrou(, Schönig), Wegener die jeder Informatikstudent kennen sollte. So jedenfalls liest sich der Artikel, als hätte es jemand abgeschrieben und den Inhalt nicht verstanden. --95.91.62.194 13:04, 14. Jun. 2012 (CEST)

Es gibt verschiedene Definitionen. Dass Du die hier angegebenen vorher nicht kanntest, heißt nicht, dass sie falsch sind. -- UKoch (Diskussion) 17:10, 20. Mär. 2013 (CET)

Woher stammt die hier wiedergegebene formale Definition (Beleg) ? L, N, R sind nicht erklärt.--Claude J (Diskussion) 09:12, 10. Mai 2020 (CEST)