Diskussion:Orakel-Turingmaschine

Eine mögliche Redundanz der Artikel Nichtdeterministische Turingmaschine und Orakel-Turingmaschine wurde im Oktober 2007 diskutiert (zugehörige Redundanzdiskussion). Bitte beachte dies vor der Anlage einer neuen Redundanzdiskussion.

• Es sollte noch ein Abschnitt über Relativierung und den Zusammenhang zur Diagonalisierung geben. Außerdem wäre es schön, wenn auf das P=NP Problem in diesem Kontext eingegangen wird. (Zufallsorakelhypothese). --Tobias Diskussion:Orakel-Turingmaschine#c-TVoe-2008-07-01T13:59:00.000Z11Beantworten

Falls du das mit Relativierung meintest, hab ich den entsrpechenden Abschnitt hinzugefügt. Deine Ausführung zur Diagonalisierung erschliesst sich mir nicht. Meinst du den Beweis, dass das Orakel-Halteproblem für Orakel-Turingmaschinen unentscheidbar ist? Der ist wortgleich zum Ursprungsbeweis, ausserdem scheinen ja Beweise von manchen Leuten in der Wikipedia eh nicht gern gesehen zu werden.

--86.56.107.65 Diskussion:Orakel-Turingmaschine#c-86.56.107.65-2015-04-11T16:06:00.000Z-TVoe-2008-07-01T13:59:00.000Z11Beantworten

Ist dies so richtig? Ich meine co-NP ist in P^NP = P^SAT = P^Compl(SAT) enthalten. NP ist aber nicht beweisbar abgeschlossen unter Komplementbildung.

Danke für den Hinweis, 212.117.84.247. Du hast recht. Die Gleichung muss lauten NP = NP^P. Ich habe das im Artikel korrigiert.--AlfonsGeser Diskussion:Orakel-Turingmaschine#c-AlfonsGeser-2008-05-31T07:46:00.000Z-Auf dieselbe Weise zeigt man NP = P^NP.11Beantworten

Hallo, ich habe den Begriff des Orakels bisher immer nur im Zusammenhang mit nichtdeterministischen Turingmaschinen gehört. Ist das nicht dasselbe? Bitte erläutern, ansonsten käme hier ggf. ein Redundanz-Baustein in Betracht. --Mkleine Diskussion:Orakel-Turingmaschine#c-Mkleine-2007-09-29T14:46:00.000Z-Orakel = Nichtdeterministische TM?11Beantworten

Technisch gibt es keinen wesentlichen Unterschied, aber die Intention ist unterschiedlich. Bei Orakel-TM nimmt man geeignete Orakel hinzu um die Berechenbarkeit zu verstärken oder die Komplexität zu verringern. Zum Beispiel TM mit dem Halteproblem als Orakel können das Halteproblem für TM lösen. TM mit SAT als Orakel können jedes NP-vollständige Problem in polynomialer Zeit lösen. Und so weiter. Bei den nicht-deterministischen TM führt man eine Schar von Orakeln ein, um den Nichtdeterminismus deterministisch darzustellen. Das Orakel ist hier eine unendliche Bitfolge. Die TM befragt bei jedem nicht-deterministischen Schritt das Orakel, das heißt holt das nächste Bit ab, und trifft so seine Entscheidung.--AlfonsGeser Diskussion:Orakel-Turingmaschine#c-AlfonsGeser-2008-05-17T10:40:00.000Z-Mkleine-2007-09-29T14:46:00.000Z11Beantworten

Ich war mal mutig, und habe gleich meine Vorschläge in den Artikel eingearbeitet. Auch die Bemerkungen zum Halteproblem habe ich gleich mit überarbeitet. Die Notation für Klassen habe ich gleich allgemein formuliert für beliebige Sprachklassenpaare.--AlfonsGeser Diskussion:Orakel-Turingmaschine#c-AlfonsGeser-2008-05-17T14:38:00.000Z-Mkleine-2007-09-29T14:46:00.000Z11Beantworten

Ich muss zugeben, dass mein Verständnis dieser Definition nicht wirklich über ein nebuloses Bild hinausgeht. Möglicherweise könnte man das ganze etwas nach mehr nach dem englischen Wikipediaartikel http://en.wikipedia.org/wiki/Oracle_machine gestalten? Weiß jemand vielleicht, ob die beiden Definitionen äquivalent sind? (bzw. ob die durch zwei Turingmaschinen mit gleichem Orakel nach der einen und nach der anderen Definition die gleichen Probleme in gleicher Komplexität gelöst werden?) -- Mkoeberl (Diskussion) Diskussion:Orakel-Turingmaschine#c-Mkoeberl-2012-03-24T13:22:00.000Z-Definition der Orakelturingmaschine11Beantworten

Um deine Frage direkt zu beantworten: Die beiden Definitionen sind gleichmächtig. Sie sind dabei zwei von unzähligen Versuchen den Fakt zu formalisieren, dass mensch eine Frage fragt, auf "magische" Art eine Antwort bekommt und dann abhängig von der Antwort seine Berechnung weiterführt. Turing-Maschinen sind dabei ja nur eine vglw. anschaulige Formalisierung des Berechenbarkeitsbegriffes. Die Churchsche These mal voraus gesetzt lässt sich das ganze auch bspw. im Lambda-Kalkül realisieren, indem mensch die gewüschte (charakteristische) Funktion einfach ebenfalls (vorübergehend) als berechenbar deklariert. Das ist aber natürlich weniger greifbar als die Einführung neuer Eingabebänder oder Zustände, da letztere aber ebenfalls nur Objekte unseres Denkens sind, tun all die Formalismen das gleiche. Die Effekte dieser Erweiterung sind allerdings wieder hoch interessant und zu Recht Forschungsgegenstand der Berechenbarkeitstheorie ...um nen schönen Beweis in sein Paper zu kriegen, braucht man eben ne robuste Definition. Welche genau ist dagegen reine Geschmackssache.

--86.56.107.65 Diskussion:Orakel-Turingmaschine#c-86.56.107.65-2015-04-11T15:59:00.000Z-Mkoeberl-2012-03-24T13:22:00.000Z11Beantworten

Es heißt

Zum Beispiel können Turingmaschinen mit dem Halteproblem als Orakel das Halteproblem für Turingmaschinen lösen.

was bedeutet in diesem Satz "Halteproblem als Orakel"? Heißt es "das Orakel löst (jedes beliebige) Halteproblem"? Oder was anderes? --Hfst (Diskussion) Diskussion:Orakel-Turingmaschine#c-Hfst-2019-04-25T10:12:00.000Z-Definition der Orakelturingmaschine11Beantworten