Jaka jest różnica między niedeterminizmem a przypadkowością?

Niedawno to usłyszałem -
„Maszyna niedeterministyczna to nie to samo, co maszyna probabilistyczna. Mówiąc prymitywnie, maszyna niedeterministyczna to maszyna probabilistyczna, w której prawdopodobieństwa przejścia nie są znane”.

Czuję, że rozumiem, ale tak naprawdę nie. Czy ktoś mógłby mi to wyjaśnić (w kontekście maszyn lub ogólnie)?

Edycja 1:
Aby wyjaśnić, cytat był w kontekście skończonego automatu, ale pytanie to ma również znaczenie dla maszyn Turinga, ponieważ inni na nie odpowiedzieli.

Słyszę też, jak ludzie mówią - „... następnie wybieram obiekt x ze zbioru niedeterministycznie”. Kiedyś myślałem, że mają na myśli - „losowo”. Stąd zamieszanie.

Ważne jest, aby zrozumieć, że informatycy używają terminu „niedeterministyczny” inaczej niż zwykle w innych naukach. Niedeterministyczna TM jest faktycznie deterministyczna w sensie fizyki - to znaczy, NTM zawsze daje taką samą odpowiedź na danym wejściu: albo zawsze przyjmuje, albo zawsze odrzuca. Probabilistyczna TM przyjmie lub odrzuci dane wejściowe z pewnym prawdopodobieństwem, więc przy jednym uruchomieniu może je zaakceptować, a przy innym może odrzucić.

Bardziej szczegółowo: Na każdym etapie obliczeń wykonywanych przez NTM zamiast jednej reguły przejścia istnieje wiele reguł, które można wywołać. Aby ustalić, czy NTM akceptuje, czy odrzuca, należy spojrzeć na wszystkie możliwe gałęzie obliczeń. (Więc jeśli, powiedzmy, dokładnie 2 przejścia do wyboru na każdym kroku, a każda gałąź obliczeń ma w sumie N kroków, wówczas będą branych pod uwagę do rozważenia.) W przypadku standardowego NTM, wejście jest akceptowane jeśli jakakolwiek gałąź obliczeniowa akceptuje.$2^N$

Ostatnią część definicji można zmodyfikować, aby uzyskać inne powiązane typy maszyn Turinga. Jeśli jesteś zainteresowany problemami, które mają unikalne rozwiązanie, możesz poprosić TM o zaakceptowanie, jeśli akceptuje dokładnie jeden oddział. Jeśli interesuje Cię zachowanie większościowe, możesz zdefiniować bazę danych do akceptacji, jeśli akceptuje ją więcej niż połowa oddziałów. A jeśli losowo (według pewnego rozkładu prawdopodobieństwa) wybierzesz jedną z możliwych gałęzi i zaakceptujesz lub odrzucisz na podstawie tego, co robi ta gałąź, to masz probabilistyczną bazę TM.

W kontekście Maszyn Turinga „niedeterministyczny” naprawdę oznacza „równoległy”. Randomizowany algorytm może losowo eksplorować gałęzie drzewa obliczeniowego niedeterministycznej maszyny Turinga, ale niedeterministyczna maszyna Turinga może eksplorować je jednocześnie, co daje jej moc.

W innych kontekstach (nie mogę powiedzieć z twojego cytatu, czy mówisz o Maszynach Turinga), algorytm randomizowany może celowo używać losowości, podczas gdy algorytm, który chciałeś być deterministyczny, może w efekcie wykazywać niedeterminizm z powodu błędu ...

W odpowiedzi na Twoją edycję, gdy ludzie mówią „wybierz element ze zbioru niedeterministycznie”, możliwe, że mogą oznaczać „losowo”. Jednak możliwe jest również, że oznaczają one „magicznie wybierz element -right- ze zbioru”. Częstym sposobem przeglądania niedeterministycznych maszyn Turinga jest to, że najpierw magicznie „odgadną” rozwiązanie, a następnie sprawdzą jego poprawność. Oczywiście możesz zobaczyć tę magiczną domysł jako wynik sprawdzania wszystkich możliwości równolegle.

Istnieje kilka różnych kontekstów, w których „deterministyczny”, „losowy” i „niedeterministyczny” oznaczają trzy różne rzeczy. W kontekstach, w których jest wielu uczestników, takich jak bezpieczeństwo i współbieżność, intuicja często przypomina:

• deterministyczne oznacza „mogę wybrać”

• niedeterministyczny oznacza „ktoś inny może wybrać”

• losowy oznacza „nikt nie może wybrać”

Kilka przykładów:

1. [współbieżność, losowa] Rozważ protokół sieciowy, taki jak Ethernet , w którym wiele węzłów może wysłać wiadomość w dowolnym momencie. Jeśli dwa węzły wysyłają wiadomość w bardzo krótkich odstępach czasu, dochodzi do kolizji: wiadomości nakładają się i są nieczytelne. Jeśli dojdzie do kolizji, oba węzły muszą spróbować wysłać wiadomości ponownie później. Wyobraź sobie, że piszesz specyfikację Ethernet. Jak określić opóźnienie między ponownymi próbami? (Opóźnienia powinny być inne, inaczej nastąpi kolizja!)

   • deterministyczny: zdefiniuj algorytm, którego muszą używać oba węzły. Nie dzieje się tak w przypadku sieci Ethernet, ponieważ w celu uzyskania różnych wyników algorytm musiałby uprzywilejować jeden węzeł nad drugim (dla dowolnej zawartości wiadomości), a Ethernet tego nie robi.

   • niedeterministyczny: niech każdy implementator decyduje. Nie jest to dobre, ponieważ implementatory w obu węzłach mogą wybrać ten sam algorytm.

   • random: każdy węzeł musi losowo wybrać wartość opóźnienia (o określonym rozkładzie). Tak to działa. Istnieje małe prawdopodobieństwo, że dwa węzły wybiorą to samo opóźnienie i nastąpi kolejna kolizja, ale prawdopodobieństwo sukcesu wzrasta asymptotycznie w kierunku 1 wraz ze wzrostem liczby ponownych prób.

2. [współbieżność, niedeterministyczny] Piszesz algorytm współbieżny. W konkretnej sytuacji może wystąpić impas. Jak możesz zapobiec impasowi? To zależy od tego, jaki rodzaj planowania ma środowisko współbieżności.

   • deterministyczny: program planujący zawsze przełącza się między wątkami w pewnych ściśle określonych punktach, np. tylko wtedy, gdy kod wyraźnie ustępuje. Następnie po prostu zadbaj o to, aby nici nie ustępowały w złych momentach.

   • random: program planujący gwarantuje losowe przełączanie wątków. Wtedy wykonalną strategią może być wykrycie impasu, jeśli wystąpi, i zrestartowanie algorytmu od początku.

   • niedeterministyczny (większość harmonogramów jest taka): nie wiesz, kiedy harmonogram przełącza się między wątkami. Więc naprawdę musisz uniknąć impasu. Jeśli spróbujesz wykryć i uruchomić ponownie, jak w przypadkowym przypadku, ryzykujesz, że program planujący zaplanuje twoje wątki w dokładnie ten sam sposób.

3. [bezpieczeństwo, losowo] Piszesz aplikację z pytaniem o hasło. Jak modelujesz napastnika?

   • deterministyczny: atakujący zawsze próbuje tych samych haseł. To wcale nie jest użyteczny model atakującego - napastnicy nie są z definicji przewidywalni.

   • niedeterministyczny: atakujący w jakiś sposób zna twoje hasło i je wprowadza. To pokazuje ograniczenie haseł: należy je utrzymywać w tajemnicy. Jeśli twoje hasło jest tajne, ten atakujący jest nierealny.

   • random: atakujący losowo próbuje hasła. W tym przypadku jest to realistyczny model atakującego. Możesz dowiedzieć się, ile czasu zajmie osobie atakującej odgadnięcie hasła, w zależności od tego, jakiej używa losowej dystrybucji. Dobre hasło to takie, które długo zajmuje realistyczną dystrybucję.

4. [bezpieczeństwo, niedeterministyczny] Piszesz aplikację i martwisz się, że może mieć dziurę w zabezpieczeniach. Jak modelujesz napastnika?

   • deterministyczny: atakujący wie wszystko, co wiesz. Znowu nie jest to przydatny model atakującego.

   • random: atakujący wyrzuca losowe śmieci i ma nadzieję, że twój program się zawiesi. Czasami może to być przydatne ( fuzzing ), ale atakujący może być bardziej sprytny.

   • niedeterministyczny: jeśli jest dziura, atakujący ją w końcu znajdzie. Lepiej więc zahartuj swoją aplikację (podnieś wymaganie inteligencji atakującego; zwróć uwagę, że ponieważ jest to wymóg inteligencji, a nie wymóg obliczeniowy, liczy się to jako niedeterministyczne, dopóki nie pojawi się AI), lub lepiej, udowodnij, że nie ma dziura w zabezpieczeniach i dlatego taki atakujący nie istnieje.

Przykład, aby wyjaśnić:

Powiedz, że musisz wybrać drzwi do otwarcia wśród 10000 drzwi (powiedz, że za jednymi z nich stoi nagroda). Wybór losowy oznacza, że ​​wybierzesz jedno ze 10000 drzwi i wejdziesz do niego. Jeśli za jednymi drzwiami jest nagroda, najprawdopodobniej jej nie znajdziesz. Niedeterministyczna maszyna wszedłaby jednocześnie do wszystkich 10000 drzwi. Jeśli gdziekolwiek jest nagroda, niedeterministyczna maszyna ją znajdzie.

Definicja niedeterministycznej maszyny Turinga : Maszyna Turinga, która ma więcej niż jeden następny stan dla niektórych kombinacji zawartości bieżącej komórki i bieżącego stanu. Dane wejściowe są akceptowane, jeśli jakakolwiek sekwencja ruchu prowadzi do akceptacji.

Definicja probabilitycznej maszyny Turinga : niedeterministyczna maszyna Turinga (TM), która losowo wybiera pomiędzy dostępnymi przejściami w każdym punkcie zgodnie z pewnym rozkładem prawdopodobieństwa.

Probabilistyczna maszyna Turinga to niedeterministyczna maszyna Turinga, która może popełniać błędy.

PPT uważam za pomocny.

Wolę następującą definicję:

Nie ma czegoś takiego jak probabilistyczna maszyna Turinga! Istnieją tylko maszyny deterministyczne (na każdym etapie pojedynczy możliwy stan kontrolny) i maszyny niedeterministyczne (na każdym etapie stała liczba możliwych stanów kontrolnych).

Niedeterminizm działa w następujący sposób: Rozważ maszynę niedeterministyczną, która zatrzymuje się na każdym wejściu (możliwe, jeśli problem jest rozstrzygalny), w której każde możliwe obliczenie wykorzystuje tę samą liczbę kroków i gdzie każdy krok ma dokładnie 2 możliwe stany kontrolne ( oba nie są tak naprawdę ograniczeniem). Podobnie jak w definicji NP, niedeterministyczna maszyna przyjmuje dane wejściowe, jeśli istnieje co najmniej jedno możliwe obliczenie akceptujące, a odrzuca dane wejściowe, jeśli wszystkie obliczenia odrzucają.

Losowość wchodzi w grę w następujący sposób: Możesz wybrać jednolicie losowo pojedynczą ścieżkę obliczeń z takiej niedeterministycznej maszyny, jak wspomniano powyżej. Akceptujesz wtedy i tylko wtedy, gdy ta losowo wybrana ścieżka obliczeniowa akceptuje. To randomizowane podejście „rozwiązuje” Twój problem, jeśli z ogromnym prawdopodobieństwem ta odpowiedź jest poprawna.

Tak więc różnica między niedeterminizmem a przypadkowością polega na tym, czy szukasz zwykłego istnienia prawidłowej odpowiedzi typu „tak” (i wiarygodnych odpowiedzi „nie”), czy też jesteś zainteresowany rozwiązaniem swojego problemu „przez większość czasu” .

Mówiąc prościej: niedeterministyczna maszyna może optymalnie wybrać wynik każdego rzutu monetą (jeśli podoba ci się analogia z maszyną probabilistyczną). Można sobie również wyobrazić, że wykonuje obliczenia dla każdego wyniku rzutu monetą równolegle.

Cofanie się podczas debugowania jako motywacja do niedeterminizmu

Pojęcie niedeterministycznej maszyny sugeruje się, gdy chcesz przejść wstecz (w czasie) przez program podczas debugowania. Na typowym komputerze każdy krok modyfikuje tylko skończoną ilość pamięci. Jeśli zawsze zapisujesz te informacje dla poprzednich 10000 kroków, możesz ładnie poruszać się zarówno do przodu, jak i do tyłu w programie, a ta możliwość nie ogranicza się do programów zabawkowych. Jeśli spróbujesz usunąć asymetrię między krokami naprzód i krokami wstecznymi, to skończy się to pojęciem niedeterministycznej maszyny.

Podobieństwa i różnice między niedeterminizmem a przypadkowością

Chociaż maszyny probabilistyczne mają pewne cechy wspólne z maszynami niedeterministycznymi, ta symetria między krokami do przodu i krokami do tyłu nie jest wspólna. Aby to zobaczyć, modelujmy kroki lub przejścia maszyny deterministycznej za pomocą (całkowitych lub częściowych) funkcji, przejścia maszyny niedeterministycznej przez (skończone) relacje oraz przejścia maszyny probabilistycznej za pomocą (pod) macierzy stochastycznych . Na przykład tutaj są odpowiednie definicje automatów skończonych

• $Q$
• $\Sigma$
• $\delta:Q\times \Sigma \to Q$
• $\Delta:Q\times \Sigma \to P(Q)$
• $\Delta\subset Q\times \Sigma \times Q$
• $\Delta: \Sigma \to P(Q \times Q)$
• $\delta: \Sigma \to ssM(Q)$

$P(Q)$$Q$$ssM(Q)$$Q$

Istnieje wiele różnych uzasadnionych warunków akceptacji

Przejścia są tylko jedną częścią maszyny, stany początkowe i końcowe, możliwe warunki wyjściowe i akceptacyjne są również ważne. Istnieje jednak bardzo niewiele nierównoznacznych warunków akceptacji dla maszyn deterministycznych, szereg rozsądnych warunków akceptacji dla maszyn niedeterministycznych (NP, coNP, #P, ...) i wiele możliwych warunków akceptacji dla maszyn probabilistycznych. Dlatego odpowiedź ta koncentruje się przede wszystkim na przejściach.

Odwracalność nie jest trywialna dla maszyn probabilistycznych

$P P^T P\neq P$$P$$B$$A$$k$$A$$B$$k$

Odwracalność jest trudna nawet w przypadku maszyn niedeterministycznych

$P P^T P\neq P$$R\circ R^{op}\circ R \neq R$$R$$R$$R\circ R^{op}\circ R = R$$R^{op}\circ R\circ R^{op} = R^{op}$$P$$Q$$P\circ Q$

Te rozważania mają również sens w przypadku automatów wypychających

Ten post sugeruje, że jedną z motywacji dla niedeterminizmu jest usunięcie tej asymetrii między krokami naprzód i krokami wstecz. Czy ta symetria niedeterminizmu ogranicza się do automatów skończonych? Oto odpowiednie definicje symetryczne dla automatów pushdown

• $Q$
• $\Sigma$
• $\Gamma$
• $\delta:Q\times\Gamma\times (\Sigma\cup\{\epsilon\}) \to Q\times\Gamma^{\{0,2\}}$$\delta(q,\gamma,\epsilon)\neq\epsilon$$\delta(q,\gamma,\sigma)=\epsilon$$\sigma\in\Sigma$
• $\Delta:Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \to P(Q\times\Gamma^{\{0,1\}})$
• $\Delta\subset Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \times Q\times\Gamma^{\{0,1\}}$
• $\Delta: \Sigma\cup\{\epsilon\} \to P(Q\times\Gamma^{\{0,1\}}\ \times\ Q\times\Gamma^{\{0,1\}})$
• $\delta: \Sigma\cup\{\epsilon\} \to ssM(Q\times\Gamma^{\{0,1\}})$$\delta(\epsilon)+\delta(\sigma)\in ssM(Q\times\Gamma^{\{0,1\}})$$\sigma\in\Sigma$

$\epsilon$$\Gamma^{\{0,2\}}=\{\epsilon\}\cup\Gamma\cup(\Gamma\times\Gamma)$$\Gamma^{\{0,1\}}=\{\epsilon\}\cup\Gamma$$\Gamma^*$

Schematyczna weryfikacja odwrócenia dla (nie) zaawansowanych operacji wprowadzania i stosu

$b\in\Sigma\subset\Sigma\cup\{\epsilon\}$

$a|bc \to a|\boxed{b}c \to ab|c$
$a|bc \leftarrow a\boxed{b}|c \leftarrow ab|c$
$c|ba \to c|\boxed{b}a \to cb|a$

$\epsilon\in\Sigma\cup\{\epsilon\}$

$a|bc \to a|bc \to a|bc$
$a|bc \leftarrow a|bc \leftarrow a|bc$
$cb|a \to cb|a \to cb|a$

Oto schemat postępującej operacji wprowadzania, której odwrócenie wyglądałoby źle

$\require{cancel}\xcancel{\begin{matrix} a|bc \to \boxed{a}|bc \to ab|c\\ a|bc \leftarrow \boxed{a}b|c \leftarrow ab|c\\ c|ba \to c|b\boxed{a} \to cb|a \end{matrix}}$

Dla operacji na stosie istnieją trzy przypadki , i . Operacja na stosie zostaje odwrócona na w następujący sposób$(s,t) \in \Gamma^{\{0,1\}}\times\Gamma^{\{0,1\}}$$(s,t)=(a,\epsilon)$$(s,t)=(\epsilon,a)$$(s,t)=(a,b)$$(a,\epsilon)$$(\epsilon,a)$

$ab\ldots \to \boxed{a}b\ldots \to |b\ldots$
$\boxed{a}b\ldots \leftarrow |b\ldots \leftarrow b\ldots$
$b\ldots \to |b\ldots \to \boxed{a}b\ldots$

Operacja na stosie zostaje odwrócona do w następujący sposób$(a,b)$$(b,a)$

$ac\ldots \to \boxed{a}c\ldots \to \boxed{b}c\ldots$
$\boxed{a}c\ldots \leftarrow \boxed{b}c\ldots \leftarrow bc\ldots$
$bc\ldots \to \boxed{b}c\ldots \to \boxed{a}c\ldots$

Uogólniona operacja stosu zostałaby odwrócona do$(ab,cde)\in\Gamma^*\times\Gamma^*$$(cde,ab)$

b f ... ← c d e f ... ← c d e f ... c d e f ... → c d e f ... → b f $abf\ldots \to \boxed{ab}f\ldots \to \boxed{cde}f\ldots$
$\boxed{ab}f\ldots \leftarrow \boxed{cde}f\ldots \leftarrow cdef\ldots$
$cdef\ldots \to \boxed{cde}f\ldots \to \boxed{ab}f\ldots$

Odwracalność dla maszyn Turinga

Maszyna z więcej niż jednym stosem jest równoważna maszynie Turinga, a operacje na stosie można łatwo odwrócić. Motywacja na początku sugeruje również, że odwrócenie (maszyny Turinga) nie powinno być trudne. Maszyna Turinga z typowym zestawem instrukcji nie jest tak świetna do cofania, ponieważ symbol pod głową może wpływać na to, czy taśma przesunie się w lewo czy w prawo. Ale jeśli zestaw instrukcji zostanie odpowiednio zmodyfikowany (bez zmniejszania mocy obliczeniowej maszyny), wówczas odwrócenie jest znowu prawie banalne.

Odwrócenie można również wykonać bez modyfikowania zestawu instrukcji, ale nie jest ono kanoniczne i trochę brzydkie. Może się wydawać, że istnienie odwrócenia jest równie trudne do rozstrzygnięcia, jak wiele innych pytań dotyczących maszyn Turinga, ale odwrócenie jest lokalną konstrukcją, a trudne pytania często mają charakter globalny, więc pesymizm byłby tutaj prawdopodobnie nieuzasadniony.

Chęć przejścia na równoważne zestawy instrukcji (łatwiejsze do odwrócenia) pokazuje, że pytania te są mniej oczywiste, niż się pojawiają. Bardziej subtelna zmiana miała miejsce w tym poście wcześniej, gdy funkcje całkowite i macierze stochastyczne zostały zastąpione funkcjami częściowymi i macierzami podochastycznymi. Ten przełącznik nie jest absolutnie konieczny, ale w przeciwnym razie zmiana jest brzydka. Przejście na macierze substochastyczne było w rzeczywistości punktem, w którym stało się oczywiste, że odwracalność wcale nie jest tak trywialna, i że należy zapisać szczegóły (jak to zrobiono powyżej) zamiast przyjmować jedynie perspektywę na wysokim poziomie (przedstawioną w motywacji na początek). Pytania zadane przez Niel de Beaudrap przyczyniły się również do uświadomienia sobie, że perspektywa wysokiego poziomu jest nieco niepewna.

Wniosek

Maszyny niedeterministyczne umożliwiają skończoną liczbę deterministycznych przejść na każdym etapie. W przypadku maszyn probabilistycznych przejścia te mają dodatkowo prawdopodobieństwo. Ten post przedstawia inne spojrzenie na niedeterminizm i przypadkowość. Ignorując globalne warunki akceptacji, koncentruje się na lokalnej odwracalności (jako lokalnej symetrii). Ponieważ losowość zachowuje pewne lokalne symetrie, których determinizm nie zachowuje, perspektywa ta ujawnia nietrywialne różnice między maszynami niedeterministycznymi i probabilistycznymi.

$n$$2^n$ stanów wykładniczych) przez uwzględnienie klas równoważności stanów, bez względu na to, czy algorytm zaimplementowany w maszynie obejmuje randomizację lub prawdopodobieństwa (patrz poniżej).

Ale jeśli algorytm zaimplementowany w maszynie wiąże się z randomizacją lub prawdopodobieństwami (nieodłącznymi w algorytmie), to jest to maszyna losowa (lub probabilistyczna).

Zasadniczo zawsze możliwe jest usunięcie niedeterminizmu z maszyny i skonstruowanie deterministycznego odpowiednika (patrz algorytm powyżej), ale nie można tego zrobić (ogólnie) w celu usunięcia randomizacji (w kontekście powyższego), ponieważ jest to nieodłączny od zaimplementowanego algorytmu .

Zauważ, że w świetle powyższego, zarówno maszyna deterministyczna , jak i maszyna niedeterministyczna mogą być probabilistyczne, jeśli algorytm (zaangażowany) używa w ten sposób randomizacji (lub prawdopodobieństw).

Podsumowując, niedeterminizm w automatach (w tym kontekście) odnosi się do klas podobnych automatów, podczas gdy maszyny losowe lub probabilistyczne odnoszą się do (rzeczywistego zastosowania randomizacji w) rzeczywistych algorytmów zaimplementowanych przez te automaty.