In der Berechenbarkeitstheorie ist eine probabilistic Maschine von Turing eine nichtdeterministische Maschine von Turing, die zufällig zwischen den verfügbaren Übergängen an jedem Punkt gemäß etwas Wahrscheinlichkeitsvertrieb wählt.

Im Fall von gleichen Wahrscheinlichkeiten für die Übergänge kann es als eine deterministische Maschine von Turing definiert werden, die einen zusätzlichen hat, "schreiben" Instruktion, wo der Wert des Schreibens im Alphabet der Turing Maschine gleichförmig verteilt wird (allgemein, eine gleiche Wahrscheinlichkeit, '1' oder '0' auf dem Band zu schreiben.) Eine andere allgemeine neue Darlegung ist einfach eine deterministische Maschine von Turing mit einem zusätzlichen Band, das mit zufälligen Bit voll ist, genannt das zufällige Band.

Demzufolge kann eine probabilistic Maschine von Turing (verschieden von einer deterministischen Turing Maschine) haben stochastische Ergebnisse; auf einem gegebenen Eingang und Instruktion setzen Maschine fest, sie kann verschiedene Durchlaufzeiten haben, oder sie kann überhaupt nicht hinken; weiter kann es einen Eingang in einer Ausführung akzeptieren und denselben Eingang in einer anderen Ausführung zurückweisen.

Deshalb kann der Begriff der Annahme einer Schnur durch eine probabilistic Maschine von Turing unterschiedlich definiert werden. Verschiedene polynomisch-malige randomized Kompliziertheitsklassen, die sich aus verschiedenen Definitionen der Annahme ergeben, schließen RP, HANDELSGESELLSCHAFT, BPP und ZPP ein. Wenn wir die Maschine auf den logarithmischen Raum statt der polynomischen Zeit einschränken, erhalten wir den analogen RL, Co-RL, BPL und ZPL. Wenn wir beide Beschränkungen geltend machen, bekommen wir RLP, Co-RLP, BPLP und ZPLP.

Berechnung von Probabilistic ist auch für die Definition von den meisten Klassen von interaktiven Probesystemen kritisch, in denen die verifier Maschine von Zufälligkeit abhängt, um zu vermeiden, vorausgesagt und durch die allmächtige prover Maschine beschwindelt zu werden. Zum Beispiel die Klasse IP kommt PSPACE gleich, aber wenn Zufälligkeit vom verifier entfernt wird, werden wir mit nur NP verlassen, der nicht bekannt, aber weit geglaubt ist, eine beträchtlich kleinere Klasse zu sein.

Eine der Hauptfragen der Kompliziertheitstheorie ist, ob Zufälligkeit Macht hinzufügt; d. h. gibt es ein Problem das kann in der polynomischen Zeit durch eine probabilistic Maschine von Turing, aber nicht eine deterministische Maschine von Turing gelöst werden? Oder können deterministische Maschinen von Turing alle probabilistic Maschinen von Turing mit höchstens einer polynomischen Verlangsamung effizient vortäuschen? Es wird zurzeit von Forschern weit geglaubt, dass der Letztere der Fall ist, der P = BPP einbeziehen würde. Dieselbe Frage für den Klotz-Raum statt der polynomischen Zeit (tut L = BPLP?) wird noch weiter geglaubt, wahr zu sein. Andererseits gibt die Macht-Zufälligkeit interaktiven Probesystemen und den einfachen Algorithmen, die sie für schwierige Probleme wie polynomisch-malige Primality-Prüfung schafft und mit dem Klotzraumgraph-Zusammenhang-Prüfung darauf hinweisen, dass Zufälligkeit Macht hinzufügen kann.

Ein Quant-Computer ist ein anderes Modell der Berechnung, die von Natur aus probabilistic ist.

Siehe auch

• Algorithmus von Randomized

Links

• NIST Website auf probabilistic Maschinen von Turing