Czy probabilistyczna maszyna Turinga może rozwiązać problem zatrzymania?

Komputer z nieskończonym strumieniem naprawdę losowych bitów jest potężniejszy niż komputer bez niego. Pytanie brzmi: czy jest wystarczająco silny, aby rozwiązać problem zatrzymania?

Czy komputer probabilistyczny może ustalić, czy program deterministyczny przestaje działać?

Przykład, w którym komputer probabilistyczny robi coś, czego deterministycznie nie można: Rozważmy mały program (o długości mniejszej niż kilobajt), który generuje ciąg o złożoności Kołmogorowa większej niż gigabajt. Złożoność Kołmogorowaciągu to długość najkrótszego deterministycznego programu wytwarzającego ten ciąg. Zatem z definicji program deterministyczny nie może wytworzyć łańcucha, którego złożoność jest większa niż jego długość. Jeśli jednak otrzymamy nieskończony strumień prawdziwie losowych bitów, mały program jest w stanie osiągnąć to zadanie z 99,99999 ...% powodzeniem, po prostu powtarzając, powiedzmy, 10 miliardów losowych bitów i mając nadzieję, że złożoność Kołmogorowa tych bitów jest wystarczająco wysoka . Stąd wytwarzanie ciągu o wyższej złożoności Kołmogorowa mieści się w horyzoncie możliwości programu probabilistycznego, ale w ogóle nie jest możliwe w przypadku programu deterministycznego.

To powiedziawszy, zastanawiam się, czy można użyć naprawdę przypadkowych bitów do piły do ​​metalu przy problemie zatrzymania. Na przykład algorytm może losowo generować twierdzenia i je dowodzić / odrzucać / odrzucać, dopóki nie będzie wystarczająco dużo, aby udowodnić / obalić, że dany program deterministyczny przestaje działać.

edytuj: Właśnie zdałem sobie sprawę, że niektóre rzeczy, które napisałem, były totalne bzdury, przepraszam za to. Teraz zmieniłem dowód i uczyniłem definicję maszyny probabilistycznej, której używam, bardziej precyzyjną.

Nie wiem, czy dobrze rozumiem twoją definicję probabilistycznej maszyny Turinga: jest to maszyna z dodatkową taśmą, na której zapisany jest nieskończony nieściśliwy ciąg, a poza tym działa ona jak maszyna deterministyczna? Jeśli naprawimy nieściśliwy ciąg, otrzymana klasa nie będzie interesująca.

Myślę, że możemy zdefiniować probabilistyczną maszynę Turinga na kilka sposobów. Użyję definicji, która wydaje się całkiem naturalna (i na którą działa mój dowód;) Zdefiniujmy taką maszynę probabilistyczną: dostaje dodatkową taśmę, na której zapisany jest nieskończony ciąg, mówimy, że ta maszyna decyduje o języku jeśli co zatrzymuje się i przyjmuje z prawdopodobieństwem , kiedy prawdopodobieństwo jest przejmowane przez te dodatkowe losowe ciągi, a dla każdego zatrzymuje się i odrzuca z prawdopodobieństwem .x ∈ L > $L$$x \in L$ x∉L>$>\frac{1}{2}$$x \not \in L$$>\frac{1}{2}$

Pokażemy teraz, że jeśli istnieje taka maszyna probabilistyczna która rozwiązuje problem zatrzymania dla maszyn deterministycznych, moglibyśmy użyć jej do zbudowania maszyny deterministycznej która rozwiązuje problem zatrzymania dla maszyn deterministycznych - i wiemy, że taka maszyna nie może istnieć.$P$$H$

Załóżmy, że takie istnieje. Możemy skonstruować maszynę deterministyczną która przyjmuje jako dane wejściowe maszynę probabilistyczną z pewnym wejściem , któryM R $P$$M$$R$$x$

• zatrzymuje i akceptuje, jeśli i tylko jeśli akceptuje (tj. zatrzymuje i akceptuje na więcej niż połowie losowych ciągów).x R $R$$x$$R$$x$
• zatrzymuje i odrzuca, jeśli i tylko jeśli odrzuca (tj. zatrzymuje i odrzuca na więcej niż połowie losowych ciągów).x R $R$$x$$R$$x$
• w przeciwnym razie pętle

Zasadniczo będzie dla wszystkich symulować na wejściu i na każdym łańcuchu z jako przedrostek łańcucha na losowej taśmieTeraz:I ∈ 1 , 2 , . . . R x 0 , 1 i$M$$i \in 1, 2, ...$$R$$x$${{0,1}}^i$$R$

• jeśli prefiksy o długości zatrzymane i zaakceptowane bez próby odczytania więcej niż bitów z losowej taśmy, zatrzymuje się i akceptuje iRi$>\frac{1}{2}$$i$ $R$$i$$M$
• jeśli przedrostki o długości zatrzymane i odrzucone bez próby odczytania więcej niż bitów z losowej taśmy, zatrzyma się i odrzuci iRi$>\frac{1}{2}$$i$ $R$$i$$M$
• w przeciwnym razie uruchamia symulację za pomocą .i : = i + $M$$i := i+1$

Musimy się teraz przekonać, że jeśli przyjmuje (odrzuca) z prawdopodobieństwem , to dla niektórych akceptuje (odrzuca) dla przedrostków długość losowego ciągu bez próby odczytania więcej niż bitów z losowej taśmy. Jest to techniczne, ale dość łatwe - jeśli założymy inaczej, prawdopodobieństwo przyjęcia (odrzucenia) zbliża się do miarę, jak się do nieskończoności, stąd dla niektórych będzie musiało być .x p > $R$$x$ i>$p >\frac{1}{2}$$i$ iip>$>\frac{1}{2}$$i$$i$ iip>$p >\frac{1}{2}$$i$$i$$p >\frac{1}{2}$

Teraz po prostu definiujemy naszą deterministyczną maszynę rozwiązującą problem zatrzymania (tj. Decydujemy, czy dana deterministyczna maszyna akceptuje dane słowo ) a jako . Zauważ, że zawsze zatrzymuje się, ponieważ wybór języka przez nasze maszyny probabilistyczne został zdefiniowany w taki sposób, że zawsze występuje jedno z tych dwóch:N x H ( N , x ) = M ( P ( N , x ) ) M ( P ( N , x ) $H$$N$$x$$H(N,x) = M(P(N,x))$$M(P(N, x))$

• maszyna zatrzymuje się i przyjmuje ponad połowę losowych ciągów
• maszyna zatrzymuje się i odrzuca dla więcej niż połowy losowych ciągów.

Zależy to od tego, co rozumiesz przez algorytm probabilistyczny, który określa predykat.

Jest to prosta probabilistyczny algorytm P tak, że dla deterministycznej maszyny Turinga M ,

• P ( M ) przyjmuje z niezerowym prawdopodobieństwem, jeśli M zatrzyma się,
• P ( M ) nigdy nie akceptuje, jeśli M się nie zatrzymuje, oraz
• P ( M ) zatrzymanie z prawdopodobieństwem 1 dla wszystkich M .

Dlatego algorytm probabilistyczny P rozwiązuje w tym sensie problem zatrzymania deterministycznych maszyn Turinga. (Tutaj „ M zatrzymuje” oznacza „ M zatrzymuje na pustym wejściu”).

Jeśli jednak wzmocnisz wymaganie w jakikolwiek rozsądny sposób, jest mało prawdopodobne, że rozwiążesz problem zatrzymania deterministycznych maszyn Turinga. Na przykład,

• Jeśli wymagasz, aby P ( M ) zatrzymywał się zawsze zamiast z prawdopodobieństwem 1 , jasne jest, że P można symulować za pomocą algorytmu deterministycznego. (Zobacz Wikipedię, aby uzyskać wyjaśnienie różnicy między „zawsze” a „z prawdopodobieństwem 1.”)
• Jeśli ograniczysz granice błędu, wymagając, aby P ( M ) zatrzymał się i udzieliłeś właściwej odpowiedzi z prawdopodobieństwem znacznie większym niż 1/2 dla każdego M (to znaczy, nie obchodzi cię, czy P ( M ) nie zatrzymuje się, czy zatrzymuje podaj błędną odpowiedź w pozostałych przypadkach), następnie P można zasymulować za pomocą algorytmu deterministycznego przy użyciu argumentu zawartego w odpowiedzi Karoliny Sołtys .

Dlatego algorytm probabilistyczny nie może rozwiązać problemu zatrzymania deterministycznych maszyn Turinga w tych zmysłach.

$P$$P$$P$

Myślę, że taki był sens komentarza Raphaela.

$A\subseteq\mathbb N$$A$

de Leeuw, K., Moore, EF, Shannon, CE, i Shapiro, N. Obliczalność za pomocą maszyn probabilistycznych, badania Automata, s. 183–212. Kroniki studiów matematycznych, nr. 34. Princeton University Press, Princeton, NJ, 1956.

G. Sacks, Stopnie nierozwiązywalności, Princeton University Press, 1963.