Probabilistische Turingmaschine

Grundidee und Bedeutung

Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Modell aus der theoretischen Informatik. Sie erweitert die gewöhnliche Turingmaschine um Zufall: In jedem Rechenschritt kann sie durch ein Zufallsexperiment entscheiden, welcher von zwei möglichen Übergängen ausgeführt wird. Dadurch kann ein Lauf der Maschine auf derselben Eingabe anders enden als ein anderer Lauf.

Das Modell ist wichtig, weil es randomisierte Algorithmen mathematisch beschreibt. Solche Algorithmen nutzen Zufall, um Entscheidungen zu treffen oder schneller zu rechnen. Bei einer probabilistischen Turingmaschine untersucht man deshalb nicht nur, ob sie akzeptiert oder ablehnt, sondern auch mit welcher Wahrscheinlichkeit sie das richtige Ergebnis liefert.

Formale Definition

Eine probabilistische Turingmaschine ist eine Turingmaschine M = (Q, Σ, Γ, q₀, A, δ₁, δ₂). Der Unterschied zur gewöhnlichen Turingmaschine ist, dass sie statt einer Übergangsfunktion δ zwei Übergangsfunktionen besitzt:

δ₁: Q × Γ → Q × Γ × {L, R}

δ₂: Q × Γ → Q × Γ × {L, R}

Bei jedem Rechenschritt wählt die Maschine eine dieser beiden Übergangsfunktionen. Diese Wahl kann durch eine Bernoulli-verteilte Zufallsvariable δ ~ Ber(p) beschrieben werden. Dabei ist p die Wahrscheinlichkeit für eines der beiden δᵢ.

Die Bestandteile bedeuten: Q ist die endliche Zustandsmenge, Σ das endliche Eingabealphabet, Γ das endliche Bandalphabet, q₀ ∈ Q der Anfangszustand und A ⊆ Q die Menge der akzeptierenden Endzustände. Die Funktionen δ₁ und δ₂ legen jeweils fest, welches Zeichen geschrieben wird, welcher Zustand als Nächstes erreicht wird und ob sich der Schreib-Lese-Kopf nach links oder rechts bewegt.

Wenn die Maschine in einem akzeptierten Endzustand hält, ist das Ergebnis 0 oder 1: 0 bedeutet Ablehnung der Eingabe x, 1 bedeutet Annahme der Eingabe x.

Zufällige Rechnungen und Laufzeit

Zu jedem Rechenschritt gibt es zwei mögliche Übergänge. Welcher davon gewählt wird, hängt vom Zufall ab. Deshalb ist das Ergebnis einer Rechnung zufallsabhängig. Ein zweiter Lauf auf denselben Eingabedaten kann also ein anderes Ergebnis liefern.

Auch die Laufzeit kann von den zufälligen Entscheidungen abhängen. Darum wird die Laufzeit einer probabilistischen Turingmaschine über alle möglichen Rechnungen abgesichert definiert: Ist T: ℕ → ℕ eine Funktion, so hat die probabilistische Turingmaschine M die Laufzeit T, falls M auf der Eingabe x bei jeder möglichen Rechnung in höchstens T(|x|) Schritten hält. Dabei bezeichnet |x| die Länge der Eingabe.

Abgrenzung zu anderen Turingmaschinen

Eine deterministische Turingmaschine ist ein Spezialfall einer probabilistischen Turingmaschine. Dazu müssen die beiden Übergangsfunktionen gleich sein. Dann spielt die zufällige Wahl keine Rolle, weil beide Möglichkeiten denselben Schritt auslösen. Die Maschine verhält sich dann wie eine deterministische Turingmaschine mit einer einzigen Übergangsfunktion.

Eine nichtdeterministische Turingmaschine besitzt ebenfalls zwei Übergangsfunktionen, nutzt aber kein Zufallsexperiment. Man stellt sich bei ihr vor, dass bei jedem Rechenschritt beide Möglichkeiten verfolgt werden. Die Maschine verzweigt also immer weiter und durchläuft alle möglichen Pfade. Die zentrale Frage lautet dann, ob es irgendeinen Pfad gibt, der zur Akzeptanz führt, also zum Ergebnis 1.

Bei der probabilistischen Turingmaschine wird dagegen tatsächlich ein zufälliger Rechenweg ausgeführt. Man betrachtet das Ergebnis dieses zufälligen Laufs oder die Wahrscheinlichkeit, mit der ein bestimmtes Ergebnis erreicht wird.

Wahrscheinlichkeiten und Robustheit

Das Modell verwendet häufig Zufallsexperimente mit Wahrscheinlichkeit 1/2, also B(1/2)-Experimente. Es stellt sich aber die Frage, was passiert, wenn stattdessen eine andere feste Wahrscheinlichkeit 0 < p < 1 benutzt wird.

Wenn eine Maschine nur B(p)-Experimente ausführen kann, kann sie trotzdem B(1/2)-Experimente herstellen. Dafür gibt es einen Trick, der auf John von Neumann zurückgeht: Man führt die B(p)-Experimente paarweise aus, bis die beiden Ergebnisse verschieden sind. Dann wählt man als Ergebnis das Ergebnis der ersten Komponente. Man kann zeigen, dass dadurch ein B(1/2)-Experiment entsteht. Daher kann man alle Rechnungen einer probabilistischen Turingmaschine auch mit einer Maschine ausführen, die statt B(1/2)-Experimenten nur B(p)-Experimente für ein festes 0 < p < 1 besitzt.

Umgekehrt ist schwieriger, ob man mit B(1/2)-Experimenten auch B(p)-Experimente herstellen kann. Für nicht-berechenbares p ist das sicher nicht möglich. Unter moderaten Bedingungen an p ist es aber mit konstantem Mehraufwand möglich. Dafür genügt, 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.

Komplexitätsklassen

Probabilistische Turingmaschinen werden verwendet, um Komplexitätsklassen für randomisierte Algorithmen zu definieren. Eine Komplexitätsklasse fasst Probleme oder Sprachen danach zusammen, mit welchen Rechenressourcen sie gelöst werden können.

Sei T: ℕ → ℕ eine Funktion und L ⊂ {0,1}* eine Sprache. Man sagt, L werde von einer probabilistischen Turingmaschine M in der Zeit T entschieden, wenn M auf jeder Eingabe x ∈ {0,1}* nach höchstens T(|x|) Schritten hält und P(M(x)=L(x)) ≥ 2/3 gilt. Dabei ist M(x) das Ergebnis 0 oder 1 der Rechnung von M auf x. L(x) ist 1, wenn x ∈ L gilt, und 0, wenn x nicht in L liegt. Die Wahrscheinlichkeit P bezieht sich auf alle möglichen Rechnungen der Maschine.

BPTIME(T(n)) ist die Menge aller Sprachen, die von einer probabilistischen Turingmaschine in der Zeit T entschieden werden können. Besonders wichtig sind Sprachen, die in polynomialer Zeit entschieden werden können. Dafür definiert man BPP = ⋃_{c∈ℕ} BPTIME(n^c).

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