Probabilistische Turingmaschine - LinkFang.de





Probabilistische Turingmaschine


Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Konzept aus der theoretischen Informatik. Es handelt sich um eine Turingmaschine, die zusätzlich die Fähigkeit hat, ihre Rechenwege durch ein Zufallsexperiment zu steuern.

Definition

Eine probabilistische Turingmaschine[1] ist eine Turingmaschine, die statt einer Übergangsfunktion zwei Übergangsfunktionen hat und bei jedem Rechenschritt durch ein B(½)-Zufallsexperiment die erste oder die zweite Übergangsfunktion auswählt. Wenn die Turingmaschine auf einer Eingabe [math]x[/math] schließlich hält, dann ist das Ergebnis 0 (Ablehnung von [math]x[/math]) oder 1 (Annahme von [math]x[/math]).

Dem liegt die Vorstellung zu Grunde, dass es zu jedem Rechenschritt zwei mögliche Übergänge gibt, das heißt zwei Möglichkeiten, ein Zeichen zu schreiben, den nächsten Zustand festzulegen und die nächste Schreiblesekopfbewegung auszuführen. Welche der zwei Möglichkeiten gewählt wird, hängt vom Zufall ab. Das Ergebnis der Rechnung ist also zufallsabhängig, ein zweiter Lauf der Maschine auf denselben Eingabedaten kann zu einem anderen Ergebnis führen.

Insbesondere kann die Laufzeit einer Rechnung von den zufälligen Wahlen der Übergangsfunktion abhängen. Die Laufzeit einer probabilistischen Turingmaschine wird daher wie folgt definiert: Ist [math]T:\N\rightarrow \N[/math] eine Funktion, so sagt man, die probabilistische Turingmaschine M habe Laufzeit [math]T[/math], falls M auf der Eingabe [math]x[/math] bei jeder möglichen Rechnung in höchstens [math]T(|x|)[/math] Schritten hält, wobei [math]|x|[/math] die Länge der Eingabe sei.

Abgrenzungen

Deterministische Turingmaschine

Deterministische Turingmaschinen können als Spezialfall einer probabilistischen Turingmaschine angesehen werden. Dazu müssen die zwei Übergangsfunktionen gleich sein, denn dann ist jeder Rechenschritt unabhängig von der Wahl der Übergangsfunktion und damit vom Ausgang des Zufallsexperiments und die Maschine verhält sich wie eine deterministische Turingmaschine mit dieser einen Übergangsfunktion.

Nichtdeterministische Turingmaschine

Auch die nichtdeterministische Turingmaschine ist durch zwei Übergangsfunktionen gekennzeichnet, sie verfügt aber nicht über die Möglichkeit eines Zufallsexperiments. Bei der nichtdeterministischen Turingmaschine stellt man sich eher vor, dass bei jedem Rechenschritt beide Möglichkeiten gewählt werden, so dass die Maschine durch fortwährende Verzweigung jeden möglichen Pfad durchläuft. Es stellt sich dann die Frage, ob es einen Pfad gibt, der zur Akzeptanz führt, das heißt das Ergebnis 1 hat. Bei einer probabilistischen Turingmaschine verwendet man tatsächlich das Ergebnis der zufallsbedingten Rechnung bzw. untersucht Wahrscheinlichkeiten, mit denen ein Ergebnis erreicht wird.

Robustheit bezüglich der Wahrscheinlichkeit

Es stellt sich die Frage, wie sich das hier vorgestellte Rechnermodell verhält, wenn man die Wahrscheinlichkeit ½ der B(½)-Zufallsexperimente durch eine andere Wahrscheinlichkeit 0 < p < 1 ersetzt. Kann die Maschine nur B(p)‑Experimente ausführen, so kann sie durch folgenden auf John von Neumann[2] zurückgehenden Trick auch B(½)‑Zufallsexperimente ausführen. Die B(p)‑Experimente werden solange paarweise ausgeführt, bis die beiden Komponenten des Doppelexperiments verschieden sind; als Ergebnis wählt man dann das Ergebnis der ersten Komponente. Man kann zeigen, dass dadurch ein B(½)-Experiment zu Stande kommt. Daher kann man alle Rechnungen einer probabilistischen Turingmaschine auch mit einer solchen ausführen, für die statt der B(½)‑Experimente „nur“ B(p)-Experimente für ein festes 0 < p < 1 möglich sind.

Etwas schwieriger ist die Frage, ob man mittels einer probabilistischen Turingmaschine auch B(p)-Experimente herstellen kann. Für nicht-berechenbares p ist das sicher nicht möglich. Moderate Bedingungen an p ermöglichen allerdings mit konstantem Mehraufwand mittels B(½)‑Experimente B(p)‑Experimente durchzuführen. Dazu genügt es, dass es ein Polynom [math]f[/math] gibt und eine deterministische Turingmaschine, die die i‑te Nachkommastelle der Binärdarstellung von p in der Zeit [math]f(i)[/math] berechnet.[3]

Komplexitätsklassen

Da randomisierte Algorithmen durchaus praxisrelevant sind, liegt es nahe, Komplexitätsklassen mittels probabilistischer Turingmaschinen zu definieren.

Hauptartikel: BPP (Komplexitätsklasse)

Ist [math]T:\N\rightarrow \N[/math] eine Funktion und [math]L\subset \{0,1\}^*[/math] eine Sprache, so sagt man, [math]L[/math] werde von einer probabilistischen Turingmaschine M in der Zeit [math]T[/math] entschieden, falls M auf jeder Eingabe [math]x\in\{0,1\}^*[/math] nach höchstens [math]T(|x|)[/math] Schritten hält und [math]\textstyle P(M(x)=L(x)) \ge \frac{2}{3}[/math]. Dabei ist [math]M(x)[/math] das Ergebnis 0 oder 1 der Rechnung der Maschine M auf der Eingabe [math]x[/math], [math]L(x)[/math] ist 1 oder 0, je nachdem ob [math]x\in L[/math] oder nicht, und die Wahrscheinlichkeit [math]P[/math] bezieht sich auf die Gesamtheit aller möglichen Rechnungen.

[math]\mathrm{BPTIME}(T(n))[/math] ist die Menge aller Sprachen, die von einer probabilistischen Turingmaschine in der Zeit [math]T[/math] entschieden werden kann. Besonderes Interesse besteht an der Menge der Sprachen, die in polynomialer Zeit von einer probabilistischen Turingmaschine entschieden werden können, man definiert daher[4]

[math]\mathrm{BPP} = \bigcup_{c\in \N}\mathrm{BPTIME}(n^c)[/math].

Eine weitere wichtige Anwendung ist die Definition der Komplexitätsklasse IP der interaktiven Beweissysteme, die zu einer äquivalenten Charakterisierung der Komplexitätsklasse PSPACE führt.

Einzelnachweise

  1. Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press (2009), ISBN 978-0-521-42426-4, Abschnitt 7.1: Probabilistic Turing Machines
  2. John von Neumann: Various techniques used in connection with random digits, Applied Math Series (1951), Band 12, Seiten 36–38
  3. Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press (2009), ISBN 978-0-521-42426-4, Lemma 7.12
  4. Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press (2009), ISBN 978-0-521-42426-4, Definition 7.2

Kategorien: Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Probabilistische Turingmaschine (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.