Kann eine probabilistische Turingmaschine das Halteproblem lösen?

Ein Computer mit einem unendlichen Strom von wirklich zufälligen Bits ist leistungsfähiger als ein Computer ohne. Die Frage ist: Ist es mächtig genug, um das Halteproblem zu lösen?

Kann ein probabilistischer Computer feststellen, ob ein deterministisches Programm anhält oder nicht ?

Beispiel für einen probabilistischen Computer, der etwas tut, das ein Determinist nicht kann: Betrachten Sie ein kleines Programm (weniger als ein Kilobyte lang), das eine Zeichenfolge mit einer Kolmogorov-Komplexität ausgibt, die größer als ein Gigabyte ist. Die Kolmogorov-Komplexitäteines Strings ist die Länge des kürzesten deterministischen Programms, das diesen String erzeugt. Somit kann ein deterministisches Programm per Definition keinen String erzeugen, dessen Komplexität größer ist als seine eigene Länge. Wenn jedoch ein unendlicher Strom von wirklich zufälligen Bits gegeben ist, kann ein kleines Programm die Aufgabe mit 99,99999 ...% Erfolg erfüllen, indem es einfach beispielsweise 10 Milliarden zufällige Bits ausgibt und hofft, dass die Kolmogorov-Komplexität dieser Bits hoch genug ist . Daher liegt die Erzeugung einer Kette von überlegener Kolmogorov-Komplexität innerhalb des Wahrscheinlichkeitshorizonts des probabilistischen Programms, für das deterministische Programm jedoch überhaupt nicht möglich.

Trotzdem frage ich mich, ob es möglich ist, wirklich zufällige Bits zu verwenden, um das Problem des Anhaltens in den Griff zu bekommen. Beispielsweise kann ein Algorithmus Theoreme zufällig erzeugen und sie beweisen / widerlegen / verwerfen, bis er genug weiß, um zu beweisen / widerlegen, dass ein gegebenes deterministisches Programm anhält.

edit: Ich habe gerade festgestellt, dass einige der Dinge, die ich geschrieben habe, totaler Unsinn sind, sorry dafür. Jetzt habe ich den Beweis geändert und die Definition der Wahrscheinlichkeitsmaschine, die ich benutze, präzisiert.

Ich weiß nicht, ob ich Ihre Definition der probabilistischen Turing-Maschine richtig verstanden habe: Es handelt sich um eine Maschine mit einem zusätzlichen Band, auf das eine unendliche inkompressible Zeichenfolge geschrieben ist, und daneben verhält sie sich wie eine deterministische Maschine? Wenn wir den inkompressiblen String reparieren, scheint die Klasse, die wir bekommen, nicht interessant zu sein.

Ich denke, wir können eine probabilistische Turing-Maschine auf verschiedene Arten definieren. Ich werde eine Definition verwenden , die ganz natürlich scheint (und für die mein Beweis funktioniert;) Lassen Sie uns eine probabilistische Maschine so definieren: es ein zusätzliches Band bekommt , auf dem einige unendliche Zeichenfolge geschrieben wird, wir sagen , dass diese Maschine eine Sprache entscheidet , wenn für jedes x ∈ L hält an und akzeptiert mit einer Wahrscheinlichkeit > $L$$x \in L$ , wenn die Wahrscheinlichkeit diese zusätzlichen zufälligen Zeichenfolgenübernimmtund für jedesx∉Lmit einer Wahrscheinlichkeit>1anhält und zurückweist$>\frac{1}{2}$$x \not \in L$ .$>\frac{1}{2}$

Wir werden nun zeigen, dass, wenn es eine solche Wahrscheinlichkeitsmaschine , die das Stoppproblem für die deterministischen Maschinen löst, wir sie verwenden könnten, um eine deterministische Maschine H zu bauen , die das Stoppproblem für die deterministischen Maschinen löst - und wir wissen, dass eine solche Maschine existiert kann nicht existieren.$P$$H$

Angenommen, ein solches existiert. Wir können eine deterministische Maschine M konstruieren , die eine Wahrscheinlichkeitsmaschine R mit einer Eingabe x als Eingabe nimmt , die$P$$M$$R$$x$

• stoppt und akzeptiert genau dann, wenn x akzeptiert (dh, R stoppt und akzeptiert x für mehr als die Hälfte der zufälligen Zeichenfolgen).$R$$x$$R$$x$
• hält an und lehnt nur ab, wenn x ablehnt (dh R hält an und lehnt x an mehr als der Hälfte der zufälligen Zeichenfolgen ab).$R$$x$$R$$x$
• Schleifen sonst

Grundsätzlich für alle i ∈ 1 , 2 , . . . simulieren Sie R am Eingang x und an jeder Zeichenkette von 0 , 1 i als Präfix der Zeichenkette auf dem Zufallsband von R. Jetzt:$M$$i \in 1, 2, ...$$R$$x$${{0,1}}^i$$R$

• wenn für Präfixe der LängeiR wurdenangehalten und akzeptiert, ohne zu versuchen, mehr alsiBits vom Zufallsbandzu lesen,M wirdangehalten und akzeptiert$>\frac{1}{2}$$i$ $R$$i$$M$
• wenn für Präfixe der LängeiRgestoppt und verworfenohne mehr zu lesen versuchtalsichaus der Zufallsband Bits,Mstoppt und Spuck$>\frac{1}{2}$$i$ $R$$i$$M$
• ansonsten führt die Simulation mit i : = i + 1 aus .$M$$i := i+1$

Wir müssen uns nun davon überzeugen, dass wenn x mit der Wahrscheinlichkeit p > 1 akzeptiert (ablehnt)$R$$x$ , dann werdeichfür einigeakzeptieren (ablehnen) für>$p >\frac{1}{2}$$i$ Präfixe der Längeider Zufallszeichenfolge, ohne zu versuchen, mehr alsiBits vom Zufallsbandzu lesen. Es ist technisch, aber recht einfach - wenn wir etwas anderes annehmen, nähert sich die Wahrscheinlichkeit des Akzeptierens (Zurückweisens)p>$>\frac{1}{2}$$i$$i$ alsibis ins Unendliche geht, also für einigeies muss seinp>$p >\frac{1}{2}$$i$$i$ .$p >\frac{1}{2}$

Nun definieren wir einfach unsere deterministische Maschine , um das Halteproblem zu lösen (dh zu entscheiden, ob eine gegebene deterministische Maschine N ein gegebenes Wort x ) a als H ( N , x ) = M ( P ( N , x ) ) akzeptiert . Beachten Sie, dass M ( P ( N , x ) ) immer anhält, weil die Entscheidung für eine Sprache durch unsere probabilistischen Maschinen so definiert wurde, dass immer eine dieser beiden vorkommt:$H$$N$$x$$H(N,x) = M(P(N,x))$$M(P(N, x))$

• Die Maschine hält an und akzeptiert mehr als die Hälfte der zufälligen Zeichenfolgen
• Die Maschine hält an und lehnt mehr als die Hälfte der zufälligen Zeichenfolgen ab.

Es kommt darauf an, was Sie mit einem probabilistischen Algorithmus meinen, der ein Prädikat bestimmt.

Es ist eine triviale probabilistischen Algorithmus P , so dass für eine deterministische Turingmaschine M ,

• P ( M ) akzeptiert mit einer Wahrscheinlichkeit ungleich Null, wenn M anhält,
• P ( M ) akzeptiert niemals, wenn M nicht anhält, und
• P ( M ) hält mit Wahrscheinlichkeit 1 für jedes M an .

Daher löst der probabilistische Algorithmus P das Halteproblem für deterministische Turingmaschinen in diesem Sinne. (Hier bedeutet " M anhalten" " M anhalten bei leerer Eingabe".)

Wenn Sie die Anforderung jedoch auf eine vernünftige Weise verstärken, ist es unwahrscheinlich, dass Sie das Halteproblem für deterministische Turing-Maschinen nicht mehr lösen können. Beispielsweise,

• Soll P ( M ) immer anhalten, anstatt nur mit Wahrscheinlichkeit 1 , so ist klar, dass P durch einen deterministischen Algorithmus simuliert werden kann. ( Eine Erklärung des Unterschieds zwischen "immer" und "mit Wahrscheinlichkeit 1" finden Sie in Wikipedia. )
• If you make the error bounds strict by requiring P(M) to halt and give the right answer with probability strictly greater than 1/2 for every M (that is, you do not care if P(M) does not halt or halts and give the wrong answer in the rest of the cases), then P can be simulated by a deterministic algorithm by using the argument stated in Karolina Sołtys’s answer.

Therefore, a probabilistic algorithm cannot solve the halting problem for deterministic Turing machines in these senses.

In general, if you have a probabilistic Turing machine $P$ solving some decision problem, you can always simulate it deterministically by running $P$ for every possible value of the randomness and outputting the majority answer of $P$. Therefore, no probabilistic Turing machine can solve an undecidable decision problem.

I think this was the meaning of Raphael's comment.

If the Lebesgue measure of those oracles that compute a set $A\subseteq\mathbb N$ is positive, then $A$ is computable. This goes back to de Leeuw, Moore, Shannon, and Shapiro in 1956 and Sacks in 1963. For a discussion see Downey and Hirschfeldt's new book Algorithmic randomness and complexity. As other answers have mentioned, the idea is to take a majority vote. (While this can be done computably, there is no claim that the algorithm is efficient.)

de Leeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N. Computability by probabilistic machines, Automata studies, pp. 183–212. Annals of mathematics studies, no. 34. Princeton University Press, Princeton, N. J., 1956.

G. Sacks, Degrees of Unsolvability, Princeton University Press, 1963.