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

Mit Wahrscheinlichkeit ½ entscheidet die Programmeinheit bei jedem Schritt über die zu verwendende Übergangsfunktion

Eine probabilistische Turingmaschine^[1] ist eine Turingmaschine $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ , die statt einer Übergangsfunktion $\delta$ zwei Übergangsfunktionen hat

\delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}

\delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}

und bei jedem Rechenschritt eine der beiden Übergangsfunktionen wählt. Dies kann durch eine Bernoulli-verteilte Zufallsvariable $\delta \sim \operatorname {Ber} (p)$ beschrieben werden, wobei $p$ die Wahrscheinlichkeit für eines der beiden $\delta _{i}$ 's ist

Wenn die Turingmaschine auf einem der akzeptierten Endzustände $A\subseteq Q$ hält, dann ist das Ergebnis $0$ (Ablehnung der Eingabe $x$ ) oder $1$ (Annahme von der Eingabe $x$ ).

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 $T\colon \mathbb {N} \rightarrow \mathbb {N}$ eine Funktion, so sagt man, die probabilistische Turingmaschine M habe Laufzeit $T$ , falls M auf der Eingabe $x$ bei jeder möglichen Rechnung in höchstens $T(|x|)$ Schritten hält, wobei $|x|$ die Länge der Eingabe sei.

Legende:

$Q$ endliche Zustandsmenge
$\Sigma$ endliches Eingabealphabet
$\Gamma$ das endliche Bandalphabet
$q_{0}\in Q$ der Anfangszustand
$A\subseteq Q$ Menge der akzeptierenden Endzustände
$\delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ probabilistische Überführungsfunktion 1
$\delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ probabilistische Überführungsfunktion 2

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 $f$ gibt und eine deterministische Turingmaschine, die die i‑te Nachkommastelle der Binärdarstellung von p in der Zeit $f(i)$ berechnet.^[3]

Komplexitätsklassen

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

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

$\mathrm {BPTIME} (T(n))$ ist die Menge aller Sprachen, die von einer probabilistischen Turingmaschine in der Zeit $T$ 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]

\mathrm {BPP} =\bigcup _{c\in \mathbb {N} }\mathrm {BPTIME} (n^{c})

.

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

↑ 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
↑ John von Neumann: Various techniques used in connection with random digits, Applied Math Series (1951), Band 12, Seiten 36–38
↑ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press (2009), ISBN 978-0-521-42426-4, Lemma 7.12
↑ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press (2009), ISBN 978-0-521-42426-4, Definition 7.2

[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

[1]

[2]

[3]

[4]