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

29

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ć.

computability randomness turing-machines

— Joey Adams
źródło

3

@downvoter: To nie powinno było otrzymać negatywnego wyniku bez komentarza.

— Dave Clarke

3

Co uniemożliwia deterministycznej TM wyliczenie wszystkich przypadków? Tutaj sprawdzanie zgadywania jest problemem, a nie zgadywaniem samego siebie. Zauważ również, że tak naprawdę nie możesz powiedzieć, że jesteś silniejszy, jeśli tworzysz pożądany wynik tylko z prawdopodobieństwem .

p < 1

$p<1$

— Raphael,

1

„program deterministyczny nie może wytworzyć łańcucha, którego złożoność jest większa niż jego długość”. Wystarczy, że jakaś inna deterministyczna maszyna wyprowadza to samo wyjście. Zauważ, że deterministyczne TM mogą symulować nie tylko probabilistyczne, ale nawet niedeterministyczne TM (z dowolną liczbą zmian).

— Kaveh

Wczoraj chciałem powiedzieć - patrząc na Kaveha i in. - to było zbyt podstawowe pytanie dla tej strony (to samo pytanie dla NTM jest podstawowym wynikiem na każdym pierwszym kursie teorii). Biorąc pod uwagę, że sformalizowanie „probabilistycznej TM” wymagało sporo wysiłku, cieszę się, że tego nie zrobiłem.

— Raphael

1

I zobacz wyjaśniające odpowiedzi na moje wcześniejsze powiązane pytanie TCS: cstheory.stackexchange.com/questions/1263/…

— Joseph O'Rourke

22

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 . $L$ $x \in 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óry $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). $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). $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: $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 $>\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 $>\frac{1}{2}$ $i$ $R$ $i$ $M$
w przeciwnym razie uruchamia symulację za pomocą . $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ć . $R$ $x$ $p >\frac{1}{2}$ $i$ $>\frac{1}{2}$ $i$ $i$ $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: $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.

— Karolina Sołtys
źródło

Dziękuję za opracowanie mojego komentarza! ;) Dwa techniczne uwagi: w punkcie pierwszym masz na myśli ? Na koniec masz na myśli ?

> 2^{i - 1}

$>2^{i-1}$

S (Q)

$S(Q)$

— Raphael

1

Zauważ, że jeśli nie wymaga się, aby P zawsze się zatrzymywał, zbudowanie nawet deterministycznej maszyny Turinga P jest banalne, która akceptuje tylko wtedy, gdy dana deterministyczna maszyna Turinga się zatrzyma.

— Tsuyoshi Ito,

Jakie jest twoje założenie? Nie można zanegować probabilistycznej maszyny Turinga, chyba że zostanie ona ostatecznie zatrzymana.

— Tsuyoshi Ito,

Prawdopodobieństwo zatrzymania jest przejmowane przez dodatkowy ciąg ORAZ słowa wejściowe, czy co?

— M. Alaggan

1

@Mohammad ALAGGAN: Nie, ta część jest poprawna, jak napisano: prawdopodobieństwo jest przejmowane tylko dodatkowy ciąg (określający wyniki rzutów monetą). Ponieważ nie zakładamy żadnego rozkładu prawdopodobieństwa na ciągu wejściowym, prawdopodobieństwo na ciągu wejściowym nie jest dobrze zdefiniowane. Nawet jeśli zdefiniowano rozkład prawdopodobieństwa w ciągu wejściowym, wysokie prawdopodobieństwo poprawnej odpowiedzi w ciągu wejściowym oznacza tylko, że algorytm jest poprawny dla większości danych wejściowych, co różni się od zwykłego wymogu dotyczącego algorytmu.

— Tsuyoshi Ito

14

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.

— Tsuyoshi Ito
źródło

Wybacz moją ignorancję, ale jaka jest różnica między zatrzymaniem „zawsze” a zatrzymaniem „z prawdopodobieństwem 1”?

— Rob Simmons,

1

@Rob: Myślę, że to trudna kwestia. Zastanów się nad prostą probabilistyczną maszyną Turinga, która po prostu rzuca monetą wielokrotnie, aż wynik będzie najwyższy. Ta maszyna Turinga zatrzymuje się, z wyjątkiem sytuacji, gdy wszystkie rzuty monetą powodują ogony. Dlatego zatrzymuje się z prawdopodobieństwem 1, ale nie zawsze się zatrzymuje.

— Tsuyoshi Ito

W Wikipedii znalazłem wyjaśnienie różnicy między „zawsze” a „z prawdopodobieństwem 1” i dodałem ten sam link w odpowiedzi.

— Tsuyoshi Ito

Jeśli pozwolisz, aby P (M) zawiodło, nie zatrzymując się, to nie wiem, jak możesz wykonać deterministyczną symulację. Załóżmy na przykład, że uruchamiasz deterministyczną symulację na pewnym zestawie ciągów prefiksów o długości N, a po pewnym czasie <50% prefiksów zostało zatrzymanych i udzieliło odpowiedzi. Skąd wiesz, czy pozostałe ciągi prefiksów potrzebują więcej czasu na zwrócenie odpowiedzi, czy też wszystkie są zablokowane w nieskończonej pętli w ramach warunku niepowodzenia? Jeśli ten pierwszy, nadal czekasz. Jeśli to drugie, zakończysz obecną rundę i uruchomisz ponownie na wszystkich prefiksach długości N + 1.

— Mike Battaglia,

Ale nie można tego ustalić, ponieważ jest to problem zatrzymania! Nie mamy możliwości dowiedzieć się, czy maszyna Turinga zatrzyma się na tych wejściach, czy nie.

— Mike Battaglia,

12

$P$ $P$ $P$

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

— Marc
źródło

7

$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.

— Bjørn Kjos-Hanssen
źródło